Strukturaussagen und deren Anwendung in Scheduling- und Packungsprobleme

• Antragsteller: Professor Dr. Klaus Jansen
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2017 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 335406402

• Erstellungsjahr: 2022

Zusammenfassung der Projektergebnisse

Integer Linear Programs (ILPs) are an important tool not limited to but in particular in the area of scheduling and packing problems. They are defined as follows: Let m, n ∈ N. Formally, we are given a matrix A ∈ Zm×n , a right hand side b ∈ Zm and an objective vector c ∈ Zn . The corresponding problem, called Integer Linear Programming (ILP), is the defined as max { c x : Ax = b, x ∈ Zn } . ≥0 (1) In this project we have been able to improve the best result priorly known for solving ILPs parametrized by the largest absolute value ∆ of any occurring coefficient and m. Based on that improvement we have been able to develop the first practical implementation of an approximation scheme for scheduling on identical machines. For matrices A that are basically a block diagonal matrix with small blocks and a few additional rows, so called n-fold ILPs, we developed the first algorithm with a near-linear running time in the number of variables. For Two-Stage-Stochastic ILPs, that are ILPs where A is an n-fold ILP, we could show that the doubly exponential running time, that occurs in the best known algorithm for those ILPs, is necessary under a well-known complexity hypothesis, the Exponential Time Hypothesis (ETH). Note that this implies in particular that n-fold and Two-Stage-Stochastic ILPs are significantly different regarding their complexity, despite having the same structure up to transposition of the constraint matrix. Furthermore, we could show general structural results for ILPs, e.g. the necessary number of variables that are non-zero in a solution or the distance/difference of specific kinds of solutions. Those properties are used in algorithms, e.g. for solving ILPs. ILPs are often used as tools in the area of scheduling and packing problems for both, exact and approximative algorithms. We have been able to achieve a series of results in this area for a bunch of different problems by cleverly formulating ILPs such that it has some exploitable structure, e.g. is an n-fold ILP, and can hence be solved efficiently. As examples we want to mention Scheduling With Setup Times and Class Constraint Scheduling. For the former problem we could construct algorithms for some scenarios where such have not been known before or if, then with a worst approximation guarantee. For the latter problem we were able to improve the running time significantly and simultaneously get an algorithm that is well better suited for implementation than those priorly known.

Projektbezogene Publikationen (Auswahl)

• An EPTAS for Machine Scheduling with Bag-Constraints. The 31st ACM Symposium on Parallelism in Algorithms and Architectures, 135-144. ACM.
  Grage, Kilian; Jansen, Klaus & Klein, Kim-Manuel
  
• Near-Linear Approximation Algorithms for Scheduling Problems with Batch Setup Times. The 31st ACM Symposium on Parallelism in Algorithms and Architectures, 155-164. ACM.
  Deppert, Max A. & Jansen, Klaus
  
• Scheduling on (Un-)Related Machines with Setup Times. 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), 145-154. IEEE.
  Jansen, Klaus; Maack, Marten & Macker, Alexander
  
• Approximation Algorithms for Scheduling with Class Constraints. Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 349-357. ACM.
  Jansen, Klaus; Lassota, Alexandra & Maack, Marten
  
• Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding. SIAM Journal on Discrete Mathematics, 34(4), 2282-2299.
  Jansen, Klaus; Lassota, Alexandra & Rohwedder, Lars
  
• Empowering the configuration-IP: new PTAS results for scheduling with setup times. Mathematical Programming, 195(1-2), 367-401.
  Jansen, Klaus; Klein, Kim-Manuel; Maack, Marten & Rau, Malin
  
• New Bounds for the Vertices of the Integer Hull. Symposium on Simplicity in Algorithms (SOSA), 25-36. Society for Industrial and Applied Mathematics.
  Berndt, Sebastian; Jansen, Klaus & Klein, Kim-Manuel
  
• Load Balancing: The Long Road from Theory to Practice. 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), 104-116. Society for Industrial and Applied Mathematics.
  Berndt, Sebastian; Deppert, Max A.; Jansen, Klaus & Rohwedder, Lars
  
• On Integer Programming, Discrepancy, and Convolution. Mathematics of Operations Research, 48(3), 1481-1495.
  Jansen, Klaus & Rohwedder, Lars