| The advent of big data necessitated design of algorithms that could cope with it. Streaming algorithms process their input sequentially and use a small amount of working memory, which makes them viable for big data. Massive graphs such as social-network graphs fall under the domain of big data. A matching in a graph is a subset of edges such that each vertex has at most one edge incident to it. Matching problems have played a significant historical role in combinatorial optimization; we consider them in the streaming model. First, we give improved approximation algorithms for the maximum matching problem that go over their input a small number of times. Next, we study the problem that we call maximum submodular matching, where the input is a graph with a submodular function defined on subsets of edges, and we want to find a matching with large function value. Submodular functions are set functions that capture the diminishing returns property and generalize linear (modular) functions. We are the first to consider this problem in the streaming model. Finally, we study the problem of estimating the size of a maximum matching (as opposed to computing a matching); we show a tight trade-off between estimation quality and the space used. We also show that such a trade-off, in fact, applies to problems related to the estimation of input statistics. Inspired by these proofs, we introduce an abstract paradigm for studying such lower bounds. |
