Search Results

Documents authored by Pirotton, Lis

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.116
A Tight Double-Exponential Lower Bound for High-Multiplicity Bin Packing

Authors: Klaus Jansen, Felix Ohnesorge, and Lis Pirotton

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
Consider a high-multiplicity Bin Packing instance I with d distinct item types. In 2014, Goemans and Rothvoss gave an algorithm with runtime (|I|²)^O(d) for this problem [SODA'14], where |I| denotes the encoding length of the instance I. Although Jansen and Klein [SODA'17] later developed an algorithm that improves upon this runtime in a special case, it has remained a major open problem by Goemans and Rothvoss [J.ACM'20] whether the doubly exponential dependency on d is necessary. We solve this open problem by showing that unless the Exponential Time Hypothesis (ETH) fails, there is no algorithm solving the high-multiplicity Bin Packing problem in time (|I|²)^o(d). To prove this, we introduce a novel reduction from 3-SAT. The core of our construction is efficiently encoding all information from a 3-SAT instance with n variables into an ILP with O(log n) variables and constraints. This result confirms that the Goemans and Rothvoss algorithm is essentially best-possible for Bin Packing parameterized by the number d of item sizes in the context of XP time algorithms.
Cite as

Klaus Jansen, Felix Ohnesorge, and Lis Pirotton. A Tight Double-Exponential Lower Bound for High-Multiplicity Bin Packing. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 116:1-116:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ICALP.2026.116,
  author =	{Jansen, Klaus and Ohnesorge, Felix and Pirotton, Lis},
  title =	{{A Tight Double-Exponential Lower Bound for High-Multiplicity Bin Packing}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{116:1--116:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.116},
  URN =		{urn:nbn:de:0030-drops-265051},
  doi =		{10.4230/LIPIcs.ICALP.2026.116},
  annote =	{Keywords: Bin Packing, Lower Bound, Computational Complexity, ETH}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.15
New Algorithm for Combinatorial n-Folds and Applications

Authors: Klaus Jansen, Kai Kahler, Lis Pirotton, and Malte Tutas

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
Block-structured integer linear programs (ILPs) play an important role in various application fields. We address n-fold ILPs where the matrix 𝒜 has a specific structure, i.e., where the blocks in the lower part of 𝒜 consist only of the row vectors (1,… ,1). In this paper, we propose an approach tailored to exactly these combinatorial n-folds. We utilize a divide and conquer approach to separate the original problem such that the right-hand side iteratively decreases in size. We show that this decrease in size can be calculated such that we only need to consider a bounded amount of possible right-hand sides. This, in turn, lets us efficiently combine solutions of the smaller right-hand sides to solve the original problem. We can decide the feasibility of, and also optimally solve, such problems in time (n r Δ)^O(r) log(‖b‖_∞), where n is the number of blocks, r the number of rows in the upper blocks and Δ = ‖A‖_∞. We complement the algorithm by discussing applications of the n-fold ILPs with the specific structure we require. We consider the problems of (i) scheduling on uniform machines, (ii) closest string and (iii) (graph) imbalance. Regarding (i), our algorithm results in running times of p_max^O(d)|I|^O(1), matching a lower bound derived via ETH. For (ii) we achieve running times matching the current state-of-the-art in the general case. In contrast to the state-of-the-art, our result can leverage a bounded number of column-types to yield an improved running time. For (iii), we improve the parameter dependency on the size of the vertex cover.
Cite as

Klaus Jansen, Kai Kahler, Lis Pirotton, and Malte Tutas. New Algorithm for Combinatorial n-Folds and Applications. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.IPEC.2025.15,
  author =	{Jansen, Klaus and Kahler, Kai and Pirotton, Lis and Tutas, Malte},
  title =	{{New Algorithm for Combinatorial n-Folds and Applications}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.15},
  URN =		{urn:nbn:de:0030-drops-251472},
  doi =		{10.4230/LIPIcs.IPEC.2025.15},
  annote =	{Keywords: integer linear programming, n-fold, parameterized complexity, scheduling, uniform machines}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.48
The Support of Bin Packing Is Exponential

Authors: Klaus Jansen, Lis Pirotton, and Malte Tutas

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Consider the classical Bin Packing problem with d different item sizes s_i and amounts of items a_i. The support of a Bin Packing solution is the number of differently filled bins. In this work, we show that the lower bound on the support of this problem is 2^Ω(d). Our lower bound matches the upper bound of 2^d given by Eisenbrand and Shmonin [Oper.Research Letters '06] up to a constant factor. This result has direct implications for the time complexity of several Bin Packing algorithms, such as Goemans and Rothvoss [SODA '14], Jansen and Klein [SODA '17] and Jansen and Solis-Oba [IPCO '10]. To achieve our main result, we develop a technique to aggregate equality constrained ILPs with many constraints into an equivalent ILP with one constraint. Our technique contrasts existing aggregation techniques as we manage to integrate upper bounds on variables into the resulting constraint. We believe this technique can be useful for solving general ILPs or the d-dimensional knapsack problem.
Cite as

Klaus Jansen, Lis Pirotton, and Malte Tutas. The Support of Bin Packing Is Exponential. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ESA.2025.48,
  author =	{Jansen, Klaus and Pirotton, Lis and Tutas, Malte},
  title =	{{The Support of Bin Packing Is Exponential}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{48:1--48:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.48},
  URN =		{urn:nbn:de:0030-drops-245167},
  doi =		{10.4230/LIPIcs.ESA.2025.48},
  annote =	{Keywords: Bin Packing, Integer Programming, Support}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact