Approximation algorithms and an integer program for multi-level graph spanners.
Abu Reyan AhmedKeaton HammMohammad Javad Latifi JebelliStephen G. KobourovFaryad Darabi SahnehRichard SpencePublished in: CoRR (2019)
Keyphrases
- approximation algorithms
- integer program
- undirected graph
- np hard
- constant factor
- minimum cost
- integer programming
- column generation
- disjoint paths
- network flow
- special case
- linear program
- vertex cover
- worst case
- set cover
- spanning tree
- facility location problem
- linear programming relaxation
- randomized algorithms
- primal dual
- open shop
- linear programming
- approximation ratio
- lower bound
- approximation schemes
- random walk
- cutting plane
- planar graphs
- connected components
- directed graph
- precedence constraints
- valid inequalities
- approximation guarantees
- dynamic programming
- scheduling problem
- combinatorial auctions
- weighted graph
- optimal solution