Collection Nexus Trimester - 2016 - Inference Problems Theme
Organizer(s)
Date(s)
28/04/2024
Approximating matchings in sublinear space
Finding maximum matchings in graphs is one of the most well-studied questions in combinatorial optimization. This problem is known to be solvable in polynomial time if the edge set of the graph can be loaded into memory. However, the sizes of data sets common in modern large data analysis often make this assumption unrealistic, calling for algorithms whose space requirements are sublinear in the size of the input that they operate on. An ideal algorithm would scan the list of edges of the input graph presented to it exactly once, maintain a small space representation of the stream seen so far at each point in time, and output a good approximation to the maximum matching at the end – such algorithms are referred to as single pass streaming algorithms. In this talk we will discuss streaming algorithms for approximating maximum matchings, and limitations that space constraints imply. On the lower bounds side, we will show that if the order in which the edges are presented to the algorithm is adversarial and the algorithm must output the edges of a nearly optimal matching at the end of the stream, a substantial amount of space (much larger than the number of bits needed to describe a solution) is required to obtain a good constant factor approximation in a single pass. On the algorithms side, will we show that if only an approximation to the size of the maximum matching (as opposed to finding the actual edges) is needed and the stream is presented in a random order, a surprisingly efficient algorithm exists.
