On polynomial kernels for sparse integer linear programs

<a class="pub-badge pub-badge--doi" href="https://doi.org/10.1016/J.JCSS.2015.12.002" rel="nofollow">DOI 10.1016/J.JCSS.2015.12.002</a><a class="pub-badge pub-badge--grey" href="https://zbmath.org/1338.68111" rel="nofollow">zbMATH</a><a class="pub-badge pub-badge--grey" href="https://openalex.org/works/W1586971062" rel="nofollow">OpenAlex</a><a class="pub-badge pub-badge--mardi" href="https://portal.mardi4nfdi.de/wiki/Item:Q269481" rel="nofollow">MaRDI QID Q269481</a><a class="pub-badge pub-badge--grey" href="https://fdo.portal.mardi4nfdi.de/fdo/Q269481" rel="nofollow">FDO</a>

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

zbMATH Keywords

parameterized complexityinteger linear programskernelization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Integer programming (90C10)

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

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1349588 (Why is no real title available?)
• (Meta) Kernelization
• 50 Years of Integer Programming 1958-2008
• A Polynomial Algorithm for the Two-Variable Integer Programming Problem
• Bidimensionality and kernels
• Efficient algorithms for integer programs with two variables per constraint.
• Fast integer programming in fixed dimension
• Infeasibility of instance compression and succinct PCPs for NP
• Integer Programming with a Fixed Number of Variables
• Integer-programming software systems
• Kernelization -- preprocessing with a guarantee
• Kernelization Lower Bounds by Cross-Composition
• Kernelization lower bounds through colors and IDs
• Las Vegas algorithms for linear and integer programming when the dimension is small
• Linear Programming in Linear Time When the Dimension Is Fixed
• Minkowski's Convex Body Theorem and Integer Programming
• On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility
• On kernels for covering and packing ILPs with small coefficients
• On problems without polynomial kernels
• On the compressibility of \(\mathcal{NP}\) instances and cryptographic applications
• Parameterized algorithms
• Parametric integer programming in fixed dimension
• Recent developments in kernelization: a survey
• Representative sets and irrelevant vertices: new tools for kernelization
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses

Cited in

(8)

• Combinatorial \(n\)-fold integer programming and applications
• Combinatorial \(n\)-fold integer programming and applications
• On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility
• A structural approach to kernels for ILPs: treewidth and total unimodularity
• Parameterized complexity of sparse linear complementarity problems
• On kernels for covering and packing ILPs with small coefficients
• Faster algorithms for sparse ILP and hypergraph multi-packing/multi-cover problems
• On polynomial kernels for sparse integer linear programs

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)