Parameterized Approximation via Fidelity Preserving Transformations

Michael Fellows, Ariel Kulik, Frances Rosamond, Hadas Shachnai

    Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedings

    1 Downloads (Pure)

    Abstract

    We motivate and describe a new parameterized approximation paradigm which studies the interaction between performance ratio and running time for any parametrization of a given optimization problem. As a key tool, we introduce the concept of α-shrinking transformation, for α ≥ 1. Applying such transformation to a parameterized problem instance decreases the parameter value, while preserving approximation ratio of α (or α-fidelity).

    For example, it is well-known that Vertex Cover cannot be approximated within any constant factor better than 2 [24] (under usual assumptions). Our parameterized α-approximation algorithm for k-Vertex Cover, parameterized by the solution size, has a running time of 1.273(2 − α)k , where the running time of the best FPT algorithm is 1.273 k [10]. Our algorithms define a continuous tradeoff between running times and approximation ratios, allowing practitioners to appropriately allocate computational resources.

    Moving even beyond the performance ratio, we call for a new type of approximative kernelization race. Our α-shrinking transformations can be used to obtain kernels which are smaller than the best known for a given problem. For the Vertex Cover problem we obtain a kernel size of 2(2 − α)k. The smaller “α-fidelity” kernels allow us to solve exactly problem instances more efficiently, while obtaining an approximate solution for the original instance.

    We show that such transformations exist for several fundamental problems, including Vertex Cover, d-Hitting Set, Connected Vertex Cover and Steiner Tree. We note that most of our algorithms are easy to implement and are therefore practical in use.
    Original languageEnglish
    Title of host publicationAutomata, Languages, and Programming
    EditorsArtur Czumaj, Kurt Mehlhorn, Andrew Pitts, Roger Wattenhofer
    Place of PublicationOnline
    PublisherSpringer
    Pages351-362
    Number of pages12
    ISBN (Print)978-3-642-31593-0
    Publication statusPublished - 2012
    EventInternational Colloquium on Automata Languages and Programming (ICALP 2012 39th) - University of Warwick United Kingdown, Warwick, United Kingdom
    Duration: 9 Jul 201213 Jul 2012
    Conference number: 2012 (39th)

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer
    Volume7391
    ISSN (Print)0302-9743

    Conference

    ConferenceInternational Colloquium on Automata Languages and Programming (ICALP 2012 39th)
    Abbreviated titleICALP
    CountryUnited Kingdom
    CityWarwick
    Period9/07/1213/07/12

      Fingerprint

    Cite this

    Fellows, M., Kulik, A., Rosamond, F., & Shachnai, H. (2012). Parameterized Approximation via Fidelity Preserving Transformations. In A. Czumaj, K. Mehlhorn, A. Pitts, & R. Wattenhofer (Eds.), Automata, Languages, and Programming (pp. 351-362). (Lecture Notes in Computer Science; Vol. 7391). Online: Springer.