Approximation Algorithms for 3D Orthogonal Knapsack.
Florian DiedrichRolf HarrenKlaus JansenRalf ThöleHenning ThomasPublished in: J. Comput. Sci. Technol. (2008)
Keyphrases
- approximation algorithms
- np hard
- knapsack problem
- special case
- worst case
- vertex cover
- dynamic programming
- minimum cost
- facility location problem
- upper bound
- optimal solution
- primal dual
- greedy heuristic
- network design problem
- exact algorithms
- approximation ratio
- approximation schemes
- open shop
- np hardness
- constant factor
- precedence constraints
- undirected graph
- feasible solution
- objective function
- set cover
- column generation