Efficiency Tradeoffs for Combinatorial Optimization Problems

理论计算机科学的基本课题之一是研究资源有限时的计算能力。事实上，许多现实生活中的优化问题承认容易描述和非有效的算法解决方案，如果一个假设无限的计算能力，例如没有时间限制，并充分协调参与进程。当一个人被限制在有限的资源上使用有效的算法时，这样的问题能得到多大的解决？ 当有限的资源是时间，即计算步骤的数量时，理论计算机科学提供了丰富的问题分类，主要基于深度和未解决的数学问题。根据这些假设，一大群组合优化问题不能被精确有效地求解，因此只能在合理的时间内提供近似解。令人惊讶的是，一个有限的和系统的算法技术，基于所谓的数学工具凸规划，在这个方向上给出了显着的积极成果。最近，这种算法技术已经被利用到一个动态的计算模型中，在这个模型中，人们可以证明以效率换取准确性。目前计划的一半将研究这种计算模型对整个效率概念谱的能力，触及并扩展著名数学命题的可计算性预测，例如“P不等于NP”和独特游戏猜想。这项研究计划的进展将提高我们对硬组合优化问题的可解性的理解，将导致新的算法技术，以及将识别难以解决的输入实例的结构特性。 现实生活中的其他有价值的计算资源包括计算的中心性。例如，在搜索和救援行动中大量存在的所谓搜索和获取问题就是这种情况。事实上，现代机器人技术的最新发展引起了组合问题，其中许多自主移动的代理（无人机）试图完成一项任务，例如在未知环境中定位和救援受害者。在这些情况下，计算是“分布式”的参与移动的代理，而计算的中心是由机器人的通信能力的影响。目前的研究计划的另一半将调查的计算能力的移动的代理在搜索和获取问题。这项研究的重点将是效率权衡的中心概念，因为它是由不同的机器人通信能力。这一领域的进展将对机器人应用产生直接影响，并将加深我们对分布式系统计算能力的理解。

One of the fundamental subjects in Theoretical Computer Science is the study of computation capabilities when resources are limited. Indeed, many real-life optimization problems admit easy-to-describe and non-efficient algorithmic solutions if one assumes unlimited computation power, e.g. no restrictions in time, and full coordination of participating processes. How well can such a problem be solved when one is restricted to use efficient algorithms with limited resources? When the limited resource is time, i.e. the number of computation steps, Theoretical Computer Science has provided a rich problem classification mostly based on deep and unresolved mathematical conjectures. According to these conjectures, a large family of combinatorial optimization problems cannot be solved exactly and efficiently, and as such one is bound to provide only approximate solutions within reasonable time. Surprisingly, a restricted and systematic algorithmic technique, based on the so-called mathematical tool of convex-programming, has given remarkable positive results in this direction. Recently, this algorithmic technique has been leveraged into a dynamic model of computation where one can provably trade efficiency for accuracy. Half of the current program will investigate the capabilities of this model of computation for the whole spectrum of efficiency notions, touching and extending on the computability predictions of famous mathematical conjectures, e.g. that of ``P is not equal to NP'' and the Unique Games Conjecture. Progress in this research program will enhance our understanding of the solvability of hard combinatorial optimization problems, will result into new algorithmic techniques, as well as will identify structural properties of input instances that are difficult to solve. Other valuable computation resources in real-life problems include the centrality of computation. For example, this is the case in the so-called search-and-fetch problems that abound in search-and-rescue operations. Indeed, recent developments in modern robotics give rise to combinatorial problems in which a number of autonomous mobile agents (drones) attempt to complete a task, e.g. locate and rescue a victim in an unknown environment. Computation in these cases is ``distributed'' among the participating mobile agents, while the centrality of computation is affected by the communication capabilities of the robots. The other half of the current research program will investigate the computation capabilities of mobile agents in search-and-fetch problems. The focus of this research will be on efficiency tradeoffs for a large spectrum of centrality notions as it is imposed by different robot communication capabilities. Progress in this area will have immediate impact to robotics applications, as well as it will deepen our understanding of the computation capabilities in distributed systems.