Approximationsalgorithmen für Geometrische Optimierungsprobleme
Zusammenfassung der Projektergebnisse
Not all the problems that I defined in this grant were solved. As an example, one of the major problems which remained open was to understand and exploit the connections between streaming, sublinear and approximation algorithms not only in the context of geometric optimization problems, but in general for graph problems. We partially solved this problem. In particular we studied which property testing and sublinear time algorithms can be transformed into graph streaming algorithms for random order streams. Our main result was that for bounded degree graphs, any property that is constant-query testable in the adjacency list model can be tested with constant space in a single-pass in random order streams. Our result was obtained by estimating the distribution of local neighborhoods of the vertices on a random order graph stream using constant space. We then showed that our approach can also be applied to constant time approximation algorithms for bounded degree graphs in the adjacency list model: As an example, we obtained a constant-space single-pass random order streaming algorithms for approximating the size of a maximum matching with additive error n (n is the number of nodes). Our result established for the first time that a large class of sublinear algorithms can be simulated in random order streams, while Ω(n) space is needed for many graph streaming problems for adversarial orders.
Projektbezogene Publikationen (Auswahl)
- Brief Announcement: New Streaming Algorithms for Parameterized Maximal Matching and Beyond. SPAA 2015: 56-58
Rajesh Hemant Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Morteza Monemizadeh
(Siehe online unter https://doi.org/10.1145/2755573.2755618) - Parameterized Streaming: Maximal Matching and Vertex Cover. SODA 2015: 1234-1251
Rajesh Hemant Chitnis, Graham Cormode, Mohammad Taghi Hajiaghayi, Morteza Monemizadeh
(Siehe online unter https://doi.org/10.1137/1.9781611973730.82) - Prophet Secretary. ESA 2015: 496-508
Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh
(Siehe online unter https://doi.org/10.1007/978-3-662-48350-3_42) - Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond. SODA 2015: 1217-1233
Hossein Esfandiari, Mohammad Taghi Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh, Krzysztof Onak
(Siehe online unter https://doi.org/10.1145/3230819) - Clustering Problems on Sliding Windows. SODA 2016: 1374-1390
Vladimir Braverman, Harry Lang, Keith Levin, Morteza Monemizadeh
(Siehe online unter https://doi.org/10.1137/1.9781611974331.ch95) - Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams. SODA 2016: 1326-1344
Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, Sofya Vorotnikova
(Siehe online unter https://doi.org/10.1137/1.9781611974331.ch92) - Prophet Secretary. SIAM J. Discret. Math. 31(3): 1685-1701 (2017)
Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh
(Siehe online unter https://doi.org/10.1137/15M1029394)
