Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Lossy kernelization

Tools
- Tools
+ 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

[img]
Preview
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

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
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:
DateEvent
June 2017Published
10 February 2017Accepted
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 IDRIOXX Funder NameFunder ID
715744European Research Councilhttp://viaf.org/viaf/130022607
306992European Research Councilhttp://viaf.org/viaf/130022607
267959European Research Councilhttp://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 View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us