Efficiency Tradeoffs for Combinatorial Optimization Problems

点击翻译按钮获取中文摘要

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.