Approximation: A Paradigm for Designing Parallel Graph Algorithms

Speaker: Alex Pothen , Purdue University

Date: Monday, October 26, 2020

Time: 2:00 PM to 3:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: https://mit.zoom.us/meeting/register/tJUrdOqopj8uHdO4gUyVMnfglOFEqIye_Je0 (Registration required, if you haven't registered for this series before)

Event Type: Seminar

Room Description:

Host: Julian Shun, MIT CSAIL

Contact: Julian Shun, jshun@mit.edu, lindalynch@csail.mit.edu

Relevant URL: http://fast-code.csail.mit.edu/

Speaker URL: https://www.cs.purdue.edu/homes/apothen/

Speaker Photo:
None

Reminders to: fast-code-seminar@lists.csail.mit.edu, seminars@csail.mit.edu, pl@csail.mit.edu, commit@lists.csail.mit.edu, toc-students@csail.mit.edu, toc-postdocs@csail.mit.edu, toc-faculty@csail.mit.edu

Reminder Subject: TALK: Approximation: A Paradigm for Designing Parallel Graph Algorithms

We describe a paradigm for designing parallel algorithms on massive graphs by employing approximation techniques. Instead of solving a problem exactly, for which efficient parallel algorithms may not exist, we seek a solution with provable approximation guarantees via approximation algorithms. Furthermore, we design approximation algorithms with high degrees of concurrency. We show the computation of degree-constrained subgraphs as an example of this paradigm, and discuss a few exemplar matching and edge cover problems.

First, we discuss the vertex-weighted matching problem, a problem of interest in internet advertising, and describe a k/(k+1)-approximation algorithm based on finding short paths with specified properties in the graph (here k is related to the length of the path). Then we describe how a shared memory parallel algorithm could be obtained from it. Second, we will consider the edge-weighted b-matching problem, and describe a parallel ½-approximation algorithm, bSuitor, that scales to tens of thousands of cores. The b-Suitor algorithm is based on making proposals, and is similar to the classical algorithms for stable matching. Concepts from b-matching and primal-dual formulations can be used to design approximation algorithms for the related edge-weighted b-edge cover problem.

In all of these cases, we identify the "combinatorial structures" underlying the problem that lead to algorithmic insights. For vertex weighted matching, it is a matroid; for edge-weighted b-matching, it is a 2-extendible independence system; for b-edge cover, it is the complement of a b-matching.

We have applied our software for computing matchings and edge covers, MatchBox, to solve problems in data privacy, semi-supervised classification, load balancing in quantum chemistry computations, etc.

Short Bio: Alex Pothen is a professor of computer science at Purdue University. He received his undergraduate degree from the Indian Institute of Technology, Delhi, and a PhD from Cornell University in 1984. His research interests include combinatorial scientific computing (CSC), a research area where graph algorithms enable the solution of problems in computational science and engineering; parallel computing; and bioinformatics.

Alex led the formation of the CSC community within the Society for Industrial and Applied Mathematics (SIAM) in the early 2000’s, and currently serves as the Founding Chair of the SIAM Activity Group on Applied and Computational Discrete Algorithms.

Alex has mentored twenty PhD students, post-doctoral scientists and research faculty, who have gone on to successful careers at major research universities, the DOE Labs, and industry. He serves on the editorial board of the Journal of the ACM, and has served as an editor of SIAM Review, flagship journals of these societies. Alex is a Fellow of SIAM.

IMPORTANT NOTE FOR ATTENDEES: If you have already registered for the Fast Code Seminars on Zoom since July 27, 2020, please use the Zoom link that you have received. This link will stay the same for subsequent Fast Code seminars this semester. Zoom does not recognize a second registration, and will not send out the link a second time. If you have any problems with registration, please contact jshun@mit.edu and lindalynch@csail.mit.edu by 1:30pm on the day of the seminar, so that we can try to resolve it before the seminar begins.

Research Areas:
Algorithms & Theory, Programming Languages & Software

Impact Areas:
Big Data

See other events that are part of the Fast Code 2020 - 2021.

Created by Julian J. Shun at Tuesday, October 20, 2020 at 5:33 PM.