On the Integrality Gap of the Prize-Collecting Steiner Forest LP.
Jochen KönemannNeil OlverKanstantsin PashkovichR. RaviChaitanya SwamyJens VygenPublished in: CoRR (2017)
Keyphrases
- integrality gap
- prize collecting
- linear program
- linear programming relaxation
- lp relaxation
- linear programming
- lower bound
- valid inequalities
- arbitrarily close
- approximation algorithms
- primal dual
- knapsack problem
- single machine scheduling problem
- integer programming
- message passing
- feasible solution
- mixed integer programming
- travel time
- optimal solution
- integer programming formulation
- integer program
- energy minimization
- finite number
- branch and bound
- np hardness
- mixed integer
- distributed systems
- low degree
- column generation
- maximum a posteriori
- traveling salesman problem
- mathematical model
- particle swarm optimization
- upper bound
- genetic algorithm
- dynamic programming
- objective function