Polyhedral techniques in combinatorial optimization: matchings and tours
From MaRDI portal
Publication:6118160
DOI10.4171/icm2022/127OpenAlexW4389774924MaRDI QIDQ6118160
Publication date: 20 March 2024
Published in: International Congress of Mathematicians (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4171/icm2022/127
linear programmingcombinatorial optimizationtraveling salesman problemmatchingsapproximation algorithmsderandomization
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20) General topics in the theory of algorithms (68W01)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
- On computing the determinant in small parallel time using a small number of processors
- Matching is as easy as matrix inversion
- Constructing a perfect matching is in random NC
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Linear matroid intersection is in quasi-NC
- \(\frac{13}{9}\)-approximation for graphic TSP
- Almost exact matchings
- An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
- The Design of Approximation Algorithms
- Finding the Exact Integrality Gap for Small Traveling Salesman Problems
- Improving Christofides' Algorithm for the s-t Path TSP
- Removing and Adding Edges for the Traveling Salesman Problem
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
- Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
- The traveling salesman problem on a graph and some related integer polyhedra
- On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
- Fast Parallel Matrix Inversion Algorithms
- Maximum matching of given weight in complete and complete bipartite graphs
- The Matching Polytope has Exponential Extension Complexity
- A new approximation algorithm for the asymmetric TSP with triangle inequality
- Exact Perfect Matching in Complete Graphs
- Bipartite Perfect Matching is in Quasi-NC
- NC Algorithms for Weighted Planar Perfect Matching and Related Problems
- A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
- Planar Graph Perfect Matching Is in NC
- An improved approximation algorithm for ATSP
- Reducing path TSP to TSP
- A constant-factor approximation algorithm for the asymmetric traveling salesman problem
- A 1.5-Approximation for Path TSP
- Approaching 3/2 for the s - t -path TSP
- Paths, Trees, and Flowers
- An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
- Solution of a Large-Scale Traveling-Salesman Problem
- On the Integrality Ratio for the Asymmetric Traveling Salesman Problem
- A Randomized Rounding Approach to the Traveling Salesman Problem
- Maximum matching and a polyhedron with 0,1-vertices
- The Traveling-Salesman Problem and Minimum Spanning Trees
- The Factorization of Linear Graphs
- Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces
- In Pursuit of the Traveling Salesman
- A (slightly) improved approximation algorithm for metric TSP
