CS Events

PhD Defense

Matchings in Evolving Graphs

 

Download as iCal file

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