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.
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:
- This is the first time that the methods and the techniques of beyond-worst-case analysis have been applied to the design of efficient truthful
mechanisms and of efficient approximation algorithms for optimization problems with time-evolving costs.
- This is the first time that “typical” practical instances of optimization problems with time-evolving costs and combinatorial auctions have been
investigated, and the notion of perturbation stability has been used as a means of characterizing such instances.
- The project develops novel algorithmic techniques for optimization problems with time-evolving costs and aims at a deeper and unified understanding
of their algorithmic properties, which is missing from current literature.
- The project studies, for the first time, how the design of efficient truthful mechanisms can be facilitated, if we focus on practically relevant
instances, and proposes new forms of truthful mechanisms that best exploit this direction.
Expected Results and Impact
- A deeper understanding of the algorithmic properties of optimization problems with time-evolving costs and the development of a unified approach to the design and analysis of efficient approximation algorithms for such problems.
- The extension of the notion of the stability of the optimal solution to small perturbations of the input, and its exploitation for the characterization of “typical” practical instances in the contexts of combinatorial auctions and optimization problems with time-evolving costs.
- The development of a wide knowledge framework related to the design of efficient truthful mechanisms for perturbation stable instances.
- The formation of a research group, mostly consisted of young researchers, with top-notch expertise in the important and timely research directions of optimization over time-evolving costs and truthful mechanism design.
- Accumulation of state-of-the-art algorithmic knowledge, with significant practical applications and potential of economic and social growth though its application and exploitation.
- Further development of research culture related to high quality, high risk and high gain algorithmic research.
Research Team
Publications
- Dimitris Fotakis, Vardis Kandiros, Thanasis Lianeas, Nikos Mouzakis, Panagiotis Patsilinakos, Stratis Skoulakis:
Node-Max-Cut and the Complexity of Equilibrium in Linear Weighted Congestion Games. ICALP 2020: 50:1-50:19.
- Dimitris Fotakis, Loukas Kavouras, Grigorios Koumoutsos, Stratis Skoulakis, Manolis Vardas:
The Online Min-Sum Set Cover Problem.
ICALP 2020: 51:1-51:16.
- Dimitris Fotakis, Alkis Kalavasis, Christos Tzamos:
Efficient Parameter Estimation of Truncated Boolean Product Distributions. COLT 2020: 1586-1600.
- Giannis Fikioris, Dimitris Fotakis:
Mechanism Design for Perturbation Stable Combinatorial Auctions.
SAGT 2020: 47-63. Full version accepted in Theory of Computing
Systems.
- Ioannis Anagnostides, Dimitris Fotakis, Panagiotis Patsilinakos:
Asymptotically Optimal Communication in Simple Mechanisms. SAGT 2020:
17-31.
- Dimitris Fotakis, Thanasis Lianeas, Georgios Piliouras, Stratis Skoulakis:
Efficient Online Learning of Optimal Rankings: Dimensionality Reduction via Gradient Descent.
NeurIPS 2020.
- Dimitris Fotakis, Alkis Kalavasis, Konstantinos Stavropoulos:
Aggregating Incomplete and Noisy Rankings.
AISTATS 2021: 2278-2286.
- Dimitris Fotakis, Thanasis Pittas, Stratis Skoulakis:
Estimating the Number of Induced Subgraphs from Incomplete Data and Neighborhood Queries.
AAAI 2021: 4045-4053.
- Dimitris Fotakis, Piotr Krysta, Carmine Ventre:
Efficient Truthful Scheduling and Resource Allocation through Monitoring.
AAAI 2021: 5423-5431.
- Dimitris Fotakis, Loukas Kavouras, Lydia Zakynthinou:
Online Facility Location in Evolving Metrics.
Algorithms 14(3): 73, 2021.
- Dimitris Fotakis, Loukas Kavouras, Panagiotis Kostopanagiotis, Philip Lazos, Stratis Skoulakis, Nikos Zarifis:
Reallocating multiple facilities on the line.
Theoretical Computer Science 858: 13-34, 2021.
- Dimitris Fotakis, Panagiotis Kostopanagiotis, Vasileios Nakos, Georgios Piliouras, Stratis Skoulakis:
On the Approximability of Multistage Min-Sum Set Cover.
ICALP 2021: 65:1-65:19.
- Dimitris Fotakis, Georgios Piliouras, Stratis Skoulakis:
Efficient Online Learning for Dynamic k-Clustering.
ICML 2021: 3396-3406.
- Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, Christos Tzamos:
Efficient Algorithms for Learning from Coarse Labels.
COLT 2021: 2060-2079.
- Ioannis Anagnostides, Dimitris Fotakis, Panagiotis Patsilinakos:
Metric-Distortion Bounds Under Limited Information.
SAGT 2021: 299-313.
- Dimitris Fotakis, Panagiotis Patsilinakos: Strategyproof Facility Location in Perturbation Stable Instances.WINE
2021 (to appear).
- Robert Istvan Busa-Fekete, Dimitris Fotakis, Balazs Szorenyi, Manolis Zampetakis: Identity testing for Mallows model.
NeurIPS 2021 (to appear).
-
Robert Istvan Busa-Fekete, Dimitris Fotakis, Manolis Zampetakis: Private and Non-private Uniformity Testing for Ranking Data.
NeurIPS 2021 (to appear).