direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility

Dr. Stefan Kratsch (TU Berlin)

We study the existence of polynomial kernels for the problem of deciding feasibility of integer linear programs (ILPs), and for finding good solutions for covering and packing ILPs. Our main results are as follows: First, we show that the ILP Feasibility problem admits no polynomial kernelization when parameterized by both the number of variables and the number of constraints, unless NP is contained in coNP/poly. This extends to the restricted cases of bounded variable degree and bounded number of variables per constraint, and to covering and packing ILPs. Second, we give a polynomial kernelization for the Cover ILP problem, asking for a solution to Ax >= b with c^Tx <= k, parameterized by k, when A is row-sparse; this generalizes a known polynomial kernelization for the special case with 0/1-variables and coefficients (d-Hitting Set).

This is follow-up work to a paper that was published earlier this year and whose results were presented in a previous AKT colloquium.

31.10.2013 16:15
Stefan Kratsch
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras