Phd Defense by Tung Mai

Event Details
  • Date/Time:
    • Thursday May 17, 2018
      12:30 pm - 2:00 pm
  • Location: Skiles 005
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact
No contact information submitted.
Summaries

Summary Sentence: Distributive Lattices, Stable Matchings, and Robust Solutions

Full Summary: No summary paragraph submitted.

Title: Distributive Lattices, Stable Matchings, and Robust Solutions

 

Tung Mai

Algorithms, Combinatorics and Optimization

School of Computer Science

Georgia Institute of Technology



Date and Time: Thursday, May 17th, 2018, 12:30 pm EST
Location: Skiles 005
Advisor: Dr. Vijay Vazirani, Department of Computer Science, University of California, Irvine

Committee:
Dr. Vijay Vazirani, Department of Computer Science, University of California, Irvine
Dr. Jugal Garg, Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana-Champaign
Dr. Milena Mihail, School of Computer Science, Georgia Institute of Technology
Dr. Mohit Singh, School of Industrial and Systems Engineering, Georgia Institute of Technology
Dr. Robin Thomas, School of Mathematics, Georgia Institute of Technology


Abstract:
The stable matching problem, first presented by mathematical economists Gale and Shapley, has been studied extensively since its introduction. As a result, a remarkably rich literature on the problem has accumulated in both theory and practice. We further extend our understanding on several algorithmic and structural aspects of stable matching. Our contributions can be summarized as follows:

- Generalizing stable matching to maximum weight stable matching.
- Finding stable matchings that are robust to shifts (a class of error introduced to the input).
- Generalizing Birkhoff's theorem for distributive lattices, and an application to robust stable matching on a larger class of error, namely permutations of any preference list of a boy or a girl.

The structural and algorithmic results introduced in this thesis naturally lead to a number of new questions. We believe that, considering the deep and pristine structure of stable matching, many of these questions do get settled satisfactorily.

 

Additional Information

In Campus Calendar
No
Groups

Graduate Studies

Invited Audience
Public, Graduate students, Undergraduate students
Categories
Other/Miscellaneous
Keywords
Phd Defense
Status
  • Created By: Tatianna Richardson
  • Workflow Status: Published
  • Created On: May 8, 2018 - 11:56am
  • Last Updated: May 15, 2018 - 8:57am