Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class.
Erik D. DemaineTimothy D. GoodrichKyle KlosterBrian LavalleeQuanquan C. LiuBlair D. SullivanAli VakilianAndrew van der PoelPublished in: ESA (2019)
Keyphrases
- approximation algorithms
- np hard
- undirected graph
- special case
- worst case
- vertex cover
- minimum cost
- precedence constraints
- np hardness
- facility location problem
- primal dual
- set cover
- approximation ratio
- np complete
- computational complexity
- approximation guarantees
- open shop
- network design problem
- linear programming
- approximation schemes
- exact algorithms
- linear program
- constant factor
- randomized algorithms
- polynomial time approximation
- lower bound
- disjoint paths
- spanning tree
- finite number
- integer programming
- knapsack problem
- branch and bound algorithm
- optimal solution