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.**