Improved Approximation Lower Bounds for Vertex Cover on Power Law Graphs and Some Generalizations
Mikael GastMathias HauptmannMarek KarpinskiPublished in: CoRR (2012)
Keyphrases
- power law
- vertex cover
- approximation algorithms
- lower bound
- np hard
- small world
- planar graphs
- approximation guarantees
- worst case
- real world graphs
- polynomial time approximation
- degree distribution
- upper bound
- branch and bound algorithm
- scale free
- precedence constraints
- random graphs
- approximation ratio
- constant factor
- special case
- undirected graph
- power law distribution
- optimal solution
- objective function
- linear programming relaxation
- minimum cost
- greedy algorithm
- partition function
- scheduling problem
- error bounds
- upper and lower bounds
- lower and upper bounds