Computer Science Thesis Proposal
- Gates Hillman Centers
- Reddy Conference Room 4405
- COLIN WHITE
- Ph.D. Student
- Computer Science Department
- Carnegie Mellon University
Beyond Worst-Case Analysis in Combinatorial Optimization
Traditionally, the theory of algorithms has focused on the analysis of worst-case instances. While this has led to a thorough understanding of a wide variety of problems, there are many problems for which worst-case analysis is not useful for empirical or real-world instances. A rapidly developing line of research, the so-called beyond worst-case analysis of algorithms, considers the design and analysis of problems using more realistic models or using natural structural properties. In this thesis, we continue this line of work by making contributions in several areas. Specifically, we focus on three main problems.
i) Clustering has benefitted greatly from beyond worst-case analysis. Using the perturbation resilience assumption proposed by Bilu and Linial (2011), we design robust, efficient algorithms that output near-optimal clusterings on the stable parts of the data. We consider center-based objectives such as k-median and k-means, as well as symmetric and asymmetric k-center.
ii) An algorithm's performance may vary drastically between two applications. We consider the algorithm configuration problem for clustering, in which a clustering application is represented by a distribution over problem instances, and the goal is to find a near-optimal algorithm for the (unknown) distribution by taking a random sample. We define rich, infinite classes of clustering algorithms, and then show efficient meta-algorithms for algorithm configuration.
iii) We give a data-dependent dispatching algorithm for distributed machine learning, which takes advantage of the fact that similar data points often belong to the same or similar classes. We provide a new dispatching algorithm which casts this problem as clustering with balance and fault-tolerant constraints. Finally, we provide general and robust distributed clustering algorithms under worst-case and beyond worst-case analysis.
Maria-Florina Balcan (Chair)
Avrim Blum (Toyota Technical Institute of Chicago)
Yury Makarychev (Toyota Technical Institute of Chicago)
Copy of Thesis Summary