Theses Doctoral

Discrete Optimization Problems in Popular Matchings and Scheduling

Powers, Vladlena

This thesis focuses on two central classes of problems in discrete optimization: matching and scheduling. Matching problems lie at the intersection of different areas of mathematics, computer science, and economics. In two-sided markets, Gale and Shapley's model has been widely used and generalized to assign, e.g., students to schools and interns to hospitals. The goal is to find a matching that respects a certain concept of fairness called stability. This model has been generalized in many ways. Relaxing the stability condition to popularity allows to overcome one of the main drawbacks of stable matchings: the fact that two individuals (a blocking pair) can prevent the matching from being much larger. The first part of this thesis is devoted to understanding the complexity of various problems around popular matchings. We first investigate maximum weighted popular matching problems. In particular, we show various NP-hardness results, while on the other hand prove that a popular matching of maximum weight (if any) can be found in polynomial time if the input graph has bounded treewidth. We also investigate algorithmic questions on the relationship between popular, stable, and Pareto optimal matchings. The last part of the thesis deals with a combinatorial scheduling problem arising in cyber-security. Moving target defense strategies allow to mitigate cyber attacks. We analyze a strategic game, PLADD, which is an abstract model for these strategies.


  • thumnail for Powers_columbia_0054D_15841.pdf Powers_columbia_0054D_15841.pdf application/pdf 1.3 MB Download File

More About This Work

Academic Units
Industrial Engineering and Operations Research
Thesis Advisors
Faenza, Yuri
Ph.D., Columbia University
Published Here
July 6, 2020