• 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

On the performance of congestion games for optimum satisfiability problems

Giannakos, Aristotelis; Gourvès, Laurent; Monnot, Jérôme; Paschos, Vangelis (2007), On the performance of congestion games for optimum satisfiability problems. https://basepub.dauphine.fr/handle/123456789/20727

View/Open
cahierLamsade266.pdf (408.9Kb)
Type
Document de travail / Working paper
Date
2007
Series title
Cahiers du Lamsade
Series number
266
Metadata
Show full item record
Author(s)
Giannakos, Aristotelis
Gourvès, Laurent
Monnot, Jérôme cc
Paschos, Vangelis
Abstract (EN)
This paper focuses on tractable instances of interval data minmax regret graph problems. More precisely, we provide polynomial and pseudopolynomial algorithms for sets of particular instances of the interval data minmax regret versions of the shortest path, minimum spanning tree and weighted (bipartite) perfect matching problems. These sets are defined using a parameter that measures the distance from trivial instances. Tractable cases occur when the parameter is bounded by a constant. Two kinds of parameters are investigated, measuring either the distance from special weight structures or the distance from special graph structures.
Subjects / Keywords
price of anarchy; non oblivious local search; approximation algorithm; max sat

Related items

Showing items related by title and author.

  • Thumbnail
    On the performance of congestion games for optimum satisfiability problems 
    Monnot, Jérôme; Giannakos, A.; Gourvès, Laurent; Paschos, Vangelis (2007) Communication / Conférence
  • Thumbnail
    The Price of Optimum: Complexity and Approximation for a Matching Game 
    Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2017) Article accepté pour publication ou publié
  • Thumbnail
    The Price of Optimum in a Matching Game 
    Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2011) Communication / Conférence
  • Thumbnail
    The Maximum Duo-Preservation String Mapping Problem with Bounded Alphabet 
    Boria, Nicolas; Gourvès, Laurent; Paschos, Vangelis; Monnot, Jérôme (2021) Communication / Conférence
  • Thumbnail
    Exact and superpolynomial approximation algorithms for the densest k-subgraph problem 
    Bourgeois, Nicolas; Giannakos, Aristotelis; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2017) 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