• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Aide
  • Connexion
  • Langue 
    • Français
    • English
Consulter le document 
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Afficher

Toute la baseCentres de recherche & CollectionsAnnée de publicationAuteurTitreTypeCette collectionAnnée de publicationAuteurTitreType

Mon compte

Connexion

Enregistrement

Statistiques

Documents les plus consultésStatistiques par paysAuteurs les plus consultés
Thumbnail - No thumbnail

Super-polynomial approximation branching algorithms

Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2016), Super-polynomial approximation branching algorithms, RAIRO - Operations Research, 50, 4-5, p. 979-994. 10.1051/ro/2015060

Type
Article accepté pour publication ou publié
Lien vers un document non conservé dans cette base
https://hal.sorbonne-universite.fr/hal-01432021
Date
2016
Nom de la revue
RAIRO - Operations Research
Volume
50
Numéro
4-5
Éditeur
EDP Sciences
Pages
979-994
Identifiant publication
10.1051/ro/2015060
Métadonnées
Afficher la notice complète
Auteur(s)
Escoffier, Bruno
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Tourniaire, Emeric
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Résumé (EN)
We give sufficient conditions for deriving moderately exponential and/or parameterized time approximation schemata (i.e., algorithms achieving ratios 1 ± ϵ, for arbitrarily small ϵ) for broad classes of combinatorial optimization problems via a well-known technique widely used for deriving exact algorithms, namely the branching tree pruning.
Mots-clés
Branching algorithm; moderately exponential approximation; approximation schema

Publications associées

Affichage des éléments liés par titre et auteur.

  • Vignette de prévisualisation
    Moderate exponential time approximation and branching algorithms 
    Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012) Document de travail / Working paper
  • Vignette de prévisualisation
    Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms 
    Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2014) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    Approximating MAX SAT by moderately exponential algorithms 
    Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012) Communication / Conférence
  • Vignette de prévisualisation
    Multi-parameter Analysis for Local Graph Partitioning Problems: Using Greediness for Parameterization 
    Bonnet, Édouard; Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2015) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    Using greediness for parameterization: the case of max and min (k, n − k)-cut 
    Bonnet, Édouard; Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012) Document de travail / Working paper
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Tél. : 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo