On the public citation graph

A (2+ϵ)-Approximation for Maximum Weight Matching in the Semi-streaming Model

0 signed · 48 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.

Claim with ORCID

Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.

See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/11538462_15openalex-snapshot

Finding Graph Matchings in Data Streams

inferredcites →https://doi.org/10.1007/978-3-319-07557-0_18openalex-snapshot

Submodular Maximization Meets Streaming: Matchings, Matroids, and More

inferredcites →https://doi.org/10.1007/978-3-642-40450-4_29openalex-snapshot

Dynamic Graphs in the Sliding-Window Model

inferredcites →https://doi.org/10.1007/978-3-662-48350-3_23openalex-snapshot

Sublinear Estimation of Weighted Matchings in Dynamic Data Streams

inferredcites →https://doi.org/10.1007/978-3-662-48350-3_70openalex-snapshot

Maximum Matching in Turnstile Streams

inferredcites →https://doi.org/10.1007/s00453-010-9438-5openalex-snapshot

Weighted Matching in the Semi-Streaming Model

inferredcites →https://doi.org/10.1016/j.tcs.2005.09.013openalex-snapshot

On graph problems in a semi-streaming model

inferredcites →https://doi.org/10.1016/s0304-0208(08)73101-3openalex-snapshot

A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem

inferredcites →https://doi.org/10.1109/sfcs.1980.12openalex-snapshot

An O(v|v| c |E|) algoithm for finding maximum matching in general graphs

inferredcites →https://doi.org/10.1137/1.9781611974782.113openalex-snapshot

On Estimating Maximum Matching Size in Graph Streams

inferredcites →https://doi.org/10.1137/100801901openalex-snapshot

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

inferredcites →https://doi.org/10.1145/1041680.1041683openalex-snapshot

Local ratio

inferredcites →https://doi.org/10.1145/1989493.1989505openalex-snapshot

Filtering

inferredcites →https://doi.org/10.1145/502102.502107openalex-snapshot

A unified approach to approximating resource allocation and scheduling

inferredcites →https://doi.org/10.4153/cjm-1965-045-4openalex-snapshot

Paths, Trees, and Flowers

inferredcites →https://doi.org/10.5555/2627817.2627938openalex-snapshot

Better bounds for matchings in the streaming model

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/s00453-018-0449-yopenalex-snapshot

Structural Results on Matching Estimation with Applications to Streaming

inferred← citeshttps://doi.org/10.1007/s00453-023-01190-4openalex-snapshot

Maximum Matching Sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model

inferred← citeshttps://doi.org/10.1007/s00453-024-01272-xopenalex-snapshot

Semi-streaming Algorithms for Submodular Function Maximization Under b-Matching, Matroid, and Matchoid Constraints

inferred← citeshttps://doi.org/10.1007/s10107-022-01858-9openalex-snapshot

Semi-streaming algorithms for submodular matroid intersection

inferred← citeshttps://doi.org/10.1016/j.ic.2017.12.002openalex-snapshot

Improved bounds for randomized preemptive online matching

inferred← citeshttps://doi.org/10.1109/focs46700.2020.00040openalex-snapshot

Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms

inferred← citeshttps://doi.org/10.1137/1.9781611974782.140openalex-snapshot

A (2 + ∊)-Approximation for Maximum Weight Matching in the Semi-Streaming Model

inferred← citeshttps://doi.org/10.1137/1.9781611975482.98openalex-snapshot

Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs

inferred← citeshttps://doi.org/10.1137/1.9781611975994.107openalex-snapshot

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

inferred← citeshttps://doi.org/10.1137/1.9781611975994.108openalex-snapshot

Approximate Maximum Matching in Random Streams

inferred← citeshttps://doi.org/10.1137/1.9781611976465.112openalex-snapshot

Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model

inferred← citeshttps://doi.org/10.1137/1.9781611976465.114openalex-snapshot

Streaming Submodular Matching Meets the Primal-Dual Method

inferred← citeshttps://doi.org/10.1137/1.9781611976496.17openalex-snapshot

Communication Efficient Coresets for Maximum Matching

inferred← citeshttps://doi.org/10.1137/1.9781611977073.29openalex-snapshot

Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space

inferred← citeshttps://doi.org/10.1145/3210377.3210386openalex-snapshot

Greedy and Local Ratio Algorithms in the MapReduce Model

inferred← citeshttps://doi.org/10.1145/3289602.3293916openalex-snapshot

Substream-Centric Maximum Matchings on FPGA

inferred← citeshttps://doi.org/10.1145/3293611.3331603openalex-snapshot

Weighted Matchings via Unweighted Augmentations

inferred← citeshttps://doi.org/10.1145/3357713.3384258openalex-snapshot

Rounding dynamic matchings against an adaptive adversary

inferred← citeshttps://doi.org/10.1145/3469834openalex-snapshot

Smaller Cuts, Higher Lower Bounds

inferred← citeshttps://doi.org/10.1145/3519935.3520016openalex-snapshot

Deterministic graph coloring in the streaming model

inferred← citeshttps://doi.org/10.1145/3797905.3800555openalex-snapshot

DistroMatch: Distributed Disjoint Weighted Matchings in Demand-Aware Reconfigurable Optical Datacenters

inferred← citeshttps://doi.org/10.3929/ethz-b-000374042openalex-snapshot

Simplified and Space-Optimal Semi-Streaming (2+epsilon)-Approximate Matching

inferred← citeshttps://doi.org/10.48550/arxiv.1702.02559openalex-snapshot

Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams

inferred← citeshttps://doi.org/10.48550/arxiv.1702.08299openalex-snapshot

Independent Set Size Approximation in Graph Streams

inferred← citeshttps://doi.org/10.48550/arxiv.1705.08242openalex-snapshot

Randomized Composable Coresets for Matching and Vertex Cover

inferred← citeshttps://doi.org/10.48550/arxiv.1807.09302openalex-snapshot

Metric Sublinear Algorithms via Linear Sampling

inferred← citeshttps://doi.org/10.48550/arxiv.1808.10650openalex-snapshot

Graph reduction with spectral and cut guarantees

inferred← citeshttps://doi.org/10.48550/arxiv.2002.12856openalex-snapshot

Two Player Hidden Pointer Chasing and Multi-Pass Lower Bounds in Turnstile Streams

inferred← citeshttps://doi.org/10.48550/arxiv.2005.00417openalex-snapshot

Improved Bound for Matching in Random-Order Streams

inferred← citeshttps://doi.org/10.48550/arxiv.2005.11116openalex-snapshot

Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams

inferred← citeshttps://doi.org/10.48550/arxiv.2102.06939openalex-snapshot

Optimal Streaming Algorithms for Graph Matching

inferred← citeshttps://doi.org/10.48550/arxiv.2108.07187openalex-snapshot

A Two-Pass Lower Bound for Semi-Streaming Maximum Matching

Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.