Department of Computational and Data Sciences
Department Seminar
Speaker : Prof. Alex Pothen, Purdue University
Title : “Matchings in Big Graphs: Approximation and Streaming Algorithms”
Date & Time : December 22, 2023, 11:00 AM
Venue : # 102, CDS Seminar Hall
ABSTRACT
Matchings in graphs are classical problems in combinatorial optimization and computer science, significant due to their theoretical importance and relevance to applications. Polynomial time algorithms for several variant matching problems with linear objective functions have been known for fifty years. However, these algorithms fail to compute matchings in big graphs with billions of edges. They are also not concurrent and thus practical parallel algorithms are not known.
This has led to work in the last twenty years on designing approximation algorithms for variant matching problems with near-linear time complexity in the size of the graphs. Approximation has thus become a useful paradigm for designing parallel matching algorithms. In this talk I will report on fast approximation algorithms and streaming algorithms for the maximization versions of edge-weighted matching, edge-weighted b-matching, and the maximum k-disjoint weighted matching problems. We will also describe applications to aircraft design, traffic routing in data centers and load balancing in quantum chemistry.
BIOGRAPHY
Alex Pothen is a professor of computer science at Purdue University. His research interests are in combinatorial scientific computing, graph algorithms and parallel computing. He received the George Polya prize in applied combinatorics from the Society for Industrial and Applied Mathematics (SIAM) in 2021 for his work on graph coloring algorithms to enable Jacobian and Hessian matrix computations for optimization. He is a Fellow of SIAM, ACM and AMS.
Host Faculty: Prof. Sashikumaar Ganesan
ALL ARE WELCOME
