Near Approximation of Maximum Weight Matching through Efficient Weight Reduction

DOI10.1007/978-3-642-20877-5_6zbMath1330.68348arXiv1012.5911OpenAlexW1699956440MaRDI QIDQ3010385

Cui di, Andrzej Lingas

Publication date: 1 July 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1012.5911

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple approximation algorithm for the weighted matching problem
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
• Linear-Time Approximation for Maximum Weight Matching
• Weighted Bipartite Matching in Matrix Multiplication Time
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Faster scaling algorithms for general graph matching problems
• Faster Scaling Algorithms for Network Problems

This page was built for publication: Near Approximation of Maximum Weight Matching through Efficient Weight Reduction