scientific article; zbMATH DE number 7053293

zbMath1421.68130MaRDI QIDQ5743414

Sanjeev Khanna, Michael Kapralov, Ashish Goel

Publication date: 10 May 2019

Full work available at URL: https://dl.acm.org/citation.cfm?id=2095157

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items (18)

The Densest $k$-Subhypergraph Problem ⋮ Superlinear lower bounds for multipass graph processing ⋮ New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory ⋮ Submodular maximization meets streaming: matchings, matroids, and more ⋮ Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model ⋮ Unnamed Item ⋮ New bounds for the CLIQUE-GAP problem using graph decomposition theory ⋮ Unnamed Item ⋮ Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams ⋮ A simple augmentation method for matchings with applications to streaming algorithms ⋮ On extensions of the deterministic online model for bipartite matching and max-sat ⋮ Structural results on matching estimation with applications to streaming ⋮ Unnamed Item ⋮ On conceptually simple algorithms for variants of online bipartite matching ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Optimal lower bounds for matching and vertex cover in dynamic graph streams ⋮ The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On graph problems in a semi-streaming model
• Random Sampling in Cut, Flow, and Network Design Problems
• Approximate majorization and fair online load balancing
• Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem
• Monotonicity testing over general poset domains
• Bipartite Graph Matchings in the Semi-streaming Model
• Simple analysis of graph tests for linearity and PCP
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Fairness in routing and load balancing

This page was built for publication: