Tight complexity lower bounds for integer linear programming with few constraints

DOI10.4230/LIPICS.STACS.2019.44MaRDI QIDQ5090494zbMATH OpenFDO

Authors Dušan Knop, Michał Pilipczuk, Marcin Wrochna

Publication date 18 July 2022

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

zbMATH Keywords

ETHfixed-parameter tractabilityinteger linear programming

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Integer programming (90C10)

Recommendations

• Tight complexity lower bounds for integer linear programming with few constraints
• On the optimality of pseudo-polynomial algorithms for integer programming
• Integer programming and incidence treedepth
• On polynomial kernels for sparse integer linear programs
• On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility

Cites work

• \(n\)-fold integer programming in cubic time
• A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
• A simplified NP-complete satisfiability problem
• Algebraic and geometric ideas in the theory of discrete optimization
• An application of simultaneous diophantine approximation in combinatorial optimization
• Combinatorial \(n\)-fold integer programming and applications
• Covering a tree with rooted subtrees -- parameterized and approximation algorithms
• Determination of a Subset from Certain Combinatorial Properties
• Empowering the configuration-IP -- new PTAS results for scheduling with setups times
• Faster Algorithms for Integer Programs with Block Structure
• Finiteness theorems in stochastic integer programming
• scientific article; zbMATH DE number 6850361 (Why is no real title available?)
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming
• On a Combinatorial Problem in Number Theory
• On integer programming and convolution
• On the complexity of k-SAT
• On the complexity of integer programming
• On the optimality of pseudo-polynomial algorithms for integer programming
• Optimal reconstruction of graphs under the additive model
• Parameterized algorithms
• Scheduling meets n-fold integer programming
• SETH-based lower bounds for subset sum and bicriteria path
• Sparsity. Graphs, structures, and algorithms
• Tight lower bounds for the complexity of multicoloring
• Voting and bribing in single-exponential time
• Which problems have strongly exponential complexity?

Cited in

(17)

• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• The complexity landscape of decompositional parameters for ILP
• On some FPT problems without polynomial Turing compressions
• On the decision tree complexity of threshold functions
• The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
• Integer programming and incidence treedepth
• On the optimality of pseudo-polynomial algorithms for integer programming
• On polynomial kernels for sparse integer linear programs
• On the optimality of pseudo-polynomial algorithms for integer programming
• About the Complexity of Two-Stage Stochastic IPs
• On the Decision Tree Complexity of Threshold Functions
• Tight complexity lower bounds for integer linear programming with few constraints
• Integer programming in an algebraic computation model
• Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming
• The double exponential runtime is tight for 2-stage stochastic ILPs
• On Integer Programming, Discrepancy, and Convolution
• Faster algorithms for sparse ILP and hypergraph multi-packing/multi-cover problems

This page was built for publication: Tight complexity lower bounds for integer linear programming with few constraints

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