12 Search Results for "Pokutta, Sebastian"

Document
DOI: 10.4230/LIPIcs.SoCG.2026.52
Online Packing of Orthogonal Polygons

Authors: Tim Gerlach, Benjamin Hennies, and Linda Kleist

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
While rectangular and box-shaped objects dominate the classic discourse of theoretic investigations, a fascinating frontier lies in packing more complex shapes. Given recent insights that convex polygons do not allow for constant competitive online algorithms for diverse variants under translation, we study orthogonal polygons, in particular of small complexity. For translational packings of orthogonal 6-gons, we show that the competitive ratio of any online algorithm that aims to pack the items into a minimal number of unit bins is in Ω(n/(log n)), where n denotes the number of objects. In contrast, we show that constant competitive algorithms exist when the orthogonal 6-gons are symmetric or small. For (orthogonally convex) orthogonal 8-gons, we show that the trivial n-competitive algorithm, which places each item in its own bin, is best-possible, i.e., every online algorithm has an asymptotic competitive ratio of at least n. This implies that for general orthogonal polygons, the trivial algorithm is best possible. Interestingly, for packing degenerate orthogonal polygons (with thickness 0), called skeletons, the change in complexity is even more drastic. While constant competitive algorithms for 6-skeletons exist, no online algorithm for 8-skeletons achieves a competitive ratio better than n. For other packing variants of orthogonal 6-gons under translation, our insights imply the following consequences. The asymptotic competitive ratio of any online algorithm is in Ω(n/(log n)) for strip packing, and there exist online algorithms with competitive ratios in O(1) for perimeter packing, or in O(√n) for minimizing the area of the bounding box. Moreover, the critical packing density is positive (if every object individually fits into the interior of a unit bin).
Cite as

Tim Gerlach, Benjamin Hennies, and Linda Kleist. Online Packing of Orthogonal Polygons. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 52:1-52:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gerlach_et_al:LIPIcs.SoCG.2026.52,
  author =	{Gerlach, Tim and Hennies, Benjamin and Kleist, Linda},
  title =	{{Online Packing of Orthogonal Polygons}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{52:1--52:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.52},
  URN =		{urn:nbn:de:0030-drops-258589},
  doi =		{10.4230/LIPIcs.SoCG.2026.52},
  annote =	{Keywords: Packing, orthogonal polygon, algorithm, offline, online, competitive ratio, bin packing, strip packing, perimeter packing, critical density, 6-gon, 8-gon, L-shape, Z-shape, skeleton}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.47
Time Lower Bounds for the Metropolis Process and Simulated Annealing

Authors: Zongchen Chen, Dan Mikulincer, Daniel Reichman, and Alexander S. Wein

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
The Metropolis process (MP) and Simulated Annealing (SA) are stochastic local search heuristics that are often used in solving combinatorial optimization problems. Despite significant interest, there are very few theoretical results regarding the quality of approximation obtained by MP and SA (with polynomially many iterations) for NP-hard optimization problems. We provide rigorous lower bounds for MP and SA with respect to the classical maximum independent set problem when the algorithms are initialized from the empty set. We establish the existence of a family of graphs for which both MP and SA fail to find approximate solutions in polynomial time. More specifically, we show that for any ε ∈ (0,1) there are n-vertex graphs for which the probability SA (when limited to polynomially many iterations) will approximate the optimal solution within ratio Ω(1/n^{1-ε}) is exponentially small. Our lower bounds extend to graphs of constant average degree d, illustrating the failure of MP to achieve an approximation ratio of Ω(log(d)/d) in polynomial time. In some cases, our lower bounds apply even when the temperature is chosen adaptively. Finally, we prove exponential-time lower bounds when the inputs to these algorithms are bipartite graphs, and even trees, which are known to admit polynomial-time algorithms for the independent set problem.
Cite as

Zongchen Chen, Dan Mikulincer, Daniel Reichman, and Alexander S. Wein. Time Lower Bounds for the Metropolis Process and Simulated Annealing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 47:1-47:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.APPROX/RANDOM.2025.47,
  author =	{Chen, Zongchen and Mikulincer, Dan and Reichman, Daniel and Wein, Alexander S.},
  title =	{{Time Lower Bounds for the Metropolis Process and Simulated Annealing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{47:1--47:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.47},
  URN =		{urn:nbn:de:0030-drops-244138},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.47},
  annote =	{Keywords: Metropolis Process, Simulated Annealing, Independent Set}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.10
Improved Approximation Guarantees for Advertisement Placement

Authors: Waldo Gálvez, Roberto Oliva, and Victor Verdugo

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
The advertisement placement problem involves selecting and scheduling ads within a timeline that has capacity constraints to maximize profit. Each task is characterized by its height, width, and profit, and must be fully scheduled across multiple time slots. This problem models practical scenarios such as internet advertising and energy management, and it also generalizes classical combinatorial optimization problems like the knapsack and bin packing problems. We present a simple (2+ε)-approximation algorithm for any ε > 0, which improves upon the state-of-the-art 3+ε factor established by Freund and Naor twenty years ago. Our approach combines rounding techniques with dynamic programming and an efficient extension of list scheduling. Furthermore, we enhance this method with linear programming techniques to provide an almost optimal (1+ε)-approximation algorithm under resource augmentation, which allows for a slight increase in time slot capacities.
Cite as

Waldo Gálvez, Roberto Oliva, and Victor Verdugo. Improved Approximation Guarantees for Advertisement Placement. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{galvez_et_al:LIPIcs.APPROX/RANDOM.2025.10,
  author =	{G\'{a}lvez, Waldo and Oliva, Roberto and Verdugo, Victor},
  title =	{{Improved Approximation Guarantees for Advertisement Placement}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.10},
  URN =		{urn:nbn:de:0030-drops-243762},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.10},
  annote =	{Keywords: Advertisement Placement, Two-dimensional Packing, Geometric Knapsack, Resource Allocation}
}
Document
DOI: 10.4230/LIPIcs.CP.2025.7
Optimizing 2D Cutting: A Bin Packing Approach to Minimize Scraps and Maximize Their Reusability

Authors: Manuel Chastenay, Xavier Zwingmann, Claude-Guy Quimper, and Jonathan Gaudreault

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract
In industrial settings, cutting predefined pieces from one or multiple sheets of material is a common optimization challenge. This problem can be formulated as a variant of the 2D bin packing problem, where the edges of the pieces define the cut lines. This paper presents a constraint programming model developed in collaboration with an industrial partner in construction to minimize scrap waste generated when cutting insulation pieces. The model introduces an objective function designed to maximize the reusability of leftover material. To fully leverage the model’s efficiency, an initial process transforms irregular insulation pieces into rectangles using one of four processing methods. A comparative analysis is conducted to evaluate the impact of these methods, as well as to benchmark the model’s results against the partner’s manual approach.
Cite as

Manuel Chastenay, Xavier Zwingmann, Claude-Guy Quimper, and Jonathan Gaudreault. Optimizing 2D Cutting: A Bin Packing Approach to Minimize Scraps and Maximize Their Reusability. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chastenay_et_al:LIPIcs.CP.2025.7,
  author =	{Chastenay, Manuel and Zwingmann, Xavier and Quimper, Claude-Guy and Gaudreault, Jonathan},
  title =	{{Optimizing 2D Cutting: A Bin Packing Approach to Minimize Scraps and Maximize Their Reusability}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.7},
  URN =		{urn:nbn:de:0030-drops-238685},
  doi =		{10.4230/LIPIcs.CP.2025.7},
  annote =	{Keywords: Combinatorial optimization, constraint programming, 2D bin packing}
}
Artifact
Software
DOI: 10.4230/artifacts.23824
hannahtro/Loopless_Fluxes_with_Mixed_Integer_Optimization

Authors: Hannah Troppens, Mathieu Besançon, St. Elmo Wilken, and Sebastian Pokutta

Abstract
Cite as

Hannah Troppens, Mathieu Besançon, St. Elmo Wilken, Sebastian Pokutta. hannahtro/Loopless_Fluxes_with_Mixed_Integer_Optimization (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23824,
   title = {{hannahtro/Loopless\underlineFluxes\underlinewith\underlineMixed\underlineInteger\underlineOptimization}}, 
   author = {Troppens, Hannah and Besan\c{c}on, Mathieu and Wilken, St. Elmo and Pokutta, Sebastian},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:9c41495c7f2ecd9e7459fa0c51d4be32fa0c033e}{\texttt{swh:1:dir:9c41495c7f2ecd9e7459fa0c51d4be32fa0c033e}} (visited on 2025-07-15)},
   url = {https://github.com/hannahtro/Loopless_Fluxes_with_Mixed_Integer_Optimization},
   doi = {10.4230/artifacts.23824},
}
Document
DOI: 10.4230/LIPIcs.SEA.2025.26
Mixed-Integer Optimization for Loopless Flux Distributions in Metabolic Networks

Authors: Hannah Troppens, Mathieu Besançon, St. Elmo Wilken, and Sebastian Pokutta

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract
Constraint-based metabolic models can be used to investigate the intracellular physiology of microorganisms. These models couple genes to reactions, and typically seek to predict metabolite fluxes that optimize some biologically important metric. Classical techniques, like Flux Balance Analysis (FBA), formulate the metabolism of a microbe as an optimization problem where growth rate is maximized. While FBA has found widespread use, it often leads to thermodynamically infeasible solutions that contain internal cycles (loops). To address this shortcoming, Loopless-Flux Balance Analysis (ll-FBA) seeks to predict flux distributions that do not contain these loops. ll-FBA is a disjunctive program, usually reformulated as a mixed-integer program, and is challenging to solve for biological models that often contain thousands of reactions and metabolites. In this paper, we compare various reformulations of ll-FBA and different solution approaches. Overall, the combinatorial Benders' decomposition is the most promising of the tested approaches with which we could solve most instances. However, the model size and numerical instability pose a challenge to the combinatorial Benders' method.
Cite as

Hannah Troppens, Mathieu Besançon, St. Elmo Wilken, and Sebastian Pokutta. Mixed-Integer Optimization for Loopless Flux Distributions in Metabolic Networks. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{troppens_et_al:LIPIcs.SEA.2025.26,
  author =	{Troppens, Hannah and Besan\c{c}on, Mathieu and Wilken, St. Elmo and Pokutta, Sebastian},
  title =	{{Mixed-Integer Optimization for Loopless Flux Distributions in Metabolic Networks}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.26},
  URN =		{urn:nbn:de:0030-drops-232646},
  doi =		{10.4230/LIPIcs.SEA.2025.26},
  annote =	{Keywords: Systems biology, mixed-integer optimization, disjunctive optimization, flux balance analysis}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.104
Improved Approximation Algorithms for Three-Dimensional Bin Packing

Authors: Debajyoti Kar, Arindam Khan, and Malin Rau

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study three fundamental three-dimensional (3D) geometric packing problems: 3D (Geometric) Bin Packing (3D-BP), 3D Strip Packing (3D-SP), and Minimum Volume Bounding Box (3D-MVBB), where given a set of 3D (rectangular) cuboids, the goal is to find an axis-aligned nonoverlapping packing of all cuboids. In 3D-BP, we need to pack the given cuboids into the minimum number of unit cube bins. In 3D-SP, we need to pack them into a 3D cuboid with a unit square base and minimum height. Finally, in 3D-MVBB, the goal is to pack into a cuboid box of minimum volume. It is NP-hard to even decide whether a set of rectangles can be packed into a unit square bin - giving an (absolute) approximation hardness of 2 for 3D-BP and 3D-SP. The previous best (absolute) approximation for all three problems is by Li and Cheng (SICOMP, 1990), who gave algorithms with approximation ratios of 13, 46/7, and 46/7+ε, respectively, for 3D-BP, 3D-SP, and 3D-MVBB. We provide improved approximation ratios of 6, 6, and 3+ε, respectively, for the three problems, for any constant ε > 0. For 3D-BP, in the asymptotic regime, Bansal, Correa, Kenyon, and Sviridenko (Math. Oper. Res., 2006) showed that there is no asymptotic polynomial-time approximation scheme (APTAS) even when all items have the same height. Caprara (Math. Oper. Res., 2008) gave an asymptotic approximation ratio of T_{∞}² + ε ≈ 2.86, where T_{∞} is the well-known Harmonic constant in Bin Packing. We provide an algorithm with an improved asymptotic approximation ratio of 3 T_{∞}/2 + ε ≈ 2.54. Further, we show that unlike 3D-BP (and 3D-SP), 3D-MVBB admits an APTAS.
Cite as

Debajyoti Kar, Arindam Khan, and Malin Rau. Improved Approximation Algorithms for Three-Dimensional Bin Packing. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 104:1-104:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kar_et_al:LIPIcs.ICALP.2025.104,
  author =	{Kar, Debajyoti and Khan, Arindam and Rau, Malin},
  title =	{{Improved Approximation Algorithms for Three-Dimensional Bin Packing}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{104:1--104:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.104},
  URN =		{urn:nbn:de:0030-drops-234814},
  doi =		{10.4230/LIPIcs.ICALP.2025.104},
  annote =	{Keywords: Approximation Algorithms, Geometric Packing, Multidimensional Packing}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.60
Improved Approximation Algorithms for Three-Dimensional Knapsack

Authors: Klaus Jansen, Debajyoti Kar, Arindam Khan, K. V. N. Sreenivas, and Malte Tutas

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We study the three-dimensional Knapsack (3DK) problem, in which we are given a set of axis-aligned cuboids with associated profits and an axis-aligned cube knapsack. The objective is to find a non-overlapping axis-aligned packing (by translation) of the maximum profit subset of cuboids into the cube. The previous best approximation algorithm is due to Diedrich, Harren, Jansen, Thöle, and Thomas (2008), who gave a (7+ε)-approximation algorithm for 3DK and a (5+ε)-approximation algorithm for the variant when the items can be rotated by 90 degrees around any axis, for any constant ε > 0. Chlebík and Chlebíková (2009) showed that the problem does not admit an asymptotic polynomial-time approximation scheme. We provide an improved polynomial-time (139/29+ε) ≈ 4.794-approximation algorithm for 3DK and (30/7+ε) ≈ 4.286-approximation when rotations by 90 degrees are allowed. We also provide improved approximation algorithms for several variants such as the cardinality case (when all items have the same profit) and uniform profit-density case (when the profit of an item is equal to its volume). Our key technical contribution is container packing - a structured packing in 3D such that all items are assigned into a constant number of containers, and each container is packed using a specific strategy based on its type. We first show the existence of highly profitable container packings. Thereafter, we show that one can find near-optimal container packing efficiently using a variant of the Generalized Assignment Problem (GAP).
Cite as

Klaus Jansen, Debajyoti Kar, Arindam Khan, K. V. N. Sreenivas, and Malte Tutas. Improved Approximation Algorithms for Three-Dimensional Knapsack. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 60:1-60:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.SoCG.2025.60,
  author =	{Jansen, Klaus and Kar, Debajyoti and Khan, Arindam and Sreenivas, K. V. N. and Tutas, Malte},
  title =	{{Improved Approximation Algorithms for Three-Dimensional Knapsack}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{60:1--60:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.60},
  URN =		{urn:nbn:de:0030-drops-232126},
  doi =		{10.4230/LIPIcs.SoCG.2025.60},
  annote =	{Keywords: Approximation Algorithms, Hyperrectangle Packing, Multidimensional Knapsack, Three-dimensional Packing}
}
Document
DOI: 10.4230/LIPIcs.SEA.2024.16
Solving the Optimal Experiment Design Problem with Mixed-Integer Convex Methods

Authors: Deborah Hendrych, Mathieu Besançon, and Sebastian Pokutta

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
We tackle the Optimal Experiment Design Problem, which consists of choosing experiments to run or observations to select from a finite set to estimate the parameters of a system. The objective is to maximize some measure of information gained about the system from the observations, leading to a convex integer optimization problem. We leverage Boscia.jl, a recent algorithmic framework, which is based on a nonlinear branch-and-bound algorithm with node relaxations solved to approximate optimality using Frank-Wolfe algorithms. One particular advantage of the method is its efficient utilization of the polytope formed by the original constraints which is preserved by the method, unlike alternative methods relying on epigraph-based formulations. We assess our method against both generic and specialized convex mixed-integer approaches. Computational results highlight the performance of our proposed method, especially on large and challenging instances.
Cite as

Deborah Hendrych, Mathieu Besançon, and Sebastian Pokutta. Solving the Optimal Experiment Design Problem with Mixed-Integer Convex Methods. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 16:1-16:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hendrych_et_al:LIPIcs.SEA.2024.16,
  author =	{Hendrych, Deborah and Besan\c{c}on, Mathieu and Pokutta, Sebastian},
  title =	{{Solving the Optimal Experiment Design Problem with Mixed-Integer Convex Methods}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{16:1--16:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.16},
  URN =		{urn:nbn:de:0030-drops-203810},
  doi =		{10.4230/LIPIcs.SEA.2024.16},
  annote =	{Keywords: Mixed-Integer Non-Linear Optimization, Optimal Experiment Design, Frank-Wolfe, Boscia}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.20
Resource Sharing Revisited: Local Weak Duality and Optimal Convergence

Authors: Daniel Blankenburg

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We revisit the (block-angular) min-max resource sharing problem, which is a well-known generalization of fractional packing and the maximum concurrent flow problem. It consists of finding an 𝓁_∞-minimal element in a Minkowski sum 𝒳 = ∑_{C ∈ 𝒞} X_C of non-empty closed convex sets X_C ⊆ ℝ^ℛ_{≥ 0}, where 𝒞 and ℛ are finite sets. We assume that an oracle for approximate linear minimization over X_C is given. We improve on the currently fastest known FPTAS in various ways. A major novelty of our analysis is the concept of local weak duality, which illustrates that the algorithm optimizes (close to) independent parts of the instance separately. Interestingly, this implies that the computed solution is not only approximately 𝓁_{∞}-minimal, but among such solutions, also its second-highest entry is approximately minimal. Based on a result by Klein and Young [Klein and Young, 2015], we provide a lower bound of Ω((𝒞|+|ℛ|)/δ² log |ℛ|) required oracle calls for a natural class of algorithms. Our FPTAS is optimal within this class - its running time matches the lower bound precisely, and thus improves on the previously best-known running time for the primal as well as the dual problem.
Cite as

Daniel Blankenburg. Resource Sharing Revisited: Local Weak Duality and Optimal Convergence. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{blankenburg:LIPIcs.ESA.2022.20,
  author =	{Blankenburg, Daniel},
  title =	{{Resource Sharing Revisited: Local Weak Duality and Optimal Convergence}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.20},
  URN =		{urn:nbn:de:0030-drops-169582},
  doi =		{10.4230/LIPIcs.ESA.2022.20},
  annote =	{Keywords: Resource sharing, Dantzig-Wolfe-type algorithms, Decreasing minimization}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.52
An Algorithm-Independent Measure of Progress for Linear Constraint Propagation

Authors: Boro Sofranac, Ambros Gleixner, and Sebastian Pokutta

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract
Propagation of linear constraints has become a crucial sub-routine in modern Mixed-Integer Programming (MIP) solvers. In practice, iterative algorithms with tolerance-based stopping criteria are used to avoid problems with slow or infinite convergence. However, these heuristic stopping criteria can pose difficulties for fairly comparing the efficiency of different implementations of iterative propagation algorithms in a real-world setting. Most significantly, the presence of unbounded variable domains in the problem formulation makes it difficult to quantify the relative size of reductions performed on them. In this work, we develop a method to measure - independently of the algorithmic design - the progress that a given iterative propagation procedure has made at a given point in time during its execution. Our measure makes it possible to study and better compare the behavior of bounds propagation algorithms for linear constraints. We apply the new measure to answer two questions of practical relevance: (i) We investigate to what extent heuristic stopping criteria can lead to premature termination on real-world MIP instances. (ii) We compare a GPU-parallel propagation algorithm against a sequential state-of-the-art implementation and show that the parallel version is even more competitive in a real-world setting than originally reported.
Cite as

Boro Sofranac, Ambros Gleixner, and Sebastian Pokutta. An Algorithm-Independent Measure of Progress for Linear Constraint Propagation. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 52:1-52:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sofranac_et_al:LIPIcs.CP.2021.52,
  author =	{Sofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian},
  title =	{{An Algorithm-Independent Measure of Progress for Linear Constraint Propagation}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{52:1--52:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.52},
  URN =		{urn:nbn:de:0030-drops-153430},
  doi =		{10.4230/LIPIcs.CP.2021.52},
  annote =	{Keywords: Bounds Propagation, Mixed Integer Programming}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.515
Average Case Polyhedral Complexity of the Maximum Stable Set Problem

Authors: Gábor Braun, Samuel Fiorini, and Sebastian Pokutta

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
We study the minimum number of constraints needed to formulate random instances of the maximum stable set problem via LPs (more precisely, linear extended formulations), in two distinct models. In the uniform model, the constraints of the LP are not allowed to depend on the input graph, which should be encoded solely in the objective function. There we prove a super-polynomial lower bound with overwhelming probability for every LP that is exact for a randomly selected set of instances with a natural distribution. In the non-uniform model, the constraints of the LP may depend on the input graph, but we allow weights on the vertices. The input graph is sampled according to the Erdös-Renyi model. There we obtain upper and lower bounds holding with high probability for various ranges of p. We obtain a super-polynomial lower bound all the way from essentially p = polylog(n) / n to p = 1 / log n. Our upper bound is close as there is only an essentially quadratic gap in the exponent, which also exists in the worst case model. Finally, we state a conjecture to close the gap both in the average-case and worst-case models.
Cite as

Gábor Braun, Samuel Fiorini, and Sebastian Pokutta. Average Case Polyhedral Complexity of the Maximum Stable Set Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 515-530, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{braun_et_al:LIPIcs.APPROX-RANDOM.2014.515,
  author =	{Braun, G\'{a}bor and Fiorini, Samuel and Pokutta, Sebastian},
  title =	{{Average Case Polyhedral Complexity of the Maximum Stable Set Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{515--530},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.515},
  URN =		{urn:nbn:de:0030-drops-47201},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.515},
  annote =	{Keywords: polyhedral approximation, extended formulation, stable sets}
}
  • Refine by Type
  • 11 Document/PDF
  • 6 Document/HTML
  • 1 Artifact

  • Refine by Publication Year
  • 1 2026
  • 7 2025
  • 1 2024
  • 1 2022
  • 1 2021
  • Show More...

  • Refine by Author
  • 5 Pokutta, Sebastian
  • 3 Besançon, Mathieu
  • 2 Kar, Debajyoti
  • 2 Khan, Arindam
  • 2 Troppens, Hannah
  • Show More...

  • Refine by Series/Journal
  • 11 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Packing and covering problems
  • 1 Applied computing → Biological networks
  • 1 Applied computing → Operations research
  • 1 Mathematics of computing → Mathematical optimization
  • Show More...

  • Refine by Keyword
  • 2 Approximation Algorithms
  • 1 2D bin packing
  • 1 6-gon
  • 1 8-gon
  • 1 Advertisement Placement
  • Show More...

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