Oriented Euler complexes and signed perfect matchings
From MaRDI portal
Publication:2340282
Abstract: This paper presents "oriented pivoting systems" as an abstract framework for complementary pivoting. It gives a unified simple proof that the endpoints of complementary pivoting paths have opposite sign. A special case are the Nash equilibria of a bimatrix game at the ends of Lemke-Howson paths, which have opposite index. For Euler complexes or "oiks", an orientation is defined which extends the known concept of oriented abstract simplicial manifolds. Ordered "room partitions" for a family of oriented oiks come in pairs of opposite sign. For an oriented oik of even dimension, this sign property holds also for unordered room partitions. In the case of a two-dimensional oik, these are perfect matchings of an Euler graph, with the sign as defined for Pfaffian orientations of graphs. A near-linear time algorithm is given for the following problem: given a graph with an Eulerian orientation with a perfect matching, find another perfect matching of opposite sign. In contrast, the complementary pivoting algorithm for this problem may be exponential.
Recommendations
Cites work
- scientific article; zbMATH DE number 53115 (Why is no real title available?)
- scientific article; zbMATH DE number 3571895 (Why is no real title available?)
- scientific article; zbMATH DE number 3223483 (Why is no real title available?)
- scientific article; zbMATH DE number 3261318 (Why is no real title available?)
- A Sperner lemma complete for PPA
- A generalization of the linear complementarity problem
- A generalized complementary pivoting algorithm
- A survey of Pfaffian orientations of graphs
- Bimatrix Equilibrium Points and Mathematical Programming
- Efficiency of a Good But Not Linear Set Union Algorithm
- Equilibrium Points of Bimatrix Games
- Euler complexes
- Finding Gale strings
- Formality of the constructible derived category for spheres: a combinatorial and a geometric approach
- Hard-to-Solve Bimatrix Games
- Introduction to algorithms
- Lectures on Polytopes
- Lemke Paths on Simple Polytopes
- Linear algebra and its applications
- Matching theory
- New maximal numbers of equilibria in bimatrix games
- On generalizing shapley's index theory to labelled pseudomanifolds
- On the complexity of the parity argument and other inefficient proofs of existence
- Orientation in Complementary Pivot Algorithms
- Oriented Euler complexes and signed perfect matchings
- Paths, Trees, and Flowers
- Permanents, Pfaffian orientations, and even directed circuits
- Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
- Simple complexity from imitation games
- Sperner oiks
- The Solution of Systems of Piecewise Linear Equations
- The complexity of computing a Nash equilibrium
- The complexity of computing the permanent
Cited in
(8)- Hyperoctahedral Eulerian idempotents, Hodge decompositions, and signed graph coloring complexes
- Oriented matroid polytopes and polyhedral fans are signable
- Sperner oiks
- Oriented Euler complexes and signed perfect matchings
- Exponentiality of the exchange algorithm for finding another room-partitioning
- Games in oriented matroids
- Colorful linear programming, Nash equilibrium, and pivots
- Euler complexes (oiks)
This page was built for publication: Oriented Euler complexes and signed perfect matchings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2340282)
