On polynomial kernels for sparse integer linear programs
From MaRDI portal
Publication:269481
DOI10.1016/J.JCSS.2015.12.002zbMATH Open1338.68111OpenAlexW1586971062MaRDI QIDQ269481FDOQ269481
Authors: Stefan Kratsch 
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
Recommendations
- On polynomial kernels for sparse integer linear programs
- On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility
- On kernels for covering and packing ILPs with small coefficients
- A structural approach to kernels for ILPs: treewidth and total unimodularity
- Polynomial kernels for weighted problems
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Integer programming (90C10)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
- On problems without polynomial kernels
- Kernelization -- preprocessing with a guarantee
- Integer Programming with a Fixed Number of Variables
- 50 Years of Integer Programming 1958-2008
- Minkowski's Convex Body Theorem and Integer Programming
- Title not available (Why is that?)
- Title not available (Why is that?)
- Representative Sets and Irrelevant Vertices
- Parameterized algorithms
- On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility
- On kernels for covering and packing ILPs with small coefficients
- Parametric integer programming in fixed dimension
- Linear Programming in Linear Time When the Dimension Is Fixed
- 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
- (Meta) Kernelization
- Bidimensionality and kernels
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Fast integer programming in fixed dimension
- Efficient algorithms for integer programs with two variables per constraint.
- Infeasibility of instance compression and succinct PCPs for NP
- Integer-programming software systems
Cited In (7)
- A structural approach to kernels for ILPs: treewidth and total unimodularity
- Faster algorithms for sparse ILP and hypergraph multi-packing/multi-cover problems
- On kernels for covering and packing ILPs with small coefficients
- Title not available (Why is that?)
- Parameterized complexity of sparse linear complementarity problems
- On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility
- Combinatorial \(n\)-fold integer programming and applications
This page was built for publication: On polynomial kernels for sparse integer linear programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q269481)
