• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

Polynomial Approximation for Multicriteria Combinatorial Optimization Problems

Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2014), Polynomial Approximation for Multicriteria Combinatorial Optimization Problems, in Paschos, Vangelis Th., Paradigms of Combinatorial Optimization: Problems and New Approaches, Volume 2, ISTE, p. 511-545. 10.1002/9781118600207.ch16

Type
Chapitre d'ouvrage
Date
2014
Book title
Paradigms of Combinatorial Optimization: Problems and New Approaches, Volume 2
Book author
Paschos, Vangelis Th.
Publisher
ISTE
ISBN
9781848211483
Number of pages
700
Pages
511-545
Publication identifier
10.1002/9781118600207.ch16
Metadata
Show full item record
Author(s)
Angel, Eric
Informatique, Biologie Intégrative et Systèmes Complexes [IBISC]
Bampis, Evripidis
Laboratoire d'Informatique de Paris 6 [LIP6]
Gourvès, Laurent
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
Combinatorial optimization problems serve as models for a great number of real problems, and are studied in order to construct algorithms that are effective in terms of complexity and of the quality of the solutions returned. This chapter begins approximation algorithms with performance guarantees, it refer readers who want information on the other approaches to some publications and the references that they contain. The chapter contains a general presentation of multicriteria problems in combinatorial optimization, and tackles notions of optimality and of complexity. It presents four general approaches to polynomial approximation with performance guarantees. Furthermore, each approach is illustrated with an example from various publications. There are four of these approaches: the criteria weighting approach; the simultaneous approach; the budget approach; the Pareto curve approach.
Subjects / Keywords
Budget approach; Criteria weighting/Pareto curve; Performance guarantee; Polynomial approximation; Multicriteria combinatorial

Related items

Showing items related by title and author.

  • Thumbnail
    Approximation polynomiale avec garantie de performance pour l'optimisation multicritère 
    Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2007) Chapitre d'ouvrage
  • Thumbnail
    (Non)-Approximability for the multi-criteria TSP(1,2) 
    Monnot, Jérôme; Gourvès, Laurent; Bampis, Evripidis; Angel, Eric (2005) Communication / Conférence
  • Thumbnail
    Approximation in Multiobjective problems 
    Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2007) Chapitre d'ouvrage
  • Thumbnail
    Approximating the Pareto Curve with Local Search for the Bicriteria TSP (1, 2) Problem (extended abstract) 
    Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2003) Communication / Conférence
  • Thumbnail
    Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem 
    Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2004) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo