1 citations · 1 across the 4 of their papers we have counts for
17 papers
Tight Inapproximability for Graphical Games
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
We provide a complete characterization for the computational complexity of finding approximate equilibria in two-action graphical games. We consider the two most well-studied appro…
A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games
Argyrios Deligkas, Michail Fasoulakis, Evangelos Markakis
Since the celebrated PPAD-completeness result for Nash equilibria in bimatrix games, a long line of research has focused on polynomial-time algorithms that compute -ap…
The Parameterized Complexity of Welfare Guarantees in Schelling Segregation
Argyrios Deligkas, Eduard Eiben, Tiger-Lily Goldsmith
Schelling's model considers types of agents each of whom needs to select a vertex on an undirected graph, where every agent prefers to neighbor agents of the same type. We are…
Heterogeneous Facility Location with Limited Resources
Argyrios Deligkas, Aris Filos-Ratsikas, Alexandros A. Voudouris
We initiate the study of the heterogeneous facility location problem with limited resources. We mainly focus on the fundamental case where a set of agents are positioned in the lin…
Ranking Bracelets in Polynomial Time
Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev +1
The main result of the paper is the first polynomial-time algorithm for ranking bracelets. The time-complexity of the algorithm is O(k^2 n^4), where k is the size of the alphabet a…
The K-Centre Problem for Necklaces
Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev +1
In graph theory, the objective of the k-centre problem is to find a set of vertices for which the largest distance of any vertex to its closest vertex in the -set is minimis…