License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.80
URN: urn:nbn:de:0030-drops-39241
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3924/
Go to the corresponding LIPIcs Volume Portal

Kratsch, Stefan

On Polynomial Kernels for Sparse Integer Linear Programs

pdf-format:
12.pdf (0.6 MB)

Abstract

Integer linear programs (ILPs) are a widely applied framework for dealing with combinatorial problems that arise in practice. It is known, e.g., by the success of CPLEX, that preprocessing and simplification can greatly speed up the process of optimizing an ILP. The present work seeks to further the theoretical understanding of preprocessing for ILPs by initiating a rigorous study within the framework of parameterized complexity and kernelization.

A famous result of Lenstra (Mathematics of Operations Research, 1983) shows that feasibility of any ILP with n variables and m constraints can be decided in time O(c^{n^3} m^{c'}). Thus, by a folklore argument, any such ILP admits a kernelization to an equivalent instance of size O(c^{n^3}). It is known, that unless \containment and the polynomial hierarchy collapses, no kernelization with size bound polynomial in n is possible. However, this lower bound only applies for the case when constraints may include an arbitrary number of variables since it follows from lower bounds for \sat and \hittingset, whose bounded arity variants admit polynomial kernelizations.

We consider the feasibility problem for ILPs Ax <= b where A is an r-row-sparse matrix parameterized by the number of variables. We show that the kernelizability of this problem depends strongly on the range of the variables. If the range is unbounded then this problem does not admit a polynomial kernelization unless \containment. If, on the other hand, the range of each variable is polynomially bounded in n then we do get a polynomial kernelization. Additionally, this holds also for the more general case when the maximum range d is an additional parameter, i.e., the size obtained is polynomial in n+d.

BibTeX - Entry

@InProceedings{kratsch:LIPIcs:2013:3924,
  author =	{Stefan Kratsch},
  title =	{{On Polynomial Kernels for Sparse Integer Linear Programs}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{80--91},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3924},
  URN =		{urn:nbn:de:0030-drops-39241},
  doi =		{10.4230/LIPIcs.STACS.2013.80},
  annote =	{Keywords: integer linear programs, kernelization, parameterized complexity}
}

Keywords: integer linear programs, kernelization, parameterized complexity
Collection: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue Date: 2013
Date of publication: 26.02.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI