Exponentiality of the exchange algorithm for finding another room-partitioning

Jack Edmonds, Laura Sanità

    Research output: Contribution to journalArticleAcademicpeer-review

    1 Citation (Scopus)

    Abstract

    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.

    Original languageEnglish
    Pages (from-to)86-91
    Number of pages6
    JournalDiscrete Applied Mathematics
    Volume164
    Issue numberPART 1
    DOIs
    Publication statusPublished - 1 Jan 2014

    Keywords

    • Exchange algorithm
    • Room-partitioning
    • Two-person games

    Fingerprint Dive into the research topics of 'Exponentiality of the exchange algorithm for finding another room-partitioning'. Together they form a unique fingerprint.

    Cite this