AF: Small: Beyond Worst-Case Analysis in Approximation Algorithms, Algorithmic Mechanism Design and Online Algorithms

University Of Washington, Seattle WA

Investigators

Abstract

In theoretical computer science, algorithms are usually evaluated with respect to their worst-case performance, whereas in other areas, average-case analysis is often used. Both of these approaches have drawbacks: worst-case analysis is overly pessimistic and average-case analysis often rests on unrealistic assumptions. To address these issues, a number of other analysis frameworks have been proposed including self-improving algorithms, smoothed analysis, instance-optimality, and algorithmic design based on a variety of data models. The objective of the project is to continue this line of research and develop techniques that go beyond worst-case analysis in the areas of approximation algorithms, algorithmic mechanism design and online algorithms. In the area of approximation algorithms for NP-hard problems, the project focuses on the development of approximation algorithms that achieve a kind of instance optimality. In the area of algorithmic mechanism design, the PI will continue to study the design and analysis of profit maximizing auctions in single-parameter environments and beyond. In the area of online algorithms, the PI will work to develop effective online algorithms for a fundamental and practical self-organizing data structure problem. Through the development of more effective and practical algorithms and a deeper understanding of the performance of these algorithms in practice, this research has the potential to impact a variety of subfields of computer science including artificial intelligence, systems and networking, data mining, and electronic commerce.