21 citations · 65 across the 25 of their papers we have counts for
36 papers
Constant Inapproximability for Fisher Markets
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
We study the problem of computing approximate market equilibria in Fisher markets with separable piecewise-linear concave (SPLC) utility functions. In this setting, the problem was…
Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
We study the problem of computing a competitive equilibrium with approximately optimal bundles in Fisher markets with separable piecewise-linear concave (SPLC) utility functions, m…
Distributed Agent-Constrained Truthful Facility Location
Argyrios Deligkas, Panagiotis Kanellopoulos, Alexandros A. Voudouris
We study a distributed facility location problem in which a set of agents, each with a private position on the real line, is partitioned into a collection of fixed, disjoint groups…
Agent-Constrained Truthful Facility Location Games
Argyrios Deligkas, Mohammad Lotfi, Alexandros A. Voudouris
We consider a truthful facility location problem in which there is a set of agents with private locations on the line of real numbers, and the goal is to place a number of faciliti…
Truthful Interval Covering
Argyrios Deligkas, Aris Filos-Ratsikas, Alexandros A. Voudouris
We initiate the study of a novel problem in mechanism design without money, which we term Truthful Interval Covering (TIC). An instance of TIC consists of a set of agents each asso…
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…
Pure-Circuit: Tight Inapproximability for PPAD
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
The current state-of-the-art methods for showing inapproximability in PPAD arise from the -Generalized-Circuit (-GCircuit) problem. Rubinstein (2018) show…
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
Argyrios Deligkas, Michail Fasoulakis, Evangelos Markakis
Since the seminal PPAD-completeness result for computing a Nash equilibrium even in two-player games, an important line of research has focused on relaxations achievable in polynom…
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…
Minimizing Reachability Times on Temporal Graphs via Shifting Labels
Argyrios Deligkas, Eduard Eiben, George Skretas
We study how we can accelerate the spreading of information in temporal graphs via shifting operations; a problem that captures real-world applications varying from information flo…
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…
Pizza Sharing is PPA-hard
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos
We study the computational complexity of finding a solution for the straight-cut and square-cut pizza sharing problems. We show that computing an -approximate solution…
Two's Company, Three's a Crowd: Consensus-Halving for a Constant Number of Agents
Argyrios Deligkas, Aris Filos-Ratsikas, Alexandros Hollender
We consider the -Consensus-Halving problem, in which a set of heterogeneous agents aim at dividing a continuous resource into two (not necessarily contiguous) portions…
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…
Matching in Stochastically Evolving Graphs
Eleni C. Akrida, Argyrios Deligkas, George B. Mertzios +2
This paper studies the maximum cardinality matching problem in stochastically evolving graphs. We formally define the arrival-departure model with stochastic departures. There, a g…
Walrasian Equilibria in Markets with Small Demands
Argyrios Deligkas, Themistoklis Melissourgos, Paul G. Spirakis
We study the complexity of finding a Walrasian equilibrium in markets where the agents have -demand valuations. These valuations are an extension of unit-demand valuations where…
Heterogeneous Facility Location Games
Eleftherios Anastasiadis, Argyrios Deligkas
We study heterogeneous -facility location games. In this model there are facilities where each facility serves a different purpose. Thus, the preferences of the agents over…
Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis +1
In this paper we consider the following total functional problem: Given a cubic Hamiltonian graph and a Hamiltonian cycle of , how can we compute a second Hamiltonian…
Optimizing Reachability Sets in Temporal Graphs by Delaying
Argyrios Deligkas, Igor Potapov
A temporal graph is a dynamic graph where every edge is assigned a set of integer time labels that indicate at which discrete time step the edge is available. In this paper, we stu…
Crystal Structure Prediction via Oblivious Local Search
Dmytro Antypov, Argyrios Deligkas, Vladimir Gusev +3
We study Crystal Structure Prediction, one of the major problems in computational chemistry. This is essentially a continuous optimization problem, where many different, simple and…
Path Polymatrix Games are PPAD-hard
Argyrios Deligkas, John Fearnley, Rahul Savani
We prove that it is PPAD-hard to compute a Nash equilibrium in a tree polymatrix game with at most twenty actions per player, and path polymatrix game with at most four hundred act…
On the Hardness of Energy Minimisation for Crystal Structure Prediction
Duncan Adamson, Argyrios Deligkas, Vladimir Gusev +1
Crystal Structure Prediction (csp) is one of the central and most challenging problems in materials science and computational chemistry. In csp, the goal is to find a configuration…