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）中的典型优化问题要求给定加权网络的最小成本子图满足某些连通性要求。这个通用模型捕捉了许多经典的例子（例如，从卡普的原始清单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]。对于每一个领域，我将概述适合研究生的短期和中期研究目标，这些目标的解决方案将使我能够朝着我的议程中提出的长期目标取得进展。这里讨论的一些问题是与工业伙伴直接合作产生的。因此，获得有效的理论成果的实施是我的研究的优先事项。