TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publications
  4. New support size bounds for integer programming, applied to makespan minimization on uniformly related machines
 
Options

New support size bounds for integer programming, applied to makespan minimization on uniformly related machines

Citation Link: https://doi.org/10.15480/882.8887
Publikationstyp
Conference Paper
Date Issued
2023
Sprache
English
Author(s)
Berndt, Sebastian  
Brinkop, Hauke  
Universität zu Kiel
Jansen, Klaus  
Universität zu Kiel
Mnich, Matthias  orcid-logo
Algorithmen und Komplexität E-11  
Stamm, Tobias  
Algorithmen und Komplexität E-11  
TORE-DOI
10.15480/882.8887
TORE-URI
https://hdl.handle.net/11420/44403
First published in
Leibniz international proceedings in informatics (LIPIcs)  
Number in series
283
Article Number
13
Citation
International Symposium on Algorithms and Computation (ISAAC 2023)
Contribution to Conference
34th International Symposium on Algorithms and Computation, ISAAC 2023  
Publisher DOI
10.4230/LIPIcs.ISAAC.2023.13
Scopus ID
2-s2.0-85179132772
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing
ISBN
978-3-95977-289-1
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∥_1 denotes the 1-norm of the constraint matrix A. Furthermore, we show support bounds in the linearized form s ≤ 2m · log(1.46A_{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||Cmax). Our EPTAS yields a (1 + ε)-approximation for Q||Cmax on N jobs in time 2^O(1/ε log3(1/ε) log(log(1/ε))) + O(N), which improves over the previously fastest algorithm by Jansen, Klein and Verschae (Math. Oper. Res., 2020) with run time 2^O(1/ε log4(1/ε)) + N^O(1). Arguably, our approximation scheme is also simpler than all previous EPTASes for Q||Cmax, as we reduce the problem to a novel MILP formulation which greatly benefits from the small support.
Subjects
Integer programming
makespan minimization
scheduling algorithms
uniformly related machines
DDC Class
004: Computer Sciences
Publication version
publishedVersion
Lizenz
https://creativecommons.org/licenses/by/4.0/
Loading...
Thumbnail Image
Name

LIPIcs.ISAAC.2023.13.pdf

Type

Main Article

Size

901.88 KB

Format

Adobe PDF

TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback