Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem

DOI10.1007/978-3-642-22012-8_42zbMath1333.68291arXiv1104.2315OpenAlexW2788362138MaRDI QIDQ3012945

Sudipto Guha, Kook Jin Ahn

Publication date: 7 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items (8)

Finding Articulation Points of Large Graphs in Linear Time ⋮ Maximum Matching in Turnstile Streams ⋮ Superlinear lower bounds for multipass graph processing ⋮ Efficient Primal-Dual Graph Algorithms for MapReduce ⋮ Submodular maximization meets streaming: matchings, matroids, and more ⋮ Fractional Set Cover in the Streaming Model. ⋮ Unnamed Item ⋮ Unnamed Item

Uses Software

• AdaBoost.MH

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the fractional matching polytope of a hypergraph
• Towards a theoretical foundation for Laplacian-based manifold methods
• Maximum degree and fractional matchings in uniform hypergraphs
• A decision-theoretic generalization of on-line learning and an application to boosting
• Linear programming in the semi-streaming model with application to the maximum matching problem
• A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
• On graph problems in a semi-streaming model
• Approximating Fractional Multicommodity Flow Independent of the Number of Commodities
• A linear-time approximation algorithm for weighted matchings in graphs
• IMPROVED APPROXIMATION GUARANTEES FOR WEIGHTED MATCHING IN THE SEMI-STREAMING MODEL *
• Data Streams: Algorithms and Applications
• Graph Sparsification in the Semi-streaming Model
• Bipartite Graph Matchings in the Semi-streaming Model
• Graph Distances in the Data-Stream Model
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Maximum matching and a polyhedron with 0,1-vertices
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem