Oriented Euler complexes and signed perfect matchings
From MaRDI portal
Publication:2340282
DOI10.1007/S10107-014-0770-4zbMATH Open1309.90112arXiv1210.4694OpenAlexW2109784667MaRDI QIDQ2340282FDOQ2340282
Authors: László A. Végh, Bernhard von Stengel 
Publication date: 16 April 2015
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1210.4694
Recommendations
linear complementarity problemNash equilibriumPfaffian orientationperfect matchingcomplementary pivotingEuler complexPPAD
Cites Work
- Introduction to algorithms
- Matching theory
- Lectures on Polytopes
- New maximal numbers of equilibria in bimatrix games
- Permanents, Pfaffian orientations, and even directed circuits
- Title not available (Why is that?)
- Title not available (Why is that?)
- Paths, Trees, and Flowers
- A survey of Pfaffian orientations of graphs
- The complexity of computing the permanent
- Efficiency of a Good But Not Linear Set Union Algorithm
- The complexity of computing a Nash equilibrium
- Bimatrix Equilibrium Points and Mathematical Programming
- Linear algebra and its applications
- On the complexity of the parity argument and other inefficient proofs of existence
- Equilibrium Points of Bimatrix Games
- Title not available (Why is that?)
- A generalization of the linear complementarity problem
- Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
- Euler complexes
- Oriented Euler complexes and signed perfect matchings
- Hard-to-Solve Bimatrix Games
- Finding Gale strings
- Lemke Paths on Simple Polytopes
- A generalized complementary pivoting algorithm
- The Solution of Systems of Piecewise Linear Equations
- Title not available (Why is that?)
- Simple complexity from imitation games
- A Sperner lemma complete for PPA
- Orientation in Complementary Pivot Algorithms
- Formality of the constructible derived category for spheres: a combinatorial and a geometric approach
- On generalizing shapley's index theory to labelled pseudomanifolds
- Sperner oiks
Cited In (9)
- Oriented matroid polytopes and polyhedral fans are signable
- Hyperoctahedral Eulerian idempotents, Hodge decompositions, and signed graph coloring complexes
- Sperner oiks
- The maximum diameter of pure simplicial complexes and pseudo-manifolds
- 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)
