Tight lower bounds for block-structured integer programs

Area of Science:

• Theoretical Computer Science
• Operations Research
• Discrete Mathematics

Background:

• Studies fundamental block-structured integer programs (IPs): tree-fold and multi-stage IPs.
• These IPs exhibit a recursive pattern in their constraint matrices, with tree-fold IPs being transposes of multi-stage IPs.
• Current algorithms for solving these IPs possess a significant exponential time gap.

Purpose of the Study:

• To determine if the exponential time gap in solving tree-fold and multi-stage IPs is inherent.
• To establish theoretical limits on the efficiency of algorithms for these specific IP structures.
• To investigate the fundamental building blocks of existing algorithms, such as Graver basis elements.

Main Methods:

• Proving lower bounds based on the Exponential Time Hypothesis (ETH).
• Analyzing the structure of constraint matrices for tree-fold and multi-stage IPs.
• Establishing unconditional lower bounds on the size of Graver basis elements.

Main Results:

• Demonstrated that the exponential time gap in solving these IPs is necessary, assuming the ETH.
• Established that current state-of-the-art algorithms are essentially optimal in terms of their exponential running time.
• Proved unconditional lower bounds on the size of Graver basis elements, indicating limitations for current algorithmic approaches.

Conclusions:

• The exponential time complexity for solving tree-fold and multi-stage integer programs is inherent and cannot be fundamentally improved.
• Existing algorithms are close to optimal, and significant breakthroughs in polynomial time are unlikely under standard complexity assumptions.
• Future improvements to algorithms solving these IPs are constrained by the established lower bounds on Graver basis elements.