Solving matching problems with linear programming

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

zbMATH Keywords

simplex methodimplementationcomputational studysparse subgraphscutting plane algorithmperfect matching problem

Mathematics Subject Classification ID

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