Approximation Algorithms for Matroidal and Cardinal Generalizations of Stable Matching.
Gergely CsájiTamás KirályYu YokoiPublished in: SOSA (2023)
Keyphrases
- approximation algorithms
- np hard
- special case
- vertex cover
- minimum cost
- worst case
- primal dual
- randomized algorithms
- facility location problem
- set cover
- graph matching
- open shop
- network design problem
- np hardness
- approximation ratio
- constant factor
- exact algorithms
- optimal solution
- constant factor approximation
- polynomial time approximation
- undirected graph
- scheduling problem
- precedence constraints
- upper bound