Curriculum Vitae - Dimitris Fotakis
March 2009


Contact Information

Division of Computer Science
School of Electrical and Computer Engineering
National Technical University of Athens
15780 Athens, GREECE

  Phone: +30 210 7724302
  Fax: +30 210 7722509
  URL:

http://www.softlab.ntua.gr/~fotakis

   

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.  

Post-Doctoral Researcher (Sept. 2001 - Aug. 2003), Max-Planck-Institut für Informatik, Algorithms and Complexity Group (AG-1). 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, 11-13 September, 2006.

1st Symposium on Algorithmic Game Theory (SAGT 08), Paderborn, April 30 - May 2, 2008.

12th Pan-Hellenic Conference on Informatics (PCI 08), Samos, August 28 - 30, 2008.

 

Journal Articles D. Fotakis and P. Spirakis. Cost-Balancing 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. 1-57, 2008.

D. Fotakis. Incremental Algorithms for Facility Location and k-Median. Theoretical Computer Science 361, Special Issue on Approximation and Online Algorithms, pp. 275-313, 2006.

D. Fotakis. A Primal-Dual Algorithm for Online Non-Uniform Facility Location. Journal of Discrete Algorithms 5, pp. 141-148, 2006.

D. Fotakis, S. Nikoletseas, V. Papadopoulou, and P. Spirakis. Radiocolorings in Periodic Planar Graphs: PSPACE-Completeness and Efficient Approximations for the Optimal Range of Frequencies. Journal of Discrete Algorithms 4, pp. 433-454, 2006.

D. Fotakis, S. Kontogiannis, and P. Spirakis. Selfish Unsplittable Flows. Theoretical Computer Science 348, Special Issue on ICALP 2004, pp. 226-239, 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. 229-248, 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. 514-538, 2005.

D. Fotakis and P. Spirakis. Minimum Congestion Redundant Assignments to Tolerate Random Faults. Algorithmica 32, 396-422, Springer-Verlag, 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, 121-180, 2001.

D. Fotakis and S. Gritzalis. Efficient Heuristic Algorithms for Correcting the Cascade Vulnerability Problem for Interconnected Networks. Computer Communications 29, pp. 2109-2122, 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. 2253-2261, 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. 608-620, 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, HNI-Verlagsschriftenreihe 181, pp. 25-42, Heinz Nixdorf Institut, Universität Paderborn, 2006.

D. Fotakis and P. Spirakis. Assignment of Reusable and Non-Reusable Frequencies. P.M. Pardalos, A. Migdalas, and R. Burkard (eds.), Combinatorial and Global Optimization, pp. 75-93, World Scientific, 2001.

D. Fotakis and P. Spirakis. Machine Partitioning and Scheduling under Fault-Tolerance Constraints. P.M. Pardalos (ed.), Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems, Non-Convex Optimization and its Applications 42, pp. 209-244, 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. 73-90, American Mathematical Society, 1999.

D. Fotakis and P. Spirakis. Minimum Congestion Redundant Assignments: Complexity and Efficiency. Ming-Yang 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. 152-181, 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. 33-45, 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. 121-132, 2008.

D. Fotakis and P. Spirakis. Cost-Balancing Tolls for Atomic Network Congestion Games. Workshop on Internet and Network Economics - WINE '07, LNCS 4858, pp. 179-190, 2007.

D. Fotakis. Stackelberg Strategies for Atomic Congestion Games. European Symposium on Algorithms - ESA '07, LNCS 4698, pp. 299-310, 2007.

D. Fotakis and P. Spirakis. Cost-Balancing 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. 573-584, 2006.

D. Fotakis. Memoryless Facility Location in One Pass. Symposium on Theoretical Aspects of Computer Science - STACS '06. LNCS 3884, pp. 608-620, 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. 161-175, 2006.

D. Fotakis. A Primal-Dual Algorithm for Online Non-Uniform Facility Location. Panhellenic Conference on Informatics - PCI 05, LNCS 3746, pp. 47-56, 2005.

D. Fotakis. Incremental Algorithms for Facility Location and k-Median. European Symposium on Algorithms ESA 04, LNCS 3221, pp. 347-358, 2004.

D. Fotakis, S. Kontogiannis, and P. Spirakis. Selfish Unsplittable Flows. International Colloquium on Automata, Languages, and Programming ICALP 04, LNCS 3142, pp. 593-605, 2004.

D. Fotakis. On the Competitive Ratio for Online Facility Location. International Colloquium on Automata, Languages and Programming - ICALP '03, LNCS 2719, pp. 637-652, 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. 271-282, 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. 123-134, 2002.

M. Andreou, D. Fotakis, S. Nikoletseas, V. Papadopoulou, and P. Spirakis. On Radiocoloring Hierarchically Specified Planar Graphs: PSPACE-Completeness and Approximations. Mathematical Foundations of Computer Science - MFCS '02, LNCS 2420, pp. 81-92, 2002.

D. Fotakis, S. Nikoletseas, V. Papadopoulou, and P. Spirakis. Radiocolorings in Periodic Planar Graphs: PSPACE-Completeness and Efficient Approximations for the Optimal Range of Frequencies. Graph Theoretical Concepts in Computer Science - WG '02, LNCS 2573, pp. 223-234, 2002.

D. Fotakis, S. Likothanasis, and S. Stefanakos. An Evolutionary Approach to Graph Coloring. Evolutionary Programming in Combinatorial Optimization - EvoCOP 2001, LNCS 2037, 120-129, 2001.

D. Fotakis, S. Nikoletseas, V. Papadopoulou, and P. Spirakis. NP-Completeness Results and Efficient Approximations for Radio Coloring in Planar Graphs. Mathematical Foundations of Computer Science - MFCS '00, LNCS 1893, 363-372, 2000.

D. Fotakis and P. Spirakis. Efficient Redundant Assignments under Fault-Tolerance Constraints. Approximation Algorithms for Combinatorial Optimization Problems - APPROX '99, LNCS 1671, 156-167, 1999.

D. Fotakis and P. Spirakis. An Upper Bound on Redundant Assignment Reliability. Conference in the Memory of Paul Erdos and His Mathematics, 69-73, 1999.

D. Fotakis and P. Spirakis. A Hamiltonian Approach to the Assignment of Non-Reusable Frequencies. Foundations of Software Technology and Theoretical Computer Science - FCS&TCS '98, LNCS 1530, 18-29, 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, 360-371, 1996.

Technical Reports D. Fotakis and P. Spirakis. Random Walks, Conditional Hitting Sets and Partial Derandomization. Electronic Colloquium on Computational Complexity (ECCC), Technical Report 98-049, 1998.

D. Fotakis and P. Spirakis. Graph Properties that Facilitate Travelling. Electronic Colloquium on Computational Complexity (ECCC), Technical Report 98-031, 1998.