Improved Approximation Algorithms for a Bilevel Knapsack Problem.
Xian QiuWalter KernPublished in: COCOON (2014)
Keyphrases
- approximation algorithms
- knapsack problem
- np hard
- exact algorithms
- implicit enumeration
- linear programming
- special case
- optimal solution
- combinatorial optimization problems
- worst case
- multidimensional knapsack problem
- vertex cover
- production planning
- set cover
- linear programming relaxation
- optimization problems
- integer programming
- open shop
- minimum cost
- network design problem
- dynamic programming
- lower bound
- scheduling problem
- randomized algorithms
- primal dual
- greedy heuristic
- undirected graph
- branch and bound algorithm
- approximation ratio
- maximum profit
- constraint satisfaction problems
- constant factor approximation
- constant factor
- objective function
- precedence constraints
- cutting plane
- greedy algorithm