Servicenavigation

Project Details

Back

Projekt Print View

Structural results and their application in scheduling and packing problems

Subject Area Theoretical Computer Science
Term from 2017 to 2022
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 335406402
 
Final Report Year 2022

Final Report Abstract

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.

Publications

 
 

Additional Information

© 2026 DFG Disclaimer / Copyright / Privacy Policy

Textvergrößerung und Kontrastanpassung