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?
Chapter 2 introduces the optimal ordering problem in optimal stopping theory. We prove that the problem of finding an optimal ordering is NP-hard even in very restricted cases where the support of each distribution has support on at most three points. Next, we prove an FPTAS for the hardness case and provide a tractable algorithm and a prophet inequality for two-point distributions. Chapter 3 studies the optimal ordering problem when the player can choose ๐ > 1 rewards before stopping. We show that finding an optimal static ordering is NP-hard even for very simple two-point distributions. Next, we prove an FPTAS for the hardness case and give prophet inequalities under static and dynamic policies for two-point distributions.
In the second part of the thesis, we study popular matchings. Suppose we are given a bipartite graph with independent sets ๐จ and ๐ต. Each vertex in ๐จ has a ranked order of preferences on the vertices in ๐ต, and vice versa. A matching ๐ด is popular if for any other matching ๐ดโฒ, the number of vertices that prefer ๐ด is at least as much as the number of vertices that prefer ๐ดโฒ.
Chapter 4 studies popular matchings. In the first part, we provide a general reduction which, through minor adjustments, proves NP-Hardness for a variety of different questions, including that of finding a max-weight popular matching. In the second part, we restrict our attention to graphs of bounded treewidth and provide a tractable algorithm for finding a max-weight popular matching.
| Identifer | oai:union.ndltd.org:columbia.edu/oai:academiccommons.columbia.edu:10.7916/dawc-4e11 |
| Date | January 2022 |
| Creators | Zhang, Xingyu |
| Source Sets | Columbia University |
| Language | English |
| Detected Language | English |
| Type | Theses |
Page generated in 0.0025 seconds