A Simple (1−eps)-Approximation Adaptive Sketching Algorithm for Maximum (Weighted) Matching
summary
Presents a concrete algorithm that achieves a (1−ε)-approximation for weighted matching in general (non‑bipartite) graphs using O(log n / ε) rounds of adaptive sketching, matching best known bounds while being much simpler. It repeatedly samples ~n/ε edges, computes a dual (vertex cover or odd‑set cover), and boosts uncovered edges by doubling their sampling weight, a multiplicative weight update style primal–dual method. Analysis bounds total weight growth and forces termination in the claimed rounds; it extends to deterministic streaming variants.
AI-written summary · about