direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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.

Date
Speaker
Location
Language
10.07.2014 16:15
Anh Quyen Vuong
TEL 512
english

Back to the research colloquium site.

Zusatzinformationen / Extras