Moderate exponential time approximation and branching algorithms

Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric

Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012), Moderate exponential time approximation and branching algorithms. https://basepub.dauphine.fr/handle/123456789/12146

Type

Document de travail / Working paper

External document link

https://hal.archives-ouvertes.fr/hal-00874358

Date

2012

Publisher

Université Paris-Dauphine

Series title

Cahiers du Lamsade

Published in

Paris

Metadata

Show full item record

Author(s)

Escoffier, Bruno
Paschos, Vangelis
Tourniaire, Emeric

Abstract (EN)

We study links between approximation, exponential time computation and fixed parameter tractability. In particular, rather than focusing on one particular optimization problem, we tackle the question of finding sufficient conditions for a problem to admit "good" approximation algorithms in exponential time. In particular, we focus on the existence of "approximation schemata" (ratios 1 ± ε for arbitrarily small ε) and we exhibit conditions under which a technique of devising approximate branching algorithms reaches interesting results.

Subjects / Keywords

Complexité; Algorithme et structure de données