DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2026.20

Approximation Algorithms for Integer Programming with Resource Augmentation

Authors: Hauke Brinkop, Hua Chen, Lin Chen, Klaus Jansen, and Guochuan Zhang

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

Solving a general integer program (IP) is NP-hard. The classic algorithm [Papadimitriou, J.ACM '81] for IPs has a running time n^{{𝒪}(m)}(m⋅max{Δ,‖b‖_{∞}})^{{𝒪}(m²)}, where m is the number of constraints, n is the number of variables, and Δ and ‖b‖_{∞} are, respectively, the largest absolute values among the entries in the constraint matrix and the right-hand side vector of the constraint. The running time is exponential in m, and becomes pseudo-polynomial if m is a constant. In recent years, there has been extensive research on FPT (fixed parameter tractable) algorithms for the so-called n-fold IPs, which may possess a large number of constraints, but the constraint matrix satisfies a specific block structure. It is remarkable that these FPT algorithms take as parameters Δ and the number of rows and columns of some small submatrices. If Δ is not treated as a parameter, then the running time becomes pseudo-polynomial even if all the other parameters are taken as constants. This paper explores the trade-off between time and accuracy in solving an IP. We show that, for arbitrary small ε > 0, there exists an algorithm for IPs with m constraints that runs in {f(m,ε)}⋅poly(|I|) time, and returns a near-feasible solution that violates the constraints by at most εΔ. Furthermore, for n-fold IPs, we establish a similar result - our algorithm runs in time that depends on the number of rows and columns of small submatrices together with 1/ε, and returns a solution that slightly violates the constraints. Meanwhile, both solutions guarantee that their objective values are no worse than the corresponding optimal objective values satisfying the constraints. As applications, our results can be used to obtain additive approximation schemes for multidimensional knapsack as well as scheduling.

Cite as

Hauke Brinkop, Hua Chen, Lin Chen, Klaus Jansen, and Guochuan Zhang. Approximation Algorithms for Integer Programming with Resource Augmentation. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brinkop_et_al:LIPIcs.STACS.2026.20,
  author =	{Brinkop, Hauke and Chen, Hua and Chen, Lin and Jansen, Klaus and Zhang, Guochuan},
  title =	{{Approximation Algorithms for Integer Programming with Resource Augmentation}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.20},
  URN =		{urn:nbn:de:0030-drops-255090},
  doi =		{10.4230/LIPIcs.STACS.2026.20},
  annote =	{Keywords: Approximation algorithms, Resource augmentation, Integer programs, n-fold IPs}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2023.13

New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines

Authors: Sebastian Berndt, Hauke Brinkop, Klaus Jansen, Matthias Mnich, and Tobias Stamm

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract

Mixed-integer linear programming (MILP) is at the core of many advanced algorithms for solving fundamental problems in combinatorial optimization. The complexity of solving MILPs directly correlates with their support size, which is the minimum number of non-zero integer variables in an optimal solution. A hallmark result by Eisenbrand and Shmonin (Oper. Res. Lett. , 2006) shows that any feasible integer linear program (ILP) has a solution with support size s ≤ 2m⋅log(4mΔ), where m is the number of constraints, and Δ is the largest absolute coefficient in any constraint. Our main combinatorial result are improved support size bounds for ILPs. We show that any ILP has a solution with support size s ≤ m⋅(log(3A_max)+√{log(A_max)}), where A_max≔ ‖A‖₁ denotes the 1-norm of the constraint matrix A. Furthermore, we show support bounds in the linearized form s ≤ 2m⋅log(1.46 A_max). Our upper bounds also hold with A_max replaced by √mΔ, which improves on the previously best constants in the linearized form. Our main algorithmic result are the fastest known approximation schemes for fundamental scheduling problems, which use the improved support bounds as one ingredient. We design an efficient approximation scheme (EPTAS) for makespan minimization on uniformly related machines (Q||C_{max}). Our EPTAS yields a (1+ε)-approximation for Q||C_{max} on N jobs in time 2^𝒪(1/ε log³(1/ε)log(log(1/ε))) + 𝒪(N), which improves over the previously fastest algorithm by Jansen, Klein and Verschae (Math. Oper. Res., 2020) with run time 2^𝒪(1/ε log⁴(1/ε)) + N^𝒪(1). Arguably, our approximation scheme is also simpler than all previous EPTASes for Q||C_max, as we reduce the problem to a novel MILP formulation which greatly benefits from the small support.

Cite as

Sebastian Berndt, Hauke Brinkop, Klaus Jansen, Matthias Mnich, and Tobias Stamm. New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{berndt_et_al:LIPIcs.ISAAC.2023.13,
  author =	{Berndt, Sebastian and Brinkop, Hauke and Jansen, Klaus and Mnich, Matthias and Stamm, Tobias},
  title =	{{New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.13},
  URN =		{urn:nbn:de:0030-drops-193155},
  doi =		{10.4230/LIPIcs.ISAAC.2023.13},
  annote =	{Keywords: Integer programming, scheduling algorithms, uniformly related machines, makespan minimization}
}

Search Results

Documents authored by Brinkop, Hauke

Approximation Algorithms for Integer Programming with Resource Augmentation

Abstract

Cite as

New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines

Abstract

Cite as

Thanks for your feedback!

Could not send message