- Online Maximum Weight Bipartite Matchings with Recourse
- Project Year:
2019
- REU Student (s):
Shyamal Patel | Georgia Institute of Technology-Main Campus GA
- Student 1 Institution:
Georgia Institute of Technology-Main Campus
- Project Mentor:
Aaron Bernstein
- Project Mentor Area:
Computer Science
- Project Abstract:
We consider the problem of maintaining a maximum weight matching in the online setting with small recourse. The servers are known in advance, and clients come in one at a time with all of their weighted edges. We consider doing this both exactly and approximately. In the exact case, we show an upper bound that differs from the lower bound by only logarithmic factors. The upper bound is proved by a reduction to the problem in the unweighted setting. We also address solving the problem approximately and show that we can use O(1) amortized recourse to maintain a 2 + ε approximate solution.
