Parameterized Complexity and Approximation Algorithms

Approximation algorithms and parameterized complexity are usually considered to be two separate ways of dealing with hard algorithmic problems. In this paper, our aim is to investigate how these two fields can be combined to achieve better algorithms than what any of the two theories could offer. We...

Full description

Saved in:
Bibliographic Details
Published in:Computer journal 2008-01, Vol.51 (1), p.60-78
Main Author: Marx, Dániel
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Computer science
Graph coloring
Optimization
Parameter estimation
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Approximation algorithms and parameterized complexity are usually considered to be two separate ways of dealing with hard algorithmic problems. In this paper, our aim is to investigate how these two fields can be combined to achieve better algorithms than what any of the two theories could offer. We discuss the different ways parameterized complexity can be extended to approximation algorithms, survey results of this type and propose directions for future research.
ISSN:0010-4620
1460-2067
0010-4620
DOI:10.1093/comjnl/bxm048