Approximationsalgorithmen für Geometrische Optimierungsprobleme

• Antragsteller: Dr. Morteza Monemizadeh
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2013 bis 2016
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 228173343

• Erstellungsjahr: 2021

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
  
• Parameterized Streaming: Maximal Matching and Vertex Cover. SODA 2015: 1234-1251
  Rajesh Hemant Chitnis, Graham Cormode, Mohammad Taghi Hajiaghayi, Morteza Monemizadeh
  
• Prophet Secretary. ESA 2015: 496-508
  Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh
  
• 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
  
• Clustering Problems on Sliding Windows. SODA 2016: 1374-1390
  Vladimir Braverman, Harry Lang, Keith Levin, Morteza Monemizadeh
  
• 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
  
• Prophet Secretary. SIAM J. Discret. Math. 31(3): 1685-1701 (2017)
  Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh