A polynomial time approximation scheme (PTAS) for an optimization problem A is an algorithm that given in input an instance of A and ε &gt; 0 finds a (1 + ε)-approximate solution in time that is polynomial for each fixed ε. Typical running times are nO(1/ε) or 21/εO(1) n. While algorithms of the former kind tend to be impractical, the latter ones are more interesting. In several cases, the development of algorithms of the second type required considerably new, and sometimes harder, techniques. For some interesting problems, only nO(1/ε) approximation schemes are known. Under likely assumptions, we prove that for some problems (including natural ones) there cannot be approximation schemes running in time f(1/ε)nO(1), no matter how fast function f grows. Our result relies on a connection with Parameterized Complexity Theory, and we show that this connection is necessary.

Cesati, M., Trevisan, L. (1997). On the efficiency of polynomial time approximation schemes. INFORMATION PROCESSING LETTERS, 64(4), 165-171 [10.1016/s0020-0190(97)00164-6].

### On the efficiency of polynomial time approximation schemes

#### Abstract

A polynomial time approximation scheme (PTAS) for an optimization problem A is an algorithm that given in input an instance of A and ε > 0 finds a (1 + ε)-approximate solution in time that is polynomial for each fixed ε. Typical running times are nO(1/ε) or 21/εO(1) n. While algorithms of the former kind tend to be impractical, the latter ones are more interesting. In several cases, the development of algorithms of the second type required considerably new, and sometimes harder, techniques. For some interesting problems, only nO(1/ε) approximation schemes are known. Under likely assumptions, we prove that for some problems (including natural ones) there cannot be approximation schemes running in time f(1/ε)nO(1), no matter how fast function f grows. Our result relies on a connection with Parameterized Complexity Theory, and we show that this connection is necessary.
##### Scheda breve Scheda completa Scheda completa (DC)
28-nov-1997
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore ING-INF/05
English
Approximation algorithms
Computational complexity
Parameterized complexity
sciencedirect.com/science/article/abs/pii/S0020019097001646
Cesati, M., Trevisan, L. (1997). On the efficiency of polynomial time approximation schemes. INFORMATION PROCESSING LETTERS, 64(4), 165-171 [10.1016/s0020-0190(97)00164-6].
Cesati, M; Trevisan, L
Articolo su rivista
File in questo prodotto:
File
s0020-0190(97)00164-6.pdf

non disponibili

Descrizione: Articolo principale
Tipologia: Versione Editoriale (PDF)
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/2108/260207`