Approximation algorithms for a hierarchically structured bin packing problem.
Bruno CodenottiGianluca De MarcoMauro LeonciniManuela MontangeroMassimo SantiniPublished in: Inf. Process. Lett. (2004)
Keyphrases
- hierarchically structured
- approximation algorithms
- precedence constraints
- np hard
- lower bound
- hierarchical structure
- special case
- bin packing
- vertex cover
- worst case
- minimum cost
- randomized algorithms
- facility location problem
- network design problem
- primal dual
- approximation ratio
- np hardness
- set cover
- branch and bound algorithm
- knapsack problem
- undirected graph
- packing problem
- open shop
- constant factor
- approximation guarantees
- dynamic programming
- scheduling problem
- polynomial time approximation
- approximation schemes
- objective function
- information retrieval