Power and Limitations of Conceptually Simple Algorithms

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

Theoretical computer science has been hugely successful in terms of both design of new efficient and practical algorithms, as well as analysis and explanation of performance of existing algorithms. Yet, the gap between "theory" and "practice" remains. One of the most common criticisms is that worst-case analysis is often too pessimistic to reflect "practice". Prime examples of this phenomenon are linear programming and satisfiability problems. Another criticism is that negative results are often based on assumptions. Sometimes these assumptions are quite reasonable, such as P not equal to NP, but other times these assumptions are more controversial, such as strong exponential time hypothesis. Yet another criticism is that computational models might lack some practical features, e.g., extra side information that might be available to an algorithm. Side-information is often modelled in theory by an all-powerful oracle, where the "all-powerful" part is not very realistic. While there is no single "silver bullet" model that addresses all these concerns, there are many success stories in attempts to bridge practice and theory. This research program falls under this umbrella of trying to reduce the gap between theory and practice as it pertains to conceptually simple algorithms. Conceptually simple algorithms have many properties that make them desirable in practice, but they are hard to analyze. Part of the problem is that usually simple algorithms have bad worst-case behavior, but excellent empirical performance. An analysis consistent with such reality has to accurately model practical instances, which already is a very difficult task. Another problem is that the notion of simplicity is not well-defined. This makes negative answers to questions of the form "can this problem be solved by a simple algorithm?" impossible. The long-term goal of this project is to develop a formal theory of simple algorithms that would address the three criticisms mentioned above. Short-term goals consist of practical input modelling, algorithmic modelling with information-theoretic bottlenecks, and evaluation of conceptually simple algorithms for specific problems within various application domains, such as online advertising, scheduling, packing, and optimization.