On polynomial kernels for sparse integer linear programs
From MaRDI portal
Publication:269481
DOI10.1016/j.jcss.2015.12.002zbMath1338.68111OpenAlexW1586971062MaRDI QIDQ269481
Publication date: 18 April 2016
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2015.12.002
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (3)
Parameterized complexity of sparse linear complementarity problems ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Infeasibility of instance compression and succinct PCPs for NP
- Integer-programming software systems
- On problems without polynomial kernels
- On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility
- Kernelization – Preprocessing with a Guarantee
- On Kernels for Covering and Packing ILPs with Small Coefficients
- Integer Programming with a Fixed Number of Variables
- On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
- Parametric Integer Programming in Fixed Dimension
- 50 Years of Integer Programming 1958-2008
- Linear Programming in Linear Time When the Dimension Is Fixed
- Minkowski's Convex Body Theorem and Integer Programming
- A Polynomial Algorithm for the Two-Variable Integer Programming Problem
- Las Vegas algorithms for linear and integer programming when the dimension is small
- Kernelization Lower Bounds Through Colors and IDs
- Kernelization Lower Bounds by Cross-Composition
- Representative Sets and Irrelevant Vertices
- (Meta) Kernelization
- Bidimensionality and Geometric Graphs
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
- Algorithms - ESA 2003
- Efficient algorithms for integer programs with two variables per constraint.
This page was built for publication: On polynomial kernels for sparse integer linear programs
