Efficient Algorithms for Combinatorial Optimization Problems in Networks and Beyond

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

• 批准号: RGPIN-2017-03956
• 负责人: Koenemann, Jochen
• 金额: $ 3.06万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=688457
• 关键词: 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.博弈论，1971]，以及Kleinberg和Tardos将前两个结果扩展到网络环境的最新算法[STOC， 2008]。对于这些领域中的每一个，我将概述适合研究生的短期和中期研究目标，这些目标的解决将使我能够朝着我议程中提出的长期目标取得进展。******虽然本建议的大部分内容侧重于CO的理论方面，但所描述的技术具有重要的实际影响。这里讨论的一些问题是在与工业伙伴的直接合作中产生的。因此，如何有效地实现理论成果是我研究的重点。