Efficient Algorithms for Combinatorial Optimization Problems in Networks and Beyond

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

• 批准号: RGPIN-2017-03956
• 负责人: Koenemann, Jochen
• 金额: $ 3.06万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=655795
• 关键词: 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-Hard问题中)，但在过去的5-10年里已经取得了令人印象深刻的进展(例子可以在Byrka等人关于Steiner树的可逼近性的工作[J.ACM，2013年]中找到，或者Sebo和Vygen关于在图形度量中近似TSP的工作[Combinatorica，2014])。领域(2)研究自私和战略行为在网络环境中的影响。和以前一样，这个领域包含了许多著名的结果，如纳什关于讨价还价的著名著作[Economrica，1950]，Shapley&Shubik对合作匹配博弈的研究[Int.J.博弈论，1971]，以及由于Kleinberg&Tardos[STEC，2008]，前两个结果在算法上的扩展到网络环境。对于这些领域中的每一个，我将概述适合研究生的短期和中期研究目标，这些目标的解决将使我朝着我议程中提议的长期目标取得进展。*虽然本提案的大部分集中在CO的理论方面，但所描述的技术具有重大的实践影响。这里讨论的一些问题是在与行业合作伙伴直接合作时出现的。因此，获得理论结果的有效实施是我研究的重点。