Chen, Q. (CSE) – New Approximation and Online Algorithms using Novel Combinatorial Structures
Most optimization problems face the challenge of computing an optimum solution requiring superpolynomial time. In particular, they are classified as NP-hard problems that have no polynomial-time algorithm to date. Instead, computer scientists turn to find an approximate solution and create numerous elegant algorithms. However, in the modern era, computational environments have changed drastically, and we are not able to afford to design new algorithms for each new problem via repeated trial and error. Therefore, systematic ways to understand the possibilities and limitations of these problems are desired. This dissertation studies several central combinatorial optimization problems, focusing on understanding the key structural obstacles and developing unified frameworks. Mainly, we study two types of combinatorial optimization problems:
(1) Scheduling. The problem is associated with limited resources, and our target is to find an allocation method to complete all jobs over time that minimizes the overall budget cost.
(2) Network Design. Different from scheduling problems. In this problem, we aim to find a minimum-cost topological network that supports routing for demanding communications.
Our first work is focused on a group-to-group survivable network design problem that generalizes the classic point-to-point network to support routing between any pair of subsets of nodes. Previous research stops at limited faults, and the difficulty comes from the way to compress the graph into a tree. We propose a new framework via capacitated tree embeddings against arbitrary faults in the network, which gives the first polylogarithmic approximation algorithm. Further, this framework captures nearly all the recent models proposed in the area.
In contrast to the offline optimization problems mentioned above, online algorithms are natural adaptations that have been found in tremendous real applications. In online algorithms, the algorithm wants to compete against arbitrary uncertainty, which means the instance is unknown at first and revealed over time. We study various scheduling problems and focus on some important metrics – average flow time, which measures the average time a job stays in the system from its arrival to completion. Real-world demands give online scheduling problems enormously different settings. Computer scientists need to repeat errors and trials to find a provably good solution. We find the key required combinatorial property is supermodularity for the residual objective, which measures the average completion time for all alive jobs assuming they have the same arrival time. Further, we relate supermodularity with gross-substitute/linear-
Event Host: Qingyun Chen, Ph.D. Student, Computer Science and Engineering
Advisor: Sungjin Im
Zoom- https://ucsc.zoom.us/j/
