On the performance of congestion games for optimum satisfiability problems

Giannakos, Aristotelis; Gourvès, Laurent; Monnot, Jérôme; Paschos, Vangelis

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

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