Approximation Algorithms for Clustering and Vehicle Routing

点击翻译按钮获取中文摘要

Challenging optimization problems appear in many aspects of our society. For example, how should one schedule a fleet of vehicles to deliver thousands of packages in a day? How can we allocate hundreds of courses to various classrooms on campus while respecting a number of auxiliary constraints such as avoiding overlap between courses that are likely to be taken by the same students? How can we place components on a circuit board and connect them via wires while keeping the entire board as small as possible? Further challenges are easy to find in many other subjects: airport scheduling, data clustering, medical testing, mobile aid station placement, etc. Poor solutions can sometimes result in millions of dollars lost. Many of these problems are so large that we rely on algorithms to find their solutions. Unfortunately, the models we use to address these problems are provably hard; being able to efficiently find the optimum solution with an algorithm would yield an unexpected resolution to the fundamental P vs. NP problem in computing science. Despite this barrier, we still need to address these important problems. To cope with this difficulty, I design approximation algorithms for hard optimization problems. These are efficient algorithms that find near-optimal solutions. This is not a mere heuristic statement, such algorithms also come with a proof that the cost of solutions they produce are within some bounded error of the best possible solution's cost. With such an approach, we have confidence that the algorithms we design are guaranteed to perform well when used on data sets that may not have been considered when the algorithm was designed. This research focuses on two very common classes of problems: data clustering and vehicle routing. Data clustering is used to support the results in hundreds of research papers every year with applications stemming from data mining, machine learning, image processing, statistical analysis, big data visualization, etc. Other applications include operations research, for example when we want to place distribution centres to serve clients in a cost-effective manner. The algorithms that are used in practice typically work well, but are known to perform poorly in certain instances. My work will focus on designing improved approximations for clustering models that, provably, work well in every instance of the problem. I am also interested in articulating, from a fundamental point of view, why certain algorithms perform better than their worst-case guarantees on "real-world" data. My work on vehicle routing will focus on improving service times and operating costs by designing improved approximations for some fundamental models beyond the well-known Traveling Salesperson Problem. Further, how do solutions to these models relate? How can solving one vehicle routing problem provide better approximation algorithms for other models?