BALSAM: Beyond Worst-Case Analysis in Approximation Algorithms and Mechanism Design

Funded by the Hellenic Foundation for Research and Innovation (H.F.R.I.) under the "1st Call for H.F.R.I. Research Projects to Support Faculty Members and Researchers and Procure High-Value Research Equipment", project number 1424.

 

Principal Investigator:

Dimitris Fotakis

Scientific Area:

Theoretical Computer Science, Algorithms and Complexity

Host Institution:

National Technical University of Athens, School of Electrical and Computer Engineering

Collaborating Institution:

University of Wisconsin-Madison, Department of Computer Sciences ( Prof. Christos Tzamos )

Duration:

42 months (12/2019 - 6/2023)

Budget:

170,000 Euros

Synopsis

We aim at circumventing strong lower bounds and negative results, imposed by worst-case analysis, and at a deeper understanding of the algorithmic properties of fundamental problems in the research areas of Approximation Algorithms and Algorithmic Mechanism Design for “typical” instances that appear in practice.

We will study central problems in the research areas above, under realistic assumptions on the structure of the input. These assumptions will be deterministic, e.g., that the optimal solution is stable to small input perturbations, or stochastic in nature, e.g., that the valuation functions of the participants in an auction follow some fixed distribution.

In the area of Approximation Algorithms, we will investigate the computational complexity and the approximability of clustering problems, such as the problems of k-median, k-means and k-center, and network infrastructure design problems, such as the problems of facility location and minimum spanning tree, when the connection costs are time-evolving. We will focus on perturbation-stable instances, where the perturbation stability assumption will be appropriately adjusted to take the temporal dimension of the problems into account.

In the area of Algorithmic Mechanism Design, we will determine the tradeoff between the level of perturbation stability and the approximation ratio (with respect to the social welfare) achievable by truthful mechanisms for k-facility location games on the line and in general metric spaces, and for combinatorial auctions.

Originality and Objectives

The research agenda of so-called “beyond worst-case analysis”, which aims at a deeper understanding of the algorithmic properties of fundamental computational problems for practically relevant instances, has been significantly developed in the last few years and keeps developing rapidly.

The project aims to make a substantial research contribution to the research agenda of beyond worst-case analysis. Its originality concerns the following, among others:

Expected Results and Impact

Research Team

Publications