Restricted Max-Min Allocation: Approximation and Integrality Gap.
Siu-Wing ChengYuchen MaoPublished in: CoRR (2019)
Keyphrases
- max min
- integrality gap
- linear programming relaxation
- linear program
- approximation algorithms
- lower bound
- valid inequalities
- min max
- arbitrarily close
- linear programming
- lp relaxation
- primal dual
- knapsack problem
- branch and bound
- low degree
- finite number
- integer program
- column generation
- integer programming
- special case
- resource allocation
- hill climbing
- objective function
- optimal solution
- upper bound
- robust optimization
- feasible solution
- mixed integer programming
- genetic programming
- convex hull
- scheduling problem
- np hard
- approximation guarantees
- agnostic learning
- mixed integer
- neural network