A survey on approximation in parameterized complexity: Hardness and algorithms

Andreas E. Feldmann; C. S. Karthik; Euiwoong Lee; Pasin Manurangsi

doi:10.3390/A13060146

A survey on approximation in parameterized complexity: Hardness and algorithms

Andreas E. Feldmann, C. S. Karthik, Euiwoong Lee, Pasin Manurangsi

Research output: Contribution to journal › Article › peer-review

27 Scopus citations

Abstract

Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions.

Original language	English (US)
Article number	146
Journal	Algorithms
Volume	13
Issue number	6
DOIs	https://doi.org/10.3390/A13060146
State	Published - Jun 1 2020
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Numerical Analysis
Computational Theory and Mathematics
Computational Mathematics

Keywords

Approximation algorithms
Hardness of approximation
Parameterized complexity

Access to Document

10.3390/A13060146

Cite this

@article{729f1e80c29c47068667d4a35437f1cc,

title = "A survey on approximation in parameterized complexity: Hardness and algorithms",

abstract = "Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions.",

keywords = "Approximation algorithms, Hardness of approximation, Parameterized complexity",

author = "Feldmann, {Andreas E.} and Karthik, {C. S.} and Euiwoong Lee and Pasin Manurangsi",

note = "Funding Information: Funding: Andreas Emil Feldmann is supported by the Czech Science Foundation GACR (grant #19-27871X), and by the Center for Foundations of Modern Computer Science (Charles Univ. project UNCE/SCI/004). Karthik C. S. is supported by ERC-CoG grant 772839, the Israel Science Foundation (grant number 552/16), and from the Len Blavatnik and the Blavatnik Family foundation. Euiwoong Lee is supported by the Simons Collaboration on Algorithms and Geometry. Publisher Copyright: {\textcopyright} 2020 by the authors.",

year = "2020",

month = jun,

day = "1",

doi = "10.3390/A13060146",

language = "English (US)",

volume = "13",

journal = "Algorithms",

issn = "1999-4893",

publisher = "MDPI AG",

number = "6",

}

TY - JOUR

T1 - A survey on approximation in parameterized complexity

T2 - Hardness and algorithms

AU - Feldmann, Andreas E.

AU - Karthik, C. S.

AU - Lee, Euiwoong

AU - Manurangsi, Pasin

N1 - Funding Information: Funding: Andreas Emil Feldmann is supported by the Czech Science Foundation GACR (grant #19-27871X), and by the Center for Foundations of Modern Computer Science (Charles Univ. project UNCE/SCI/004). Karthik C. S. is supported by ERC-CoG grant 772839, the Israel Science Foundation (grant number 552/16), and from the Len Blavatnik and the Blavatnik Family foundation. Euiwoong Lee is supported by the Simons Collaboration on Algorithms and Geometry. Publisher Copyright: © 2020 by the authors.

PY - 2020/6/1

Y1 - 2020/6/1

N2 - Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions.

AB - Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions.

KW - Approximation algorithms

KW - Hardness of approximation

KW - Parameterized complexity

UR - http://www.scopus.com/inward/record.url?scp=85087501207&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85087501207&partnerID=8YFLogxK

U2 - 10.3390/A13060146

DO - 10.3390/A13060146

M3 - Article

AN - SCOPUS:85087501207

SN - 1999-4893

VL - 13

JO - Algorithms

JF - Algorithms

IS - 6

M1 - 146

ER -

A survey on approximation in parameterized complexity: Hardness and algorithms

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this