The Library
Lossy kernelization
Tools
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
|
PDF
WRAP-Lossy-Kernelization-Ramanujan-2019.pdf - Accepted Version - Requires a PDF viewer. Download (937Kb) | Preview |
Official URL: https://doi.org/10.1145/3055399.3055456
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, Engineering and Medicine > Science > Computer Science | ||||||||||||
Library of Congress Subject Headings (LCSH): | Heuristic algorithms, Approximation algorithms | ||||||||||||
Series Name: | STOC: ACM Symposium on Theory of Computing | ||||||||||||
Journal or Publication Title: | STOC 2017 Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | ||||||||||||
Publisher: | ACM | ||||||||||||
ISBN: | 9781450345286 | ||||||||||||
Official Date: | June 2017 | ||||||||||||
Dates: |
|
||||||||||||
Page Range: | 224-237 | ||||||||||||
DOI: | 10.1145/3055399.3055456 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Reuse Statement (publisher, data, author rights): | © 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 | ||||||||||||
Date of first compliant deposit: | 12 February 2019 | ||||||||||||
Date of first compliant Open Access: | 1 March 2019 | ||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||
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: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year