Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions.
Khaled M. ElbassioniTrung Thanh NguyenPublished in: Discret. Appl. Math. (2017)
Keyphrases
- approximation algorithms
- packing problem
- constraint programming
- np hard
- special case
- vertex cover
- worst case
- precedence constraints
- quadratic program
- minimum cost
- network design problem
- approximation ratio
- constraint satisfaction
- integer programming
- constant factor
- bin packing
- open shop
- primal dual
- polynomial time approximation
- approximation schemes
- global constraints
- set cover
- computational complexity
- randomized algorithms
- constrained minimization
- cutting stock
- binary variables
- linear constraints
- undirected graph
- combinatorial auctions
- convex optimization
- np complete
- disjoint paths
- linear programming