Lokshtanov, Daniel, Panolan, Fahad, Maadapuzhi Sridharan, Ramanujan and Saurabh, Saket (2017) Lossy kernelization. In: STOC 2017, 49th Annual ACM Symposium on the Theory of Computing, Montreal, 19-23 Jun 2017. Published in: STOC 2017 Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing 224-237 . ISBN 9781450345286. doi:10.1145/3055399.3055456

Preview

PDF WRAP-Lossy-Kernelization-Ramanujan-2019.pdf - Accepted Version - Requires a PDF viewer. Download (937Kb) | Preview

Request Changes to record.

Abstract

In this paper we propose a new framework for analyzing the performance of preprocessing algorithms. Our framework builds on the notion of kernelization from parameterized complexity. However, as opposed to the original notion of kernelization, our definitions com- bine well with approximation algorithms and heuristics. The key new definition is that of a polynomial size α-approximate kernel. Loosely speaking, a polynomial size α-approximate kernel is a polynomial time pre-processing algorithm that takes as input an instance (I, k) to a parameterized problem, and outputs another instance (I′,k′) to the same problem, such that |I′| + k′ ≤ kO(1). Additionally, for every c ≥ 1, a c-approximate solution s′ to the pre-processed instance (I′, k′) can be turned in polynomial time into a (c · α)-approximate solution s to the original instance (I,k).

Amongst our main technical contributions are α-approximate kernels of polynomial size for three problems, namely Connected Vertex Cover, Disjoint Cycle Packing and Disjoint Factors. These problems are known not to admit any polynomial size kernels unless NP ⊆ coNP/Poly. Our approximate kernels simultaneously beat both the lower bounds on the (normal) kernel size, and the hardness of approximation lower bounds for all three problems. On the negative side we prove that Longest Path parameterized by the length of the path and Set Cover parameterized by the universe size do not admit even an α-approximate kernel of polynomial size, for any α≥1, unless NP ⊆ coNP/Poly. In order to prove this lower bound we need to combine in a non-trivial way the techniques used for showing kernelization lower bounds with the methods for showing hardness of approximation.

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Library of Congress Subject Headings (LCSH):	Heuristic algorithms, Approximation algorithms
Journal or Publication Title:	STOC 2017 Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
Publisher:	ACM
ISBN:	9781450345286
Official Date:	10 February 2017
Dates:	Date Event 10 February 2017 Accepted
Date of first compliant deposit:	12 February 2019
Page Range:	224-237
DOI:	10.1145/3055399.3055456
Status:	Peer Reviewed
Publication Status:	Published
Publisher Statement:	© ACM New York, NY, USA ©2017 . This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in STOC 2017 Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computinghttp://dx.doi.org/10.1145/3055399.3055456
Access rights to Published version:	Restricted or Subscription Access
RIOXX Funder/Project Grant:	Project/Grant ID RIOXX Funder Name Funder ID 715744 European Research Council http://viaf.org/viaf/130022607 306992 European Research Council http://viaf.org/viaf/130022607 267959 European Research Council http://viaf.org/viaf/130022607
Conference Paper Type:	Paper
Title of Event:	STOC 2017, 49th Annual ACM Symposium on the Theory of Computing
Type of Event:	Conference
Location of Event:	Montreal
Date(s) of Event:	19-23 Jun 2017
Open Access Version:	ArXiv

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads