CS Events
PhD DefenseMatchings in Evolving Graphs |
|
||
Thursday, March 02, 2023, 08:30am - 10:30am |
|||
Abstract:
Traditionally, the matching problem has been studied in settings where the entire graph is a priori available to the algorithm. Several practical applications such as internet ad allocation, ride sharing, and task allocation have motivated the study of this problem in models where the graph is revealed in parts or is undergoing modifications. In this thesis, we study the matching problem in such evolving graph models:
1. Online Graphs with Bounded Recourse: In the online model, the graph, while fixed, is revealed to the algorithm adversarially, in the form of requests. The algorithm is required to respond to these requests immediately, and irrevocably. We study a variant of this model where the algorithm can revoke its decisions a bounded number of times. In this setting, we show upper and lower bounds on the recourse when the goal is to maintain an optimal matching. 2. Dynamic Graphs: In the dynamic graph model, the graph is undergoing modifications in the form of edge insertions and deletions. The algorithm must adapt to these changes with the goal of minimizing the work done to reoptimize the solution. We study the matching problem in partially and fully dynamic settings, and obtain efficient algorithms which maintain close to optimal solutions.Speaker: Aditi Dudeja
Location : CoRE 431
Committee:
Professor Aaron Bernstein (Chair)
Professor Jie Gao
Professor Sepehr Assadi
Professor Sayan Bhattacharya (University of Warwick)
Event Type: PhD Defense
Abstract: See above
Organization:
Rutgers University
School of Arts & Sciences
Department of Computer Science
Contact Professor Aaron Bernstein