Atomic congestion games: fast, myopic and concurrent ⋆ (2008)
Dimitris Fotakis, Alexis C. Kaporis, Paul G. Spirakis
Abstract. We study here the effect of concurrent greedy moves of players in atomic congestion games where n selfish agents (players) wish to select a resource each (out of m resources) so that her...
and Theoretical Computer Science Frequency Assignment in Mobile and Radio Networks (2007)
Dimitris Fotakis, Grammati Pantziou, George Pentaris, Paul Spirakis
Abstract. We deal with the problem of frequency assignment in mobile and general radio networks, where the signal interferences are modeled using an interference graph G. Our approach uses graph...
Virtual European School – VES (2007)
Christos Bouras, Dimitris Fotakis, Vaggelis Kapoulas, Anni Koubek, Harald Mayer, Herwig Rehatschek
The Virtual European School (VES) is an ongoing European project- funded by the Educational Multimedia Task Force Initiative of the European Union- with the aim to develop a comprehensive on-line...
Dimitris Fotakis, Spyros Kontogiannis, Elias Koutsoupias, Marios Mavronicolas, Paul Spirakis
Abstract. In this work, we study the combinatorial structure and the computational complexity of Nash equilibria for a certain game that models selsh routing over a network consisting of m parallel...
Algorithmic Issues in Coalitional and Dynamic Network Games (2005)
Dimitris Fotakis, Spyros Kontogiannis, Panagiota Panagopoulou, Christoforos Raptopoulos, Paul Spirakis
We discuss some new algorithmic and complexity issues in coalitional and dynamic/evolutionary games, related to the understanding of modern selfish and Complex networks.
Symmetry in Network Congestion Games: Pure Equilibria and Anarchy Cost (2005)
Dimitris Fotakis, Spyros Kontogiannis, Paul Spirakis
Abstract. We study computational and coordination efficiency issues of Nash equilibria in symmetric network congestion games. We first propose a simple and natural greedy method that computes a pure...
Space Efficient Hash Tables With Worst Case Constant Access Time (2005)
Fotakis, Dimitris, Pagh, Rasmus, Sanders, Peter, Spirakis, Paul
We generalize Cuckoo Hashing to \emph{$d$-ary Cuckoo Hashing} and show how this yields a simple hash table data structure that stores $n$ elements in $(1+\e)\,n$ memory cells, for any constant $\e >...
Incremental Algorithms for Facility Location and k-Median (2004)
Fotakis, Dimitris, Albers, Susanne, Radzik, Tomasz
In the incremental versions of Facility Location and k-Median, the demand points arrive one at a time and the algorithm must maintain a good solution by either adding each new demand to an existing...
Selfish unsplittable flows (2004)
Dimitris Fotakis, Paul Spirakis
Abstract. What is the price of anarchy when unsplittable demands are routed selfishly in general networks with load-dependent edge delays? Motivated by this question we generalize the model of [14]...
Incremental algorithms for facility location and k-median (2004)
In the incremental versions of Facility Location and k-Median, the demand points arrive one at a time and the algorithm maintains a good solution by either adding each new demand to an existing...
Incremental algorithms for facility location and k-median (2004)
Abstract. In the incremental versions of Facility Location and k-Median, the demand points arrive one at a time and the algorithm must maintain a good solution by either adding each new demand to an...
Incremental Algorithms for Facility Location and k-Median (2004)
Fotakis, Dimitris, Albers, Susanne, Radzik, Tomasz
In the incremental versions of Facility Location and k-Median, the demand points arrive one at a time and the algorithm must maintain a good solution by either adding each new demand to an existing...
Space Efficient Hash Tables with Worst Case Constant Access Time (2003)
Fotakis,Dimitris, Pagh,Rasmus, Sanders,Peter, Spirakis,Paul G.
We generalize Cuckoo Hashing \cite{PagRod01} to \emph{$d$-ary Cuckoo Hashing} and show how this yields a simple hash table data structure that stores $n$ elements in $(1+\epsilon)\,n$ memory cells,...
On the Competitive Ratio for Online Facility Location (2003)
Fotakis, Dimitris, Baeten, Jos C.M., Lenstra, Jan Karel, Parrow, Joachim, Woeginger, Gerhard J.
We consider the problem of Online Facility Location, where demands arrive online and must be irrevocably assigned to an open facility upon arrival. The objective is to minimize the sum of facility...
Space Efficient Hash Tables with Worst Case Constant Access Time (2003)
Fotakis, Dimitris, Pagh, Rasmus, Sanders, Peter, Spirakis, Paul G., Alt, Helmut, Habib, Michel
We generalize Cuckoo Hashing \cite{PagRod01} to \emph{$d$-ary Cuckoo Hashing} and show how this yields a simple hash table data structure that stores $n$ elements in $(1+\epsilon)\,n$ memory cells,...
Space efficient hash tables with worst case constant access time (2003)
Dimitris Fotakis, Rasmus Pagh, Peter Sanders, Paul Spirakis
Abstract. We generalize Cuckoo Hashing [23] to d-ary Cuckoo Hashing and show how this yields a simple hash table data structure that stores n elements in (1 + ffl) n memory cells, for any constant...
On the competitive ratio for online facility location (2003)
Abstract. We consider the problem of Online Facility Location, where demands arrive online and must be irrevocably assigned to an open facility upon arrival. The objective is to minimize the sum of...
Space efficient hash tables with worst case constant access time (2003)
Dimitris Fotakis, Rasmus Pagh, Peter S, Paul Spirakis
Abstract. We generalize Cuckoo Hashing [23] to d-ary Cuckoo Hashing and show how this yields a simple hash table data structure that stores n elements in (1 + ε) n memory cells, for any constant...
Andreou,Maria, Fotakis,Dimitris, Nikoletseas,Sotiris, Papadopoulou,Vicky, Spirakis,Paul G.
Hierarchical specifications of graphs have been widely used in many important applications, such as VLSI design, parallel programming and software engineering. A well known hierarchical specification...
Fotakis,Dimitris, Nikoletseas,Sotiris, Papadopoulou,Vicky, Spirakis,Paul G.
The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters exploiting frequency reuse while keeping signal interference to acceptable levels. The...
The Structure and Complexity of Nash Equilibria for a Selfish Routing Game (2002)
Fotakis,Dimitris, Kontogiannis,Spyros, Koutsoupias,Elias, Mavronicolas,Marios, Spirakis,Paul G.
In this work, we study the combinatorial structure and the computational complexity of Nash equilibria for a certain game that models {\em selfish routing} over a network consisting of $m$ parallel...
Minimum Congestion Redundant Assignments to Tolerate Random Faults (2002)
Fotakis,Dimitris, Spirakis,Paul G.
We consider the problem of computing minimum congestion, fault-tolerant, redundant assignments of messages to faulty, parallel delivery channels. In particular, we are given a set $K$ of faulty...
Andreou, Maria, Fotakis, Dimitris, Nikoletseas, Sotiris, Papadopoulou, Vicky, Spirakis, Paul G., Diks, Krzysztof, ...
Hierarchical specifications of graphs have been widely used in many important applications, such as VLSI design, parallel programming and software engineering. A well known hierarchical specification...
Fotakis, Dimitris, Nikoletseas, Sotiris, Papadopoulou, Vicky, Spirakis, Paul G., Kucera, Ludek
The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters exploiting frequency reuse while keeping signal interference to acceptable levels. The...
The Structure and Complexity of Nash Equilibria for a Selfish Routing Game (2002)
Fotakis, Dimitris, Kontogiannis, Spyros, Koutsoupias, Elias, Mavronicolas, Marios, Spirakis, Paul G., Widmayer, Peter, ...
In this work, we study the combinatorial structure and the computational complexity of Nash equilibria for a certain game that models {\em selfish routing} over a network consisting of $m$ parallel...
Minimum Congestion Redundant Assignments to Tolerate Random Faults (2002)
Fotakis, Dimitris, Spirakis, Paul G.
We consider the problem of computing minimum congestion, fault-tolerant, redundant assignments of messages to faulty, parallel delivery channels. In particular, we are given a set $K$ of faulty...
The Structure and Complexity of Nash Equilibria for a Selfish Routing Game (2002)
Dimitris Fotakis, Spyros Kontogiannis, Elias Koutsoupias, Marios Mavronicolas, Paul Spirakis
Abstract. In this work, we study the combinatorial structure and the computational complexity of Nash equilibria for a certain game that models selfish routing over a network consisting of m parallel...
The Structure and Complexity of Nash Equilibria for a Selfish Routing Game (2002)
Dimitris Fotakis, Spyros Kontogiannis, Elias Koutsoupias, Marios Mavronicolas, Paul Spirakis
Abstract. In this work, we study the combinatorial structure and the computational complexity of Nash equilibria for a certain game that models selfish routing over a network consisting of m parallel...
principles on the design of an educational network (1997)
Christos Bouras, Dimitris Fotakis, Alexandra Katanou, Agisilaos Konidaris, Spyros Kontogiannis, Afrodite Sevasti, ...
Abstract: The modern communication networks, apart from the specialized applications that they offer depending on the nature of their target groups, they support a set of general purpose elementary...
poly(loglog n); poly(loglog n))--restricted verifiers are unlikely to exist for languages (1996)
Dimitris Fotakis, Paul Spirakis
Abstract. The aim of this paper is to present a proof of the equivalence of the equalities NP = PCP(log log n; 1) and P = NP. The proof is based on producing long pseudo-random bit strings through...