Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model

We study the maximum weight matching problem in the semi-streaming model, and improve on the currently best one-pass algorithm due to Zelke (Proc.\ STACS~'08, pages 669--680) by devising a deterministic approach whose performance guarantee is $4.91 + \eps$. In addition, we study {\em preemptive} online algorithms, a sub-class of one-pass algorithms where we are only allowed to maintain a feasible matching in memory at any point in time. All known results prior to Zelke's belong to this sub-class. We provide a lower bound of $4.967$ on the competitive ratio of any such deterministic algorithm, and hence show that future improvements will have to store in memory a set of edges which is not necessarily a feasible matching. We conclude by presenting an empirical study, conducted in order to compare the practical performance of our approach to that of previously suggested algorithms.

• Publication year

  2009

• Venue

  SIAM Journal on Discrete Mathematics

• Publication date

  2009-07-02

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/100801901arXiv 0907.0305
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• I and J

  2012cited by this paper
• Weighted Matching in the Semi-Streaming Model

  2010cited by this paper
• Graph Distances in the Data-Stream Model

  2008cited by this paper
• Engineering Algorithms for Approximate Weighted Matching

  2007influential reference
• An O (log2 k )-Competitive Algorithm for Metric Bipartite Matching

  2007cited by this paper
• Weighted Matching in the Semi-Streaming Model

  2007influential reference
• Efficient algorithms for constructing (1+∊,β)-spanners in the distributed and streaming models

  2006cited by this paper
• Finding Graph Matchings in Data Streams

  2005influential reference
• Data streams: algorithms and applications

  2005cited by this paper
• On graph problems in a semi-streaming model

  2005influential reference
• Efficient algorithms for constructing (1+,ε, β)-spanners in the distributed and streaming models

  2004cited by this paper
• Combinatorial optimization. Polyhedra and efficiency.

  2003cited by this paper
• On Graph Problems in a Semi-streaming Model

  2003cited by this paper
• The 25th Annual

  2001cited by this paper
• Implementing weighted b-matching algorithms: towards a flexible software design

  1999cited by this paper
• Online computation and competitive analysis

  1998cited by this paper
• Efficient On-Line Call Control Algorithms

  1997cited by this paper
• Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem

  1996cited by this paper
• Eecient On-line Call Control Algorithms

  1993cited by this paper
• Online Weighted Matching

  1993cited by this paper
• On-Line Algorithms for Weighted Bipartite Matching and Stable Marriages

  1991cited by this paper
• An optimal algorithm for on-line bipartite matching

  1990cited by this paper
• Probabilistic computations: Toward a unified measure of complexity

  1977cited by this paper
• Schaum's Outline of Theory and Problems of Discrete Mathematics

  1976cited by this paper
• A and V

  1962cited by this paper

• Dynamic Algorithms for Submodular Matching

  2025cites this paper
• Semi-online models for cardinality constrained bin packing

  2025cites this paper
• Weighted Matching in a Poly-Streaming Model

  2025influential citation
• Streaming Matching and Edge Cover in Practice

  2024cites this paper
• An Improved Space Semi-Streaming Algorithm for Submodular Maximization under b-Matching Constraint

  2024cites this paper
• Weighted Matching in the Random-Order Streaming and Robust Communication Models

  2024cites this paper
• Semi-Streaming Algorithms for Weighted k-Disjoint Matchings

  2023cites this paper
• Online Coalition Formation under Random Arrival or Coalition Dissolution

  2023cites this paper
• A Batch-dynamic Suitor Algorithm for Approximating Maximum Weighted Matching

  2022cites this paper
• Closing the Gap between Weighted and Unweighted Matching in the Sliding Window Model

  2022cites this paper
• Improved Weighted Matching in the Sliding Window Model

  2022cites this paper
• Relative Worst-Order Analysis A Survey

  2021cites this paper
• Semi-Streaming Algorithms for Submodular Function Maximization under $b$-Matching Constraint

  2021cites this paper
• Maximum Matching Sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model

  2021cites this paper
• Maximum Coverage in the Data Stream Model: Parameterized and Generalized

  2021cites this paper
• Semi-streaming Algorithms for Submodular Function Maximization Under b-Matching, Matroid, and Matchoid Constraints

  2021cites this paper
• Optimal Streaming Algorithms for Graph Matching

  2021cites this paper
• Deterministic (1+ε)-Approximate Maximum Matching with poly(1/ε) Passes in the Semi-Streaming Model

  2021cites this paper
• Deterministic (1+𝜀)-approximate maximum matching with poly(1/𝜀) passes in the semi-streaming model and beyond

  2021cites this paper
• Data Stream Algorithms Lecture Notes

  2020cites this paper
• Semi-Streaming Bipartite Matching in Fewer Passes and Less Space

  2020cites this paper
• Substream-Centric Maximum Matchings on FPGA

  2020cites this paper
• Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms

  2020cites this paper
• Improved Bounds for Matching in Random-Order Streams

  2020cites this paper
• Substream-Centric Maximum Matchings on FPGA

  2019cites this paper
• Approximate Maximum Matching in Random Streams

  2019cites this paper
• A (2+ϵ)-Approximation for Maximum Weight Matching in the Semi-streaming Model

  2019cites this paper
• 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8-9, 2019, San Diego, CA, USA

  2019cites this paper
• Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

  2019cites this paper
• Distributed Weighted Matching via Randomized Composable Coresets

  2019cites this paper
• Massive Graph Analysis in the Data Stream Model

  2019cites this paper
• Maximum Matching on Trees in the Online Preemptive and the Incremental Graph Models

  2019influential citation
• Metric Sublinear Algorithms via Linear Sampling

  2018cites this paper
• David Wajc Matching Algorithms Under Uncertainty , and Matching Lower Bounds

  2018cites this paper
• Matroid Intersection : Beating Half for Random Arrival ⋆

  2018cites this paper
• Relative Worst-order Analysis

  2018cites this paper
• Combinatorial Optimization On Massive Datasets: Streaming, Distributed, And Massively Parallel Computation

  2018cites this paper
• Computational Explorations of Information and Mechanism Design in Markets

  2018cites this paper
• Simulating Random Walks on Graphs in the Streaming Model

  2018cites this paper
• 21st Century Algorithms Project Report

  2018cites this paper
• Structural Results on Matching Estimation with Applications to Streaming

  2018cites this paper
• Deterministic Algorithms for Maximum Matching on General Graphs in the Semi-Streaming Model

  2018cites this paper
• Simplified and Space-Optimal Semi-Streaming ( 2 + ε )-Approximate Matching

  2018cites this paper
• Access to Data and Number of Iterations

  2018cites this paper
• Allocations in Large Markets

  2017cites this paper
• Simplified and Space-Optimal Semi-Streaming for $(2+\epsilon)$-Approximate Matching

  2017cites this paper
• Improved bounds for randomized preemptive online matching

  2017influential citation
• Algorithms for Environments with Uncertainty

  2017cites this paper
• On Conceptually Simple Algorithms for Variants of Online Bipartite Matching

  2017cites this paper
• On Estimating Maximum Matching Size in Graph Streams

  2017cites this paper
• Randomized Composable Coresets for Matching and Vertex Cover

  2017cites this paper
• Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams

  2017cites this paper
• Space-Optimal Semi-Streaming for (2+ε)-Approximate Matching

  2017influential citation
• Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs

  2017cites this paper
• A (2 + ∊)-Approximation for Maximum Weight Matching in the Semi-Streaming Model

  2017cites this paper
• Maximum Matching in Two Passes, Three Passes, and a Few More Passes Over Graph Streams

  2017cites this paper
• Communication complexity of approximate maximum matching in the message-passing model

  2017cites this paper
• Relaxing the Irrevocability Requirement for Online Graph Algorithms

  2017cites this paper
• Maximum Matching in the Online Batch-arrival Model

  2017cites this paper
• Combinatorial Optimization Under Uncertainty ( Probing and Stopping-Time Algorithms )

  2017cites this paper
• Estimating Weighted Matchings in o(n) Space

  2016cites this paper
• Streaming Verification of Graph Properties

  2016cites this paper
• Planar Matching in Streams Revisited

  2016cites this paper
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams

  2016cites this paper
• Streaming Algorithms for Independent Sets in Sparse Hypergraphs

  2016cites this paper
• The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs

  2016cites this paper
• Maximum Matching on Trees in the Online Preemptive and the Incremental Dynamic Graph Models

  2016cites this paper
• Almost Optimal Streaming Algorithms for Coverage Problems

  2016cites this paper
• Streaming Weighted Matchings: Optimal Meets Greedy

  2016influential citation
• Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model

  2016cites this paper
• An Agent-Based Model of Competition Between Financial Exchanges: Can Frequent Call Mechanisms Drive Trade Away from CDAs?

  2016cites this paper
• Graph Sketches : Sparsification , Spanners , and Subgraphs

  2016cites this paper
• Communication Complexity of Approximate Matching in Distributed Graphs

  2015cites this paper
• Sublinear Estimation of Weighted Matchings in Dynamic Data Streams

  2015cites this paper
• Kernelization via Sampling with Applications to Dynamic Graph Streams

  2015cites this paper
• Maximum Matching in Turnstile Streams

  2015cites this paper
• Dimensionality reduction for sparse and structured matrices

  2015cites this paper
• Graph Sketches : Sparsification , Spanners , and Subgraphs

  2015cites this paper
• On graph algorithms for large-scale graphs

  2015cites this paper
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond

  2015cites this paper
• Tight Bounds for Linear Sketches of Approximate Matchings

  2015cites this paper
• Streaming Algorithms Via Reductions

  2014influential citation
• Automata, Languages, and Programming

  2014influential citation
• Semi-Streaming Set Cover - (Extended Abstract)

  2014cites this paper
• Improved Streaming Algorithms for Weighted Matching, via Unweighted Matching

  2014cites this paper
• Single Pass Spectral Sparsification in Dynamic Streams

  2014cites this paper
• Semi-Streaming Set Cover

  2014cites this paper
• Graph stream algorithms: a survey

  2014cites this paper
• Analyzing Massive Graphs in the Semi-streaming Model

  2013influential citation
• Fully Dynamic $(1+\epsilon)$-Approximate Matchings

  2013cites this paper
• Access to Data and Number of Iterations: Dual Primal Algorithms for Maximum Matching under Resource Constraints

  2013cites this paper
• Submodular maximization meets streaming: matchings, matroids, and more

  2013cites this paper
• Communication Complexity of Approximate Maximum Matching in Distributed Graph Data

  2013cites this paper
• Computations on Massive Data Sets : Streaming Algorithms and Two-party Communication. (Calculs sur des grosses données : algorithmes de streaming et communication entre deux joueurs)

  2013cites this paper
• On the Social Welfare of Mechanisms for Repeated Batch Matching

  2012cites this paper
• Space-Constrained Interval Selection

  2012cites this paper
• Open Questions from the Workshop on Algorithms for Data Streams 2012 at TU -

  2012cites this paper
• Graph sketches: sparsification, spanners, and subgraphs

  2012cites this paper
• Superlinear Lower Bounds for Multipass Graph Processing

  2012cites this paper
• Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs

  2012cites this paper