Linear-Time Approximation for Maximum Weight Matching

DOI10.1145/2529989zbMath1295.68213OpenAlexW2047281923MaRDI QIDQ3189636

Ran Duan, Seth Pettie

Publication date: 12 September 2014

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2529989

zbMATH Keywords

matchingapproximationassignment

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Related Items

Minimum cost input/output design for large-scale linear structural systems, Faster approximation algorithms for maximizing a monotone submodular function subject to a \(b\)-matching constraint, Euclidean maximum matchings in the plane -- local to global, Fully Dynamic Matching in Bipartite Graphs, Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers, Costly circuits, submodular schedules and approximate Carathéodory theorems, Two dimensional maximum weight matching using Manhattan topology, A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs, Classes of linear programs solvable by coordinate-wise minimization, Matching and scheduling of student-company-talks for a university it-speed dating event, Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching, Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence, Data Reduction for Maximum Matching on Real-World Graphs, Advice complexity of online non-crossing matching, Multiplicative auction algorithm for approximate maximum weight bipartite matching, Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks, Unnamed Item, (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings, Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs, Unnamed Item, The power of linear-time data reduction for maximum matching, A 2/3-Approximation Algorithm for Vertex Weighted Matching in Bipartite Graphs, Approximating Spectral Clustering via Sampling: A Review, Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments, Near Approximation of Maximum Weight Matching through Efficient Weight Reduction, Structurally quotient fixed modes, Structural minimum controllability problem for switched linear continuous-time systems, On conceptually simple algorithms for variants of online bipartite matching, Recovery of disrupted airline operations using \(k\)-maximum matching in graphs, Maximum bipartite matchings with low rank data: locality and perturbation analysis, On improving matchings in trees, via bounded-length augmentations, Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs, A \(2/3\)-approximation algorithm for vertex-weighted matching, Approximation algorithms in combinatorial scientific computing, Efficient Approximation Algorithms for Weighted $b$-Matching, Exact and approximation algorithms for weighted matroid intersection, Unnamed Item, The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs, The Power of Linear-Time Data Reduction for Maximum Matching

Uses Software

• PARDISO
• JOSTLE
• KaFFPa
• Scotch
• Chaco
• KaHIP
• PARTY

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• A simple reduction from maximum weight matching to maximum cardinality matching
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• A simple approximation algorithm for the weighted matching problem
• Maximum weight bipartite matching in matrix multiplication time
• A linear-time algorithm for a special case of disjoint set union
• Scaling algorithms for network problems
• Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication
• New scaling algorithms for the assignment and minimum mean cycle problems
• Priority queues with update and finding minimum spanning trees
• Sorting in linear time?
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• Maximum skew-symmetric flows and matchings
• Clique partitions, graph compression and speeding-up algorithms
• A new pivoting strategy for Gaussian elimination
• Algorithms for dense graphs and networks on the random access computer
• A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
• Matching-based preprocessing algorithms to the solution of saddle-point problems in large-scale nonconvex interior-point optimization
• A Decomposition Theorem for Maximum Weight Bipartite Matchings
• A linear-time approximation algorithm for weighted matchings in graphs
• Undirected single-source shortest paths with positive integer weights in linear time
• An algorithm for solving the transportation problem
• Algorithms for the Assignment and Transportation Problems
• A survey of heuristics for the weighted matching problem
• Bounds on delays and queue lengths in input-queued cell switches
• Equivalence between priority queues and sorting
• Algebraic Algorithms for Matching and Matroid Problems
• An $O(EV\log V)$ Algorithm for Finding a Maximal Weighted Matching in General Graphs
• On Approximation Methods for the Assignment Problem
• An approximative algorithm for the fixed-charges transportation problem
• A new algorithm for the assignment problem
• On a Greedy Heuristic for Complete Matching
• Heuristics for planar minimum‐weight perfect metchings
• Probabilistic analysis of divide‐and‐conquer heuristics for minimum weighted euclidean matching
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• Faster scaling algorithms for general graph matching problems
• Global Price Updates Help
• Faster Scaling Algorithms for Network Problems
• Matching, Euler tours and the Chinese postman
• A General Approximation Technique for Constrained Forest Problems
• A note on shortest path, assignment, and transportation problems
• Paths, Trees, and Flowers
• A near-linear time ε-approximation algorithm for geometric bipartite matching
• Multiplying matrices faster than coppersmith-winograd
• Weighted Matchings for Preconditioning Symmetric Indefinite Linear Systems
• Maximum matching and a polyhedron with 0,1-vertices
• Modification of Edmonds' maximum matching algorithm
• A Graph-Theoretic Approach to a Class of Integer-Programming Problems
• On some techniques useful for solution of transportation network problems
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• The Distribution of a Product from Several Sources to Numerous Localities
• A Combinatorial Algorithm
• Algorithms and Computation
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Integer priority queues with decrease key in constant time and the single source shortest paths problem