Curriculum Vitae  Dimitris Fotakis
March 2009
Contact Information 
 
Current Position 
Lecturer (Feb. 2009  ), Division of Computer Science, School of Electrical and Computer Engineering, National Technical University of Athens, Greece. 

Previous Positions 
Assistant Professor (Oct. 2004  Jan. 2009, tenured since June 2008), Department of Information and Communication Systems Engineering, School of Sciences, University of the Aegean, Greece. Lecturer (Nov. 2003  Oct. 2004), General Department of Mathematical, Physical, and Computational Sciences, School of Engineering, Aristotle University of Thessaloniki, Greece. PostDoctoral Researcher (Sept. 2001  Aug. 2003), MaxPlanckInstitut für Informatik, Algorithms and Complexity Group (AG1). Director: Prof.Dr. Kurt Mehlhorn. 

Education 
PhD in Computer Science,
Department of Computer
Engineering and Informatics, University of Patras, Greece
(1999). Thesis: Approximate Solution of Computationally Hard Problems: Algorithms and Complexity (in Greek). Abstract is also available in English. Advisor: Prof. Paul Spirakis.
Computer Engineering Diploma,
Department of Computer Engineering and Informatics, University of Patras, Greece (1994).


Research Interests 
Approximation and Online Algorithms. Algorithmic Aspects of Communication Networks. Algorithmic Game Theory. Facility Location Problems. Computational Complexity. Algorithmic Engineering.


Program Committees 
14th European Symposium on Algorithms, Track A: Design and Analysis (ESA 06), ETH Zürich, 1113 September, 2006. 1st Symposium on Algorithmic Game Theory (SAGT 08), Paderborn, April 30  May 2, 2008. 12th PanHellenic Conference on Informatics (PCI 08), Samos, August 28  30, 2008.


Journal Articles 
D. Fotakis and P. Spirakis. CostBalancing Tolls for Atomic Network
Congestion Games. Accepted in Internet Mathematics,
Special Issue on WINE 2007, January 2009.
D. Fotakis. Congestion Games with Linearly Independent Paths: Convergence Time and Price of Anarchy. Accepted in Theory of Computing Systems, Special Issue on SAGT 2008, March 2009. D. Fotakis, A. Kaporis, and P. Spirakis. Atomic Congestion Games: Fast, Myopic, and Concurrent. Accepted in Theory of Computing Systems, Special Issue on SAGT 2008, March 2009. D. Fotakis. Stackelberg Strategies for Atomic Congestion Games. Accepted in Theory of Computing Systems, October 2008. D. Fotakis, S. Kontogiannis, E. Koutsoupias, M. Mavronicolas, and P. Spirakis. The Structure and Complexity of Nash Equilibria for a Selfish Routing Game. Accepted in Theoretical Computer Science, 2008. D. Fotakis, S. Kontogiannis, and P. Spirakis. Atomic Congestion Games Among Coalitions. ACM Transactions on Algorithms 4(4), 2008. D. Fotakis. On the Competitive Ratio for Online Facility Location. Algorithmica 50(1), pp. 157, 2008. D. Fotakis. Incremental Algorithms for Facility Location and kMedian. Theoretical Computer Science 361, Special Issue on Approximation and Online Algorithms, pp. 275313, 2006. D. Fotakis. A PrimalDual Algorithm for Online NonUniform Facility Location. Journal of Discrete Algorithms 5, pp. 141148, 2006. D. Fotakis, S. Nikoletseas, V. Papadopoulou, and P. Spirakis. Radiocolorings in Periodic Planar Graphs: PSPACECompleteness and Efficient Approximations for the Optimal Range of Frequencies. Journal of Discrete Algorithms 4, pp. 433454, 2006. D. Fotakis, S. Kontogiannis, and P. Spirakis. Selfish Unsplittable Flows. Theoretical Computer Science 348, Special Issue on ICALP 2004, pp. 226239, 2005. D. Fotakis, R. Pagh, P. Sanders, and P. Spirakis. Space Efficient Access Tables with Worst Case Constant Access Time. Theory of Computing Systems 38, Special Issue on STACS 2003, pp. 229248, 2005. D. Fotakis, S. Nikoletseas, V. Papadopoulou, and P. Spirakis. Radiocoloring in Planar Graphs: Complexity and Approximations. Theoretical Computer Science 340, Special Issue on MFCS 2000, pp. 514538, 2005. D. Fotakis and P. Spirakis. Minimum Congestion Redundant Assignments to Tolerate Random Faults. Algorithmica 32, 396422, SpringerVerlag, 2002. D. Fotakis, S. Nikoletseas, V. Papadopoulou, and P. Spirakis. Hardness Results and Efficient Approximations for Frequency Assignment Problems: Radio Labelling and Radio Coloring. Computing and Informatics 20, 121180, 2001. D. Fotakis and S. Gritzalis. Efficient Heuristic Algorithms for Correcting the Cascade Vulnerability Problem for Interconnected Networks. Computer Communications 29, pp. 21092122, Elsevier, 2006. S. Likothanassis, G. Beligiannis, D. Fotakis, D. Fragoudis, and K. Giotopoulos. An Evolutionary Computation Technique For User Profile Optimization. International Journal of Computers and Their Applications – ISCA 10(1), 2002. S. Katsikas, S. Likothanassis, G. Beligiannis, K. Berketis and D. Fotakis. Genetically Determined Variable Structure Multiple Model Estimation. IEEE Transactions on Signal Processing 49(10), pp. 22532261, 2001. 

Recent Submissions  D. Fotakis. Memoryless Facility Location in One Pass. Full version submitted for journal publication, 2006. Extended abstract in STACS '06. LNCS 3884, pp. 608620, 2006.  
Chapters in Books and Survey Articles 
D. Fotakis, S. Kontogiannis, P. Panagopoulou, C. Raptopoulos, P. Spirakis.
Algorithmic Issues in Coalitional and Dynamic Network Games. F. Meyer
auf der Heide and B. Monien (eds.), New Trends in Parallel and Distributed
Computing, HNIVerlagsschriftenreihe 181, pp. 2542, Heinz
Nixdorf Institut, Universität Paderborn, 2006. D. Fotakis and P. Spirakis. Assignment of Reusable and NonReusable Frequencies. P.M. Pardalos, A. Migdalas, and R. Burkard (eds.), Combinatorial and Global Optimization, pp. 7593, World Scientific, 2001. D. Fotakis and P. Spirakis. Machine Partitioning and Scheduling under FaultTolerance Constraints. P.M. Pardalos (ed.), Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems, NonConvex Optimization and its Applications 42, pp. 209244, Kluwer, 2000. D. Fotakis, G. Pantziou, G. Pentaris, and P. Spirakis. Frequency Assignment in Mobile and Radio Networks. M. Mavronicolas, M. Merritt, and N. Shavit (eds.), Networks in Distributed Computing, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 45, pp. 7390, American Mathematical Society, 1999. D. Fotakis and P. Spirakis. Minimum Congestion Redundant Assignments: Complexity and Efficiency. MingYang Kao (ed.), Encyclopedia of Algorithms, Springer, 2007. D. Fotakis, S. Nikoletseas, V. Papadopoulou, P. Spirakis. Hardness Results and Efficient Approximations for Frequency Assignment Problems and the Radio Coloring Problem. Bulletin of the EATCS 75, pp. 152181, 2001. 

Conference Publications 
D. Fotakis. Congestion Games with Linearly Independent Paths: Convergence Time and
Price of Anarchy. Symposium on Algorithmic Game Theory  SAGT '08,
LNCS 4997, pp. 3345, 2008.
D. Fotakis, A. Kaporis, and P. Spirakis. Atomic Congestion Games: Fast, Myopic, and Concurrent. Symposium on Algorithmic Game Theory  SAGT '08, LNCS 4997, pp. 121132, 2008. D. Fotakis and P. Spirakis. CostBalancing Tolls for Atomic Network Congestion Games. Workshop on Internet and Network Economics  WINE '07, LNCS 4858, pp. 179190, 2007. D. Fotakis. Stackelberg Strategies for Atomic Congestion Games. European Symposium on Algorithms  ESA '07, LNCS 4698, pp. 299310, 2007. D. Fotakis and P. Spirakis. CostBalancing Tolls for Atomic Network Congestion Games. Workshop on Internet and Network Economics  WINE '07, LNCS, 2007. D. Fotakis, S. Kontogiannis, and P. Spirakis. Atomic Congestion Games Among Coalitions. International Colloquium on Automata, Languages, and Programming – ICALP ’06, LNCS 4051, pp. 573584, 2006. D. Fotakis. Memoryless Facility Location in One Pass. Symposium on Theoretical Aspects of Computer Science  STACS '06. LNCS 3884, pp. 608620, 2006. D. Fotakis, S. Kontogiannis, and P. Spirakis. Symmetry in Network Congestion Games: Pure Equilibria and Anarchy Cost. Workshop on Approximation and Online Algorithms  WAOA ’05, LNCS 3879, pp. 161175, 2006. D. Fotakis. A PrimalDual Algorithm for Online NonUniform Facility Location. Panhellenic Conference on Informatics  PCI ’05, LNCS 3746, pp. 4756, 2005. D. Fotakis. Incremental Algorithms for Facility Location and kMedian. European Symposium on Algorithms – ESA ’04, LNCS 3221, pp. 347358, 2004. D. Fotakis, S. Kontogiannis, and P. Spirakis. Selfish Unsplittable Flows. International Colloquium on Automata, Languages, and Programming – ICALP ’04, LNCS 3142, pp. 593605, 2004.D. Fotakis. On the Competitive Ratio for Online Facility Location. International Colloquium on Automata, Languages and Programming  ICALP '03, LNCS 2719, pp. 637652, 2003. D. Fotakis, R. Pagh, P. Sanders, and P. Spirakis. Space Efficient Access Tables with Worst Case Constant Access Time. Symposium on Theoretical Aspects of Computer Science  STACS '03, LNCS 2607, pp. 271282, 2003. D. Fotakis, S. Kontogiannis, E. Koutsoupias, M. Mavronicolas, and P. Spirakis. The Structure and Complexity of Nash Equilibria for a Selfish Routing Game. International Colloquium on Automata, Languages and Programming  ICALP '02, LNCS 2380, pp. 123134, 2002. M. Andreou, D. Fotakis, S. Nikoletseas, V. Papadopoulou, and P. Spirakis. On Radiocoloring Hierarchically Specified Planar Graphs: PSPACECompleteness and Approximations. Mathematical Foundations of Computer Science  MFCS '02, LNCS 2420, pp. 8192, 2002. D. Fotakis, S. Nikoletseas, V. Papadopoulou, and P. Spirakis. Radiocolorings in Periodic Planar Graphs: PSPACECompleteness and Efficient Approximations for the Optimal Range of Frequencies. Graph Theoretical Concepts in Computer Science  WG '02, LNCS 2573, pp. 223234, 2002. D. Fotakis, S. Likothanasis, and S. Stefanakos. An Evolutionary Approach to Graph Coloring. Evolutionary Programming in Combinatorial Optimization  EvoCOP 2001, LNCS 2037, 120129, 2001. D. Fotakis, S. Nikoletseas, V. Papadopoulou, and P. Spirakis. NPCompleteness Results and Efficient Approximations for Radio Coloring in Planar Graphs. Mathematical Foundations of Computer Science  MFCS '00, LNCS 1893, 363372, 2000. D. Fotakis and P. Spirakis. Efficient Redundant Assignments under FaultTolerance Constraints. Approximation Algorithms for Combinatorial Optimization Problems  APPROX '99, LNCS 1671, 156167, 1999. D. Fotakis and P. Spirakis. An Upper Bound on Redundant Assignment Reliability. Conference in the Memory of Paul Erdos and His Mathematics, 6973, 1999. D. Fotakis and P. Spirakis. A Hamiltonian Approach to the Assignment of NonReusable Frequencies. Foundations of Software Technology and Theoretical Computer Science  FCS&TCS '98, LNCS 1530, 1829, 1998. D. Fotakis and P. Spirakis. (poly(loglog n), poly(loglog n))restricted verifiers are unlikely to exist for languages in NP. Mathematical Foundations of Computer Science  MFCS '96, LNCS 1113, 360371, 1996. 

Technical Reports 
D. Fotakis and P. Spirakis. Random Walks, Conditional Hitting Sets and
Partial Derandomization. Electronic Colloquium on Computational
Complexity (ECCC), Technical Report 98049, 1998.
D. Fotakis and P. Spirakis. Graph Properties that Facilitate Travelling.
Electronic Colloquium on Computational Complexity (ECCC), Technical
Report 98031, 1998.
