Thumbnail

On the performance of congestion games for optimum satisfiability problems

Monnot, Jérôme; Giannakos, A.; Gourvès, Laurent; Paschos, Vangelis (2007), On the performance of congestion games for optimum satisfiability problems, in Graham, Fan Chung, Internet and Network Economics 3rd International Workshop, WINE 2007, San Diego, CA, USA, December 12-14, 2007, Proceedings, Springer : Berlin Heidelberg, p. 598

View/Open
Type
Communication / Conférence
Date
2007
Conference date
2007
Conference country
UNITED STATES
Book title
Internet and Network Economics 3rd International Workshop, WINE 2007, San Diego, CA, USA, December 12-14, 2007, Proceedings
Book author
Graham, Fan Chung
Publisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-540-77104-3
Pages
598
Metadata
Show full item record
Author(s)
Monnot, Jérôme cc

Giannakos, A.

Gourvès, Laurent

Paschos, Vangelis
Abstract (EN)
We introduce and study a congestion game having max sat as an underlying structure and show that its price of anarchy is 1/2. The main result is a redesign of the game leading to an improved price of anarchy of 2/3 from which we derive a non oblivious local search algorithm for max sat with locality gap 2/3. A similar congestion min sat game is also studied.
Subjects / Keywords
price of anarchy; approximation algorithm; max sat; non oblivious local search