Linear-time approximation for maximum weight matching
From MaRDI portal
Recommendations
- A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
- scientific article; zbMATH DE number 1304326
- Improved linear time approximation algorithms for weighted matchings
- A linear-time approximation algorithm for weighted matchings in graphs
- A simple approximation algorithm for the weighted matching problem
Cites work
- scientific article; zbMATH DE number 2089222 (Why is no real title available?)
- scientific article; zbMATH DE number 3643026 (Why is no real title available?)
- scientific article; zbMATH DE number 432790 (Why is no real title available?)
- scientific article; zbMATH DE number 3119304 (Why is no real title available?)
- scientific article; zbMATH DE number 3174052 (Why is no real title available?)
- scientific article; zbMATH DE number 3664381 (Why is no real title available?)
- scientific article; zbMATH DE number 3637616 (Why is no real title available?)
- scientific article; zbMATH DE number 1304326 (Why is no real title available?)
- scientific article; zbMATH DE number 1305475 (Why is no real title available?)
- scientific article; zbMATH DE number 3231691 (Why is no real title available?)
- scientific article; zbMATH DE number 3231692 (Why is no real title available?)
- scientific article; zbMATH DE number 3231693 (Why is no real title available?)
- scientific article; zbMATH DE number 3334901 (Why is no real title available?)
- scientific article; zbMATH DE number 3338967 (Why is no real title available?)
- scientific article; zbMATH DE number 3349645 (Why is no real title available?)
- scientific article; zbMATH DE number 3390827 (Why is no real title available?)
- scientific article; zbMATH DE number 3062452 (Why is no real title available?)
- scientific article; zbMATH DE number 3099866 (Why is no real title available?)
- A Combinatorial Algorithm
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- A General Approximation Technique for Constrained Forest Problems
- A Graph-Theoretic Approach to a Class of Integer-Programming Problems
- A decomposition theorem for maximum weight bipartite matchings
- A faster implementation of the Goemans-Williamson clustering algorithm
- A linear-time algorithm for a special case of disjoint set union
- A linear-time approximation algorithm for weighted matchings in graphs
- A near-linear time ε-approximation algorithm for geometric bipartite matching
- A new algorithm for the assignment problem
- A new pivoting strategy for Gaussian elimination
- A note on shortest path, assignment, and transportation problems
- A note on two problems in connexion with graphs
- A simple approximation algorithm for the weighted matching problem
- A simple reduction from maximum weight matching to maximum cardinality matching
- A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
- A survey of heuristics for the weighted matching problem
- A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
- Algebraic algorithms for matching and matroid problems
- Algorithms and Computation
- Algorithms for dense graphs and networks on the random access computer
- Algorithms for the Assignment and Transportation Problems
- An O(EV\log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- An algorithm for solving the transportation problem
- An approximative algorithm for the fixed-charges transportation problem
- Bounds on delays and queue lengths in input-queued cell switches
- Clique partitions, graph compression and speeding-up algorithms
- Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
- Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication
- Equivalence between priority queues and sorting
- Faster Scaling Algorithms for Network Problems
- Faster scaling algorithms for general graph matching problems
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Global Price Updates Help
- Heuristics for planar minimum‐weight perfect metchings
- Improved linear time approximation algorithms for weighted matchings
- Integer priority queues with decrease key in constant time and the single source shortest paths problem
- Matching, Euler tours and the Chinese postman
- Matching-based preprocessing algorithms to the solution of saddle-point problems in large-scale nonconvex interior-point optimization
- Maximum matching and a polyhedron with 0,1-vertices
- Maximum skew-symmetric flows and matchings
- Maximum weight bipartite matching in matrix multiplication time
- Modification of Edmonds' maximum matching algorithm
- Multiplying matrices faster than coppersmith-winograd
- New scaling algorithms for the assignment and minimum mean cycle problems
- On Approximation Methods for the Assignment Problem
- On a Greedy Heuristic for Complete Matching
- On some techniques useful for solution of transportation network problems
- Paths, Trees, and Flowers
- Priority queues with update and finding minimum spanning trees
- Probabilistic analysis of divide‐and‐conquer heuristics for minimum weighted euclidean matching
- Scaling algorithms for network problems
- Sorting in linear time?
- The Distribution of a Product from Several Sources to Numerous Localities
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Undirected single-source shortest paths with positive integer weights in linear time
- Weighted Matchings for Preconditioning Symmetric Indefinite Linear Systems
Cited in
(60)- Maximum bipartite matchings with low rank data: locality and perturbation analysis
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Multiplicative auction algorithm for approximate maximum weight bipartite matching
- Dynamic matching with better-than-2 approximation in polylogarithmic update time
- A strongly polynomial-time algorithm for weighted general factors with three feasible degrees
- Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
- The weighted matching approach to maximum cardinality matching
- Euclidean maximum matchings in the plane -- local to global
- Multiplicative auction algorithm for approximate maximum weight bipartite matching
- Approximate Matching in Weighted Sequences
- Data Reduction for Maximum Matching on Real-World Graphs
- Minimum jointly structural input and output selection
- Minimum cost input/output design for large-scale linear structural systems
- scientific article; zbMATH DE number 7758339 (Why is no real title available?)
- Online metric matching on the line with recourse
- Faster approximation algorithms for maximizing a monotone submodular function subject to a b-matching constraint
- On improving matchings in trees, via bounded-length augmentations
- Fully dynamic matching in bipartite graphs
- Structurally quotient fixed modes
- Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality
- Approximating spectral clustering via sampling: a review
- Deterministic fully dynamic data structures for vertex cover and matching
- The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
- A simple approximation algorithm for the weighted matching problem
- Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks
- Approximation algorithms in combinatorial scientific computing
- New approximation results on graph matching and related problems
- Costly circuits, submodular schedules and approximate Carathéodory theorems
- Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers
- The power of linear-time data reduction for maximum matching
- Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
- Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
- A scaling algorithm for weighted f-factors in general graphs
- Shifting coresets: obtaining linear-time approximations for unit disk graphs and other geometric intersection graphs
- Two dimensional maximum weight matching using Manhattan topology
- Classes of linear programs solvable by coordinate-wise minimization
- The Power of Linear-Time Data Reduction for Maximum Matching
- Matching and scheduling of student-company-talks for a university it-speed dating event
- Recovery of disrupted airline operations using \(k\)-maximum matching in graphs
- Near approximation of maximum weight matching through efficient weight reduction
- (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings
- Approximating optimum branchings in linear time
- Decremental matching in general weighted graphs
- A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
- A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
- Advice complexity of online non-crossing matching
- A \(2/3\)-approximation algorithm for vertex-weighted matching
- Euclidean maximum matchings in the plane -- local to global
- An efficient alternative strategy for finding prices in envy-free perfect matchings
- Estimating optimal objective values for the TSP, VRP, and other combinatorial problems using randomization
- Fast matching-based approximations for maximum duo-preservation string mapping and its weighted variant
- Greediness is not always a vice: efficient discovery algorithms for assignment problems
- A simple (1-)-approximation semi-streaming algorithm for maximum (weighted) matching
- Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and =(1/)-convergence
- Exact and approximation algorithms for weighted matroid intersection
- An efficient NC algorithm for approximate maximum weight matching
- Approximation algorithms for maximum matchings in undirected graphs
- Structural minimum controllability problem for switched linear continuous-time systems
- Efficient approximation algorithms for weighted b-matching
- A 2/3-approximation algorithm for vertex weighted matching in bipartite graphs
This page was built for publication: Linear-time approximation for maximum weight matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3189636)
