000198663 001__ 198663
000198663 005__ 20180913062508.0
000198663 0247_ $$2doi$$a10.1016/j.dam.2012.03.012
000198663 022__ $$a0166-218X
000198663 02470 $$2ISI$$a000332427400009
000198663 037__ $$aCONF
000198663 245__ $$aExponentiality of the exchange algorithm for finding another room-partitioning$$p1
000198663 269__ $$a2014
000198663 260__ $$aAmsterdam$$bElsevier Science Bv$$c2014
000198663 300__ $$a6
000198663 336__ $$aConference Papers
000198663 520__ $$aLet 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.
000198663 6531_ $$aRoom-partitioning
000198663 6531_ $$aExchange algorithm
000198663 6531_ $$aTwo-person games
000198663 700__ $$aEdmonds, Jack$$uUniv Paris 06, Equipe Combinatoire & Optimisat, Paris, France
000198663 700__ $$aSanita, Laura
000198663 7112_ $$a1st International Symposium on Combinatorial Optimization (ISCO)$$cHammamet, TUNISIA$$dMAR 24-26, 2010
000198663 773__ $$j164$$q86-91$$tDiscrete Applied Mathematics
000198663 909C0 $$0252437$$pMATHAA$$xU10112
000198663 909CO $$ooai:infoscience.tind.io:198663$$pconf
000198663 937__ $$aEPFL-CONF-198663
000198663 973__ $$aEPFL$$rREVIEWED$$sPUBLISHED
000198663 980__ $$aCONF