Efficient Algorithms for Combinatorial Optimization Problems in Networks and Beyond

网络及其他领域组合优化问题的有效算法

• 批准号: RGPIN-2017-03956
• 负责人: Koenemann, Jochen
• 金额: $ 6.12万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=749569
• 关键词: Efficient; Algorithms; Combinatorial; Optimization; Problems

Combinatorial optimization problems arise in many areas of everyday life where one needs to distribute scarce resources in a utility-maximizing fashion. Practical instances of relevant problems tend to be NP-hard, and are therefore likely intractable. This proposal focuses on the design of approximation algorithms as one way of addressing the intractability. Such algorithms are efficient and produce solutions whose quality is provably close to that of optimal solutions. In this proposal we focus on the rich subclass of discrete optimization problems that, interpreted broadly, arise in a network context. The long term goal of the proposed research program is to develop versatile and efficient techniques for the design of (approximation-) algorithms for problems in this class.The work proposed here naturally continues my existing research program. Research questions proposed focus mostly on two vibrant areas: (1) Approximate Network Design, and (2) Games in Networks. A typical optimization problem in (1) asks for a minimum-cost sub-graph of a given weighted network that satisfies certain connectivity requirements. This general model captures many classical examples (e.g., from Karp's original list of 21 NP-hard problems), and yet, impressive progress has been made over the last 5-10 years (examples can be found in Byrka et al.'s work on the approximability of the Steiner tree [J. ACM, 2013], or that of Sebo and Vygen on approximating TSP in graphic metrics [Combinatorica, 2014]). Area (2) studies the impact of selfish and strategic behaviour in a network context. As before, the area contains many celebrated results, like Nash's famous work on bargaining [Econometrica, 1950], Shapley & Shubik's study of the cooperative matching game [Int. J. Game Theory, 1971], and the more recent algorithmic extension of the previous two results to the network context due to Kleinberg & Tardos [STOC, 2008]. For each of these areas, I will outline short- and medium-term research goals that are appropriate for graduate students and whose resolution will allow me to make progress towards the proposed long-term goal of my agenda.While much of this proposal focuses on theoretical aspects of CO, the techniques described have significant practical impact. Some of the problems discussed here arose in direct collaboration with industrial partners. Thus, obtaining efficient implementations of theoretical results is a priority of my research.

组合优化问题出现在日常生活的许多领域，人们需要以效用最大化的方式分配稀缺资源。相关问题的实际实例往往是 NP 困难的，因此可能很棘手。该提案侧重于近似算法的设计，作为解决棘手问题的一种方法。此类算法非常高效，并且产生的解决方案的质量可证明接近最优解决方案的质量。在本提案中，我们重点关注离散优化问题的丰富子类，这些问题从广义上讲是在网络环境中出现的。所提出的研究计划的长期目标是开发通用且有效的技术来设计此类问题的（近似）算法。这里提出的工作自然地延续了我现有的研究计划。提出的研究问题主要集中在两个充满活力的领域：（1）近似网络设计，（2）网络游戏。 (1) 中的典型优化问题要求给定加权网络的最小成本子图满足某些连接要求。这个通用模型捕获了许多经典示例（例如，来自 Karp 的 21 个 NP 难问题的原始列表），然而，在过去 5-10 年中已经取得了令人印象深刻的进展（示例可以在 Byrka 等人的工作中找到）关于 Steiner 树的近似性 [J. ACM，2013]，或 Sebo 和 Vygen 关于图形度量中 TSP 的近似性 [Combinatorica， 2014]）。领域（2）研究网络环境中自私和战略行为的影响。和以前一样，该领域包含许多著名的成果，例如纳什关于讨价还价的著名著作 [Econometrica，1950]、Shapley 和 Shubik 对合作匹配博弈的研究 [Int. J. Game Theory, 1971]，以及 Kleinberg & Tardos [STOC, 2008] 将前两个结果扩展到网络上下文的最新算法。对于每个领域，我将概述适合研究生的短期和中期研究目标，其解决方案将使我能够在实现议程中拟议的长期目标方面取得进展。虽然本提案的大部分内容集中于CO 的理论方面，所描述的技术具有重大的实际影响。这里讨论的一些问题是在与工业合作伙伴的直接合作中产生的。因此，获得理论结果的有效实现是我研究的首要任务。