Approximation Algorithms for Clustering and Vehicle Routing

聚类和车辆路径的近似算法

• 批准号: RGPIN-2020-04043
• 负责人: Friggstad, Zachary
• 金额: $ 3.5万
• 依托单位: University of Alberta
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=716782
• 关键词: Approximation; Algorithms; Clustering; 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?

具有挑战性的优化问题出现在我们社会的许多方面。例如，应该如何安排一支车队在一天内递送数千个包裹？我们如何在尊重一些辅助限制的同时，将数百门课程分配给校园内的不同教室，例如避免同一学生可能上的课程之间的重叠？我们如何将元件放置在电路板上并通过导线连接它们，同时使整个电路板尽可能小？在许多其他学科中也很容易发现进一步的挑战：机场调度、数据集群、医疗测试、移动救援站布置等。糟糕的解决方案有时可能导致数百万美元的损失。 这些问题中的许多都是如此之大，以至于我们依靠算法来找到它们的解决方案。不幸的是，我们用来解决这些问题的模型被证明是困难的；能够用算法有效地找到最优解将产生计算科学中基本的P对NP问题的意外解决。尽管存在这一障碍，我们仍然需要解决这些重要问题。 为了克服这一困难，我设计了求解困难优化问题的近似算法。这些算法效率很高，可以找到接近最优的解决方案。这不仅仅是一个启发式的陈述，这样的算法还提供了一个证据，证明它们产生的解的成本在最佳可能解的成本的有界误差范围内。有了这样的方法，我们相信我们设计的算法在用于可能在设计算法时没有考虑到的数据集时能够很好地执行。 这项研究集中在两类非常常见的问题：数据聚类和车辆路径。数据集群每年被用来支持数百篇研究论文的结果，应用程序来自数据挖掘、机器学习、图像处理、统计分析、大数据可视化等。其他应用程序包括运筹学，例如当我们想要以具有成本效益的方式建立配送中心为客户服务时。实践中使用的算法通常工作得很好，但已知在某些情况下表现不佳。我的工作将集中于为集群模型设计改进的近似，可以证明，这些模型在问题的每一个实例中都工作得很好。我还感兴趣的是，从根本上讲，为什么某些算法在“真实世界”数据上的表现要好于它们在最坏情况下的保证。 我在车辆路径方面的工作将集中在通过为一些基本模型设计改进的近似来改善服务时间和运营成本，而不是众所周知的旅行推销员问题。此外，这些模型的解决方案有何关联？一个车辆路径问题的求解如何为其他模型提供更好的近似算法？