Fixed-Parameter and Approximation Algorithms: A New Look

DOI10.1007/978-3-319-03898-8_11MaRDI QIDQ2867077zbMATH OpenOpenAlexFDO

Authors Rajesh Chitnis, Mohammad T. Hajiaghayi, Guy Kortsarz

Publication date 10 December 2013

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.3520

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Abstract: A Fixed-Parameter Tractable (FPT) $ho$-approximation algorithm for a minimization (resp. maximization) parameterized problem $P$ is an FPT algorithm that, given an instance $(x,k)inP$ computes a solution of cost at most $kcdotho(k)$ (resp. $k/ho(k)$) if a solution of cost at most (resp. at least) $k$ exists; otherwise the output can be arbitrary. For well-known intractable problems such as the W[1]-hard {Clique} and W[2]-hard {Set Cover} problems, the natural question is whether we can get any FPT-approximation. It is widely believed that both {Clique} and {Set-Cover} admit no FPT $ho$-approximation algorithm, for any increasing function $ho$. Assuming standard conjectures such as the Exponential Time Hypothesis (ETH) cite{eth-paturi} and the Projection Games Conjecture (PGC) cite{r3}, we make the first progress towards proving this conjecture by showing that 1. Under the ETH and PGC, there exist constants $F_1,F_2>0$ such that the {Set Cover} problem does not admit an FPT approximation algorithm with ratio $k^{F_1}$ in $2^{k^{F_2}}cdotextpoly(N,M)$ time, where $N$ is the size of the universe and $M$ is the number of sets. 2. Unless $NPsubseteqSUBEXP$, for every $1>delta>0$ there exists a constant $F(delta)>0$ such that {Clique} has no FPT cost approximation with ratio $k^{1-delta}$ in $2^{k^F}cdotextpoly(n)$ time, where $n$ is the number of vertices in the graph. In the second part of the paper we consider various W[1]-hard problems such as {dst}, {dsf}, Directed Steiner Network and {mec}. For all these problem we give polynomial time $f(extOPT)$-approximation algorithms for some small function $f$ (the largest approximation ratio we give is $ext{OPT}^2$).

Recommendations

• Fixed-parameter approximation: conceptual framework and approximability results
• Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
• On Parameterized Approximability
• Faster exact algorithms for hard problems: A parameterized point of view
• On fixed-parameter tractability and approximability of NP optimization problems
• An introduction to the analysis of approximation algorithms
• Approximation Algorithms: Good Solutions to Hard Problems
• Parameterized Approximation Problems

Cited in

(19)

• Time-approximation trade-offs for inapproximable problems
• Parameterized (in)approximability of subset problems
• Partitioning a graph into small pieces with applications to path transversal
• Augmenting weighted graphs to establish directed point-to-point connectivity
• A review on algorithms for maximum clique problems
• On directed Steiner trees with multiple roots
• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
• Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
• The constant inapproximability of the parameterized dominating set problem
• Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation
• Parameterized approximation algorithms for bidirected Steiner network problems
• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• On the parameterized complexity of approximating dominating set
• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
• Faster exact algorithms for hard problems: A parameterized point of view
• An ETH-tight algorithm for bidirected Steiner connectivity
• On the exact \& approximate complexity of the strongly connected Steiner subgraph problem on two terminals with demands
• Approximating split delivery path routing problems
• Parameterized inapproximability hypothesis under ETH

This page was built for publication: Fixed-Parameter and Approximation Algorithms: A New Look

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2867077)