Bin Packing via Discrepancy of Permutations
Abstract
A well-studied special case of bin packing is the 3-partition problem , where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxation for this problem into an integral solution that requires at most O (log n ) additional bins.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 01, 2013
- Source ID
- 10.1145/2483699.2483704
Entities
People
- Dömötör Pálvölgyi
- Friedrich Eisenbrand
- Thomas Rothvoß
Organizations
- Alexander von Humboldt Foundation
- Division of Computing and Communication Foundations
- Eötvös Loránd University
- German Research Foundation
- Hungarian Academy of Sciences
- Hungarian Scientific Research Fund
- Massachusetts Institute of Technology
- Office of Naval Research
- Swiss Federal Institute of Technology in Lausanne
- Swiss National Science Foundation