Fine-grained equivalence for problems related to integer linear programming

DOI10.4230/LIPICS.ITCS.2025.83MaRDI QIDQ7296730zbMATH OpenFDO

Authors Lars Rohwedder, Karol Węgrzycki

Publication date 14 July 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2025.83

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Combinatorial \(n\)-fold integer programming and applications
• Faster algorithms for bounded knapsack and bounded subset sum via fine-grained proximity results
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 7788439 (Why is no real title available?)
• Integer Programming with a Fixed Number of Variables
• Knapsack and subset sum with small items
• Minkowski's Convex Body Theorem and Integer Programming
• On Integer Programming, Discrepancy, and Convolution
• On problems as hard as CNF-SAT
• On the complexity of integer programming
• Optimizing low dimensional functions over the integers
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• Sensitivity, proximity and FPT algorithms for exact matroid problems
• SETH-based Lower Bounds for Subset Sum and Bicriteria Path
• The subspace flatness conjecture and faster integer programming
• Tight complexity lower bounds for integer linear programming with few constraints
• Tight hardness results for minimizing discrepancy
• Tight lower bounds for block-structured integer programs

Cited in

(1)

• Convolution and knapsack in higher dimensions

This page was built for publication: Fine-grained equivalence for problems related to integer linear programming

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