On Integer Programming, Discrepancy, and Convolution

DOI10.1287/MOOR.2022.1308MaRDI QIDQ6121635zbMATH OpenOpenAlexWikidataFDO

Authors Klaus Jansen, Lars Rohwedder

Publication date 27 February 2024

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.04744

zbMATH Keywords

dynamic programmingfine-grained complexityfixed-parameter tractable

Mathematics Subject Classification ID

Integer programming (90C10)

Abstract: Integer programs with m constraints are solvable in pseudo-polynomial time in $Delta$, the largest coefficient in a constraint, when m is a fixed constant. We give a new algorithm with a running time of $O(sqrtmDelta{)}^{2m}+O(nm)$, which improves on the state-of-the-art. Moreover, we show that improving on our algorithm for any $m$ is equivalent to improving over the quadratic time algorithm for $(min,+)$-convolution. This is a strong evidence that our algorithm's running time is the best possible. We also present a specialized algorithm with running time $O(sqrtmDelta{)}^{(1+o(1))m}+O(nm)$ for testing feasibility of an integer program and also give a tight lower bound, which is based on the SETH in this case.

Recommendations

• On integer programming and convolution
• Fast integer programming in fixed dimension
• On the optimality of pseudo-polynomial algorithms for integer programming
• Tight complexity lower bounds for integer linear programming with few constraints
• Tight complexity lower bounds for integer linear programming with few constraints

Cited in

(8)

• Robust scheduling on uniform machines. New results using a relaxed approximation guarantee
• Minimizing tardy processing time on a single machine in near-linear time
• Space-efficient algorithm for integer programming with few constraints
• Minimizing tardy processing time on a single machine in near-linear time
• Approximation results on resource leveling problems
• Integer points in the degree-sequence polytope
• Parameterized complexity of coupon coloring of graphs
• Separable convex mixed-integer optimization: improved algorithms and lower bounds

This page was built for publication: On Integer Programming, Discrepancy, and Convolution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6121635)