## 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.

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 language | English |
---|---|

Title of host publication | Automata, Languages, and Programming |

Editors | Artur Czumaj, Kurt Mehlhorn, Andrew Pitts, Roger Wattenhofer |

Place of Publication | Online |

Publisher | Springer |

Pages | 351-362 |

Number of pages | 12 |

ISBN (Print) | 978-3-642-31593-0 |

Publication status | Published - 2012 |

Event | International Colloquium on Automata Languages and Programming (ICALP 2012 39th) - University of Warwick United Kingdown, Warwick, United Kingdom Duration: 9 Jul 2012 → 13 Jul 2012 Conference number: 2012 (39th) |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 7391 |

ISSN (Print) | 0302-9743 |

### Conference

Conference | International Colloquium on Automata Languages and Programming (ICALP 2012 39th) |
---|---|

Abbreviated title | ICALP |

Country/Territory | United Kingdom |

City | Warwick |

Period | 9/07/12 → 13/07/12 |