10 papers
Leveraging Recourse and Size Bounds for OnlineKnapsack with Removable Items
Dimitris Fotakis, Laurent Gourvès, Aris Pagourtzis +1
In the online unweighted knapsack problem, items arrive sequentially and must be accepted or rejected immediately for a bounded-capacity knapsack, aiming to maximize the total size…
CLS Hardness of 2D Min-Max Optimization with Product Constraints
Alkis Kalavasis, Panagiotis Patsilinakos, Stratis Skoulakis +1
We study the complexity of computing approximate first-order Nash equilibria in min-max optimization problems with one dimensional min and max players and product constraints. For…
Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
Evripidis Bampis, Bruno Escoffier, Dimitris Fotakis +2
We consider a learning-augmented framework for NP-hard permutation problems. The algorithm has access to predictions telling, given a pair of elements, whether is before…
A Competitive Posted-Price Mechanism for Online Budget-Feasible Auctions
Andreas Charalampopoulos, Dimitris Fotakis, Panagiotis Patsilinakos +1
We consider online procurement auctions, where the agents arrive sequentially, in random order, and have private costs for their services. The buyer aims to maximize a monotone sub…
On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries
Dimitris Fotakis, Laurent Gourvès, Panagiotis Patsilinakos
We consider committee election of (out of ) candidates, where the voters and the candidates are associated with locations on the real line. Each voter's card…
Sampling and Optimal Preference Elicitation in Simple Mechanisms
Ioannis Anagnostides, Dimitris Fotakis, Panagiotis Patsilinakos
In this work we are concerned with the design of efficient mechanisms while eliciting limited information from the agents. First, we study the performance of sampling approximation…
Dimensionality, Coordination, and Robustness in Voting
Ioannis Anagnostides, Dimitris Fotakis, Panagiotis Patsilinakos
We study the performance of voting mechanisms from a utilitarian standpoint, under the recently introduced framework of metric-distortion, offering new insights along three main li…
Metric-Distortion Bounds under Limited Information
Ioannis Anagnostides, Dimitris Fotakis, Panagiotis Patsilinakos
In this work we study the metric distortion problem in voting theory under a limited amount of ordinal information. Our primary contribution is threefold. First, we consider mechan…
Strategyproof Facility Location in Perturbation Stable Instances
Dimitris Fotakis, Panagiotis Patsilinakos
We consider -Facility Location games, where strategic agents report their locations on the real line, and a mechanism maps them to facilities. Each agent seeks to m…
Node Max-Cut and Computing Equilibria in Linear Weighted Congestion Games
Dimitris Fotakis, Vardis Kandiros, Thanasis Lianeas +3
In this work, we seek a more refined understanding of the complexity of local optimum computation for Max-Cut and pure Nash equilibrium (PNE) computation for congestion games with…