Inapproximability of shortest paths on perfect matching polytopes
From MaRDI portal
Publication:6085990
DOI10.1007/978-3-031-32726-1_6arXiv2210.14608OpenAlexW4377200037MaRDI QIDQ6085990
No author found.
Publication date: 9 November 2023
Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2210.14608
simplex methodcombinatorial reconfigurationperfect matching polytopespivot rulescircuit augmentations
Cites Work
- Unnamed Item
- Unnamed Item
- Complexity of independent set reconfigurability problems
- A counterexample to the Hirsch conjecture
- An exponential lower bound for Cunningham's rule
- On the complexity of reconfiguration problems
- Worst case behavior of the steepest edge simplex method
- On certain polytopes associated with graphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Random walks on trees and matchings
- A note on the approximability of deepest-descent circuit steps
- A polyhedral model for enumeration and optimization over the set of circuits
- On the complexity of optimal matching reconfiguration
- Shortest reconfiguration of matchings
- Introduction to reconfiguration
- The simplex algorithm with the pivot rule of maximizing criterion improvement
- The complexity of change
- The Complexity of the Simplex Method
- An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
- On the Circuit Diameter of Dual Transportation Polyhedra
- On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
- Note on Weintraub’s Minimum-Cost Circulation Algorithm
- New Finite Pivoting Rules for the Simplex Method
- Matchings and phylogenetic trees
- Color-coding
- The Simplex Algorithm Is NP-Mighty
- On the Circuit Diameter of Some Combinatorial Polytopes
- Finding a long directed cycle
- On the flip graphs on perfect matchings of complete graphs and signed reversal graphs
- Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
- The Perfect Matching Reconfiguration Problem
- ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
- On Simplex Pivoting Rules and Complexity Theory
- Automata, Languages and Programming
- Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization
- Flip distances between graph orientations
- On matroid intersection adjacency
- An exponential lower bound for Zadeh's pivot rule
This page was built for publication: Inapproximability of shortest paths on perfect matching polytopes
