Polynomiality for Bin Packing with a Constant Number of Item Types

DOI10.1137/1.9781611973402.61zbMath1421.68080arXiv1307.5108OpenAlexW2158214373MaRDI QIDQ5384022

Michel X. Goemans, Thomas Rothvoß

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1307.5108

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Related Items (29)

Tightness of sensitivity and proximity bounds for integer linear programs ⋮ Huge Unimodular $n$-Fold Programs ⋮ Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ The Support of Integer Optimal Solutions ⋮ Parameterized complexity of configuration integer programs ⋮ A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics ⋮ Fair and efficient allocation with few agent types, few item types, or small value levels ⋮ Scheduling and fixed-parameter tractability ⋮ Block-structured integer programming: can we parameterize without the largest coefficient? ⋮ Breaking symmetries to rescue sum of squares in the case of makespan scheduling ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ Parameterized complexity of strip packing and minimum volume packing ⋮ Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines ⋮ An EPTAS for scheduling fork-join graphs with communication delay ⋮ Unnamed Item ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ Unnamed Item ⋮ A PTAS for Scheduling Unrelated Machines of Few Different Types ⋮ Unnamed Item ⋮ Streaming algorithms for bin packing and vector scheduling ⋮ An EPTAS for scheduling on unrelated machines of few different types ⋮ Closing the Gap for Makespan Scheduling via Sparsification Techniques ⋮ About the Structure of the Integer Cone and Its Application to Bin Packing ⋮ Feasibility criteria for high-multiplicity partitioning problems ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Minimizing machine assignment costs over \(\Delta\)-approximate solutions of the scheduling problem \(P||C_{\max}\) ⋮ Packing-based branch-and-bound for discrete malleable task scheduling ⋮ Online bin packing with advice

This page was built for publication: Polynomiality for Bin Packing with a Constant Number of Item Types