Academic Events

PhD Dissertation Defense: Nairen Cao

Name: PhD Dissertation Defense: Nairen Cao
Start: 2022-07-08T14:00:00-04:00
End: 2022-07-08T16:00:00-04:00
Location: 326 St. Mary’s Hall

Title: Single-source Shortest Paths for Digraphs

We study directed Single Source Shortest paths (SSSP) problem in the parallel and distributed model. Consider an n-vertex m-edge directed graph G, we present a series of efficient randomized algorithms with theoretical guarantees. Several results are listed as follows:

For graph with non-negative real-weight edges, we solve (1+ε)-approximate SSSP problem with n^{2/5 + o(1)} D^{2/5} + sqrt(n) + D rounds in the CONGEST and Broadcast CONGEST model
For graph with non-negative integer edge weights, we solve exact SSSP problem with Õ(m) work and sqrt(L) n^{1/2 + o(1)} in work-span model, where L is the maximum shortest path length.
For graph with non-negative integer edge weights, we solve exact SSSP problem with Õ(m) work and n^{1/2 + o(1)} span in work-span model.
For graph with non-negative integer edge weights, we solve exact SSSP problem with O(n^{2/5 + o(1)} D^{2/5} + sqrt(n) + D) rounds in the CONGEST and Broadcast CONGEST model.

In addition, we also consider the active-time scheduling problem, which schedules preemptible jobs with windows (release times and deadlines) on a parallel machine that can schedule up to g jobs during each timestep. The goal in the active-time problem is to minimize the number of active steps, i.e., timesteps in which at least one job is scheduled. This thesis also presents a 9/5-approximation algorithm for a special case of the active-time scheduling problem in which job windows are laminar (nested). This result improves on the previous best 2-approximation for the general case.