Linear programming in the semi-streaming model with application to the maximum matching problem
Authors:
- Kook Jin AhnKAKook Jin Ahn
- Sudipto GuhaSGSudipto Guha
- 1 January 2013
- journal article
- Published by Elsevier in Information and Computation
- Vol. 222, 59-79
Abstract
No abstract availableAll Related Versions
This publication has 23 references indexed in Scilit:
- Towards a theoretical foundation for Laplacian-based manifold methodsJournal of Computer and System Sciences, 2008
- On graph problems in a semi-streaming modelTheoretical Computer Science, 2005
- A linear-time approximation algorithm for weighted matchings in graphsACM Transactions on Algorithms, 2005
- Data Streams: Algorithms and ApplicationsFoundations and Trends® in Theoretical Computer Science, 2005
- A simpler linear time 2/3−ε approximation for maximum weight matchingInformation Processing Letters, 2004
- A Decision-Theoretic Generalization of On-Line Learning and an Application to BoostingJournal of Computer and System Sciences, 1997
- On the fractional matching polytope of a hypergraphCombinatorica, 1993
- Short proofs on the matching polyhedronJournal of Combinatorial Theory, Series B, 1983
- Maximum matching and a polyhedron with 0,1-verticesJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965
- A Short Proof of the Factor Theorem for Finite GraphsCanadian Journal of Mathematics, 1954