198663
20180913062508.0
0166-218X
10.1016/j.dam.2012.03.012
doi
000332427400009
ISI
CONF
Exponentiality of the exchange algorithm for finding another room-partitioning
1
Amsterdam
2014
Elsevier Science Bv
2014
6
Conference Papers
Let T be a triangulated surface given by the list of vertex-triples of its triangles, called rooms. A room-partitioning for T is a subset R of the rooms such that each vertex of T is in exactly one room in R. Given a room-partitioning R for T, the exchange algorithm walks from room to room until it finds a second different room-partitioning R'. In fact, this algorithm generalizes the Lemke-Howson algorithm for finding a Nash equilibrium for two-person games. In this paper, we show that the running time of the exchange algorithm is not polynomial relative to the number of rooms, by constructing a sequence of (planar) instances, in which the algorithm walks from room to room an exponential number of times. We also show a similar result for the problem of finding a second perfect matching in Eulerian graphs. (C) 2012 Elsevier B.V. All rights reserved.
Room-partitioning
Exchange algorithm
Two-person games
Edmonds, Jack
Univ Paris 06, Equipe Combinatoire & Optimisat, Paris, France
Sanita, Laura
1st International Symposium on Combinatorial Optimization (ISCO)
Hammamet, TUNISIA
MAR 24-26, 2010
86-91
Discrete Applied Mathematics
164
MATHAA
252437
U10112
oai:infoscience.tind.io:198663
conf
EPFL-CONF-198663
EPFL
PUBLISHED
REVIEWED
CONF