TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 31.10.2013

isti-logo

Page Content

to Navigation

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.

Date
Speaker
Location
Language
31.10.2013 16:15
Stefan Kratsch
TEL 512
english

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe