TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 10.07.2014


Page Content

to Navigation

On Kernels for Covering and Packing ILPs with Small Coefficients

M.Sc. Anh Quyen Vuong (TU Berlin)

This work continues the study of preprocessing for integer linear programs (ILPs) via the notion of kernelization from parameterized complexity. Previous work, amongst others, studied covering and packing ILPs under different parameterizations and restrictions on the sparseness of the constraint matrix. Several fairly restricted cases, e.g., if every variable appears only in a bounded number of constraints, were shown not to admit polynomial kernels, and in fact are even W[1]-hard, due to generalizing the Small Subset Sum(k) problem; this hardness relies on using coefficients of value exponential in the input size. We study these cases more carefully by taking into account also the coefficient size of the ILPs and obtain a finer classification into cases with polynomial kernels and cases that are fixed-parameter tractable (but without polynomial kernel) in addition to the previously established W[1]-hardness for unrestricted coefficients.

10.07.2014 16:15
Anh Quyen Vuong
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe