Solving matching problems with linear programming
From MaRDI portal
Publication:3703653
DOI10.1007/BF01584376zbMath0579.90069OpenAlexW2038344659MaRDI QIDQ3703653
Olaf Holland, Martin Grötschel
Publication date: 1985
Published in: Mathematical Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01584376
simplex methodimplementationcomputational studysparse subgraphscutting plane algorithmperfect matching problem
Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Integer programming (90C10) Linear programming (90C05)
Related Items
A branch-and-cut algorithm for vehicle routing problems, New primal and dual matching heuristics, Solving real-world linear ordering problems using a primal-dual interior point cutting plane method, Cardinality-restricted chains and antichains in partially ordered sets, A cutting plane algorithm for a clustering problem, Constraint relaxation for the discrete ordered median problem, Facet identification for the symmetric traveling salesman polytope, Undirected postman problems with zigzagging option: a cutting-plane approach, Ordered weighted average combinatorial optimization: formulations and their properties, A polyhedral approach to edge coloring, Solving the minimum label spanning tree problem by mathematical programming techniques, Euclidean semi-matchings of random samples, Solving combinatorial optimization problems using Karmarkar's algorithm, A cutting plane algorithm for the windy postman problem, The hierarchical mixed rural postman problem: polyhedral analysis and a branch-and-cut algorithm, The Cutting Plane Method is Polynomial for Perfect Matchings, Solving (large scale) matching problems combinatorially, Combinatorial optimization and small polytopes, Approximation algorithms in combinatorial scientific computing, A cutting plane algorithm for minimum perfect 2-matchings, Efficient Approximation Algorithms for Weighted $b$-Matching, Facets and algorithms for capacitated lot sizing, Solution of large-scale symmetric travelling salesman problems, Fast algorithms for the undirected negative cost cycle detection problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Assignment and matching problems: solution methods with FORTRAN-programs. In cooperation with T. Bönniger and G. Katzakidis
- The ellipsoid method and its consequences in combinatorial optimization
- Weakly bipartite graphs and the max-cut problem
- An \(O(IVI^3)\) algorithm for finding maximum flows in networks
- A Cutting Plane Algorithm for the Linear Ordering Problem
- A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem
- A primal simplex variant for the maximum-flow problem
- An analysis of alternative strategies for implementing matching algorithms
- Solving large-scale matching problems efficiently: A new primal matching approach
- Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
- Odd Minimum Cut-Sets and b-Matchings
- Paths, Trees, and Flowers
- Maximum matching and a polyhedron with 0,1-vertices
