7 papers
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…
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…
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…
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…
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…
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…