BALSAM: Beyond WorstCase
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
HighValue Research Equipment", project number 1424.
Synopsis
We aim at circumventing strong lower bounds and negative results, imposed by worstcase 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 kmedian, kmeans and kcenter, and network infrastructure design problems, such as
the problems of facility location and minimum spanning tree, when the connection costs are timeevolving. We will focus on
perturbationstable 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 kfacility location games on
the line and in general metric spaces, and for combinatorial auctions.
Originality and Objectives
The research agenda of socalled “beyond worstcase 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 worstcase analysis. Its originality concerns the following, among others:
 This is the first time that the methods and the techniques of beyondworstcase analysis have been applied to the design of efficient truthful
mechanisms and of efficient approximation algorithms for optimization problems with timeevolving costs.
 This is the first time that “typical” practical instances of optimization problems with timeevolving 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 timeevolving 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 timeevolving 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 timeevolving 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 topnotch expertise in the important and timely research directions of optimization over timeevolving costs and truthful mechanism design.
 Accumulation of stateoftheart 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:
NodeMaxCut and the Complexity of Equilibrium in Linear Weighted Congestion Games. ICALP 2020: 50:150:19.
 Dimitris Fotakis, Loukas Kavouras, Grigorios Koumoutsos, Stratis Skoulakis, Manolis Vardas:
The Online MinSum Set Cover Problem.
ICALP 2020: 51:151:16.
 Dimitris Fotakis, Alkis Kalavasis, Christos Tzamos:
Efficient Parameter Estimation of Truncated Boolean Product Distributions. COLT 2020: 15861600.
 Giannis Fikioris, Dimitris Fotakis:
Mechanism Design for Perturbation Stable Combinatorial Auctions.
SAGT 2020: 4763. Full version accepted in Theory of Computing
Systems.
 Ioannis Anagnostides, Dimitris Fotakis, Panagiotis Patsilinakos:
Asymptotically Optimal Communication in Simple Mechanisms. SAGT 2020:
1731.
 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: 22782286.
 Dimitris Fotakis, Thanasis Pittas, Stratis Skoulakis:
Estimating the Number of Induced Subgraphs from Incomplete Data and Neighborhood Queries.
AAAI 2021: 40454053.
 Dimitris Fotakis, Piotr Krysta, Carmine Ventre:
Efficient Truthful Scheduling and Resource Allocation through Monitoring.
AAAI 2021: 54235431.
 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: 1334, 2021.
 Dimitris Fotakis, Panagiotis Kostopanagiotis, Vasileios Nakos, Georgios Piliouras, Stratis Skoulakis:
On the Approximability of Multistage MinSum Set Cover.
ICALP 2021: 65:165:19.
 Dimitris Fotakis, Georgios Piliouras, Stratis Skoulakis:
Efficient Online Learning for Dynamic kClustering.
ICML 2021: 33963406.
 Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, Christos Tzamos:
Efficient Algorithms for Learning from Coarse Labels.
COLT 2021: 20602079.
 Ioannis Anagnostides, Dimitris Fotakis, Panagiotis Patsilinakos:
MetricDistortion Bounds Under Limited Information.
SAGT 2021: 299313.
 Dimitris Fotakis, Panagiotis Patsilinakos: Strategyproof Facility Location in Perturbation Stable Instances.WINE
2021 (to appear).
 Robert Istvan BusaFekete, Dimitris Fotakis, Balazs Szorenyi, Manolis Zampetakis: Identity testing for Mallows model.
NeurIPS 2021 (to appear).

Robert Istvan BusaFekete, Dimitris Fotakis, Manolis Zampetakis: Private and Nonprivate Uniformity Testing for Ranking Data.
NeurIPS 2021 (to appear).