Approximation algorithms for maximum matchings in undirected graphs.
Fanny DufosséKamer KayaIoannis PanagiotasBora UçarPublished in: CSC (2018)
Keyphrases
- approximation algorithms
- undirected graph
- np hard
- special case
- minimum cost
- worst case
- disjoint paths
- vertex cover
- approximation ratio
- integrality gap
- primal dual
- open shop
- set cover
- randomized algorithms
- constant factor approximation
- constant factor
- polynomial time approximation
- planar graphs
- multicommodity flow
- upper bound