Essays on Discrete Optimization
by Xingyu Zhang
This thesis studies two discrete optimization problems: ordering problems in optimal stopping theory and popular matchings. The main goal of this thesis is to find the boundary between NP-hardness and tractability for these problems, and whenever possible, designs polynomial-time algorithms for the easy cases and approximation schemes or prophet inequalities for the hard cases. In the first part of the thesis, we study ordering problems in optimal stopping theory. In the optimal stopping problem, a player is presented with π random variables πβ, . . . , πn, whose distributions are known to the player, but not their realizations. After observing the realization of πα΅’, the player can choose to stop and earn reward πα΅’, or reject πα΅’ and probe the next variable πα΅’ββ. If πα΅’ is rejected, it cannot be accepted in the future. The goal of the player is to maximize the expected reward at stopping time. If the order of observation is fixed, the player can find the optimal stopping criteria using a dynamic program. In this thesis, we investigate the variant in which the player is able to choose the order of observation. What is the best ordering and what benefits does ordering bring? Ch
For young readers
Book data: Open Library