Decoration
max planck institut
informatik
mpii logo Minerva of the Max Planck Society

Homepage

Spyros Angelopoulos


I was a Postdoc at MPI-INF from 2007-2010. I am currently with CNRS, France. My new homepage is here


NOTE: I do not read frequently my old MPI email. Please consult my new contact info.


Research Interests


  • Design and analysis of algorithms
  • Online algorithms and algorithms with incomplete information
  • Applications in AI: Planning and scheduling under uncertainty, design and analysis of interruptible algorithms

Publications


    Journal publications


  • Randomized Priority Algorithms [pdf]
    Spyros Angelopoulos and Allan Borodin.
    Theoretical Computer Science, 2010. (to appear.)

  • Tight Bounds for Quasi-random Rumor Spreading [ pdf ]
    Spyros Angelopoulos, Benjamin Doerr, Anna Huber, Konstantinos Panagiotou
    Electronic Journal of Combinatorics, 2009.

  • The Power of Priority Algorithms For Facility Location and Set Cover [ pdf ]
    Spyros Angelopoulos and Allan Borodin.
    Invited paper, Algorithmica , 2004. .

    Conference publications


  • On the Competitiveness of the Online Asymmteric and Euclidean Steiner Tree Problems [ pdf ]
    Spyros Angelopoulos
    In Proc. of the 7th Workshop on Approximation and Online Algorithms (WAOA), 2009. (to appear)

  • Online Priority Steiner Tree Problems [ pdf ]
    Spyros Angelopoulos
    In Proc. of the 11th Symposium on Algorithms and Data Structures (WADS), 2009. (to appear)

  • Interruptible Algorithms for Multi-Problem Solving [ pdf ]
    Spyros Angelopoulos and Alejandro Lopez-Ortiz
    In Proc. of the 21st International Joint Conference In Artificial Intelligence (IJCAI), 2009.

  • Paging and List Update under Bijective Analysis [ pdf ]
    Spyros Angelopoulos and Pascal Schweitzer
    Submitted for journal publication. Conference version in Proc. of the 20th ACM/SIAM Symposium on Discrete Algorithms (SODA), 2009

  • A Near-Tight Bound for the Online Steiner Tree Problem in Graphs of Bounded Asymmetry [ pdf ]
    Spyros Angelopoulos
    In Proc. of the 16th European Symposium on Algorithms (ESA), 2008.

  • Optimal Scheduling of Contract Algorithms with Soft Deadlines [ pdf ]
    Spyros Angelopoulos, Alejandro López-Ortiz, Angele Hamel.
    In Proc. of the 23rd National Conference on Artificial Intelligence (AAAI), 2008.

  • List Update with Locality of Reference [ pdf ]
    Spyros Angelopoulos, Reza Dorrigiv, Alejandro López-Ortiz.
    Submitted for journal publication. Conference version in in Proc. of the 8th Latin-American Theoretical Informatics Symposium (LATIN), 2008.

  • Improved Bounds for the Online Steiner Tree Problem in Graphs of Bounded Edge Asymmetry [ pdf ]
    Spyros Angelopoulos
    In Proc. of the 18th ACM/SIAM Symposium on Discrete Algorithms (SODA), 2007.

  • On the Separation and Equivalence of Paging Strategies [ pdf ]
    Spyros Angelopoulos, Reza Dorrigiv, Alejandro López-Ortiz.
    Submitted for journal publication. Conference version in Proc. of the 18th ACM/SIAM Symposium on Discrete Algorithms (SODA), 2007.

  • Optimal Scheduling of Contract Algorithms for Anytime Problems [ pdf ]
    Spyros Angelopoulos, Alejandro Lopez-Ortiz, Angele M. Hamel.
    Submitted for journal publication. Conference version in Proc. of the 21st National Conference on Artificial Intelligence (AAAI), 2006.

  • The Node-Weighted Steiner Problem in Graphs of Restricted Node Weights [ pdf ]
    Spyros Angelopoulos.
    In Proc. of the 10th Scandinavian Workshop on Algorithm Theory (SWAT), 2006 .

  • Online Algorithms for Market Equilibria [ pdf ]
    Spyros Angelopoulos, Atish DasSarma, Avner Magen, and Anastasios Viglas.
    In Proc. of the 11th Annual International Conference on Computing and Combinatorics (COCOON), 2005 .

  • Order-Preserving Transformations and Greedy-Like Algorithms [ pdf ]
    Spyros Angelopoulos.
    In Proc. of the 2nd International Workshop on Approximation and Online Algorithms (WAOA), 2004" .

  • Randomized Priority Algorithms [ pdf ]
    Spyros Angelopoulos
    Proc. of the 1st International Workshop on Approximation and Online Algorithms (WAOA), 2003" .

  • The Power of Priority Algorithms For Facility Location and Set Cover [ pdf ]
    Spyros Angelopoulos and Allan Borodin.
    Proc. of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), 2002 .


Teaching


During Fall 2008 I was co-instructor for the graduate course Approximation Algorithms with Nicole Megow and Rajeev Raman.

I was previously Instructor for the core undergraduate courses CS341--Algorithms (Winter 2007, Spring 2007) and CS240--Data Structures and Data Management (Summer 2005), at the University of Waterloo.


Recent Positions


From September 2004 to December 2006 I was a Postdoctoral Fellow with the David. R. Cheriton School of Computer Science, University of Waterloo.


Education


  • 2005: Ph.D. Degree in Computer Science, University of Toronto. Title of Thesis: "The Approximation Power of Priority Algorithms". Supervisor: Allan B. Borodin. [pdf]
  • 1999: M.Sc. in Computer Science, University of Toronto. Title of Thesis: "Efficient Online Algorithms for Multicasting with Bandwidth and Delay Guarantees". Supervisor: Irene Katzela.
  • 1997: B.Sc. in Computer Science and Engineering, Department of Computer Engineering and Informatics, University of Patras, Greece.

Research Interests



Publications



Teaching


During Fall 2008 I was co-instructor for the graduate course Approximation Algorithms with Nicole Megow and Rajeev Raman.

I was previously Instructor for the core undergraduate courses CS341--Algorithms (Winter 2007, Spring 2007) and CS240--Data Structures and Data Management (Summer 2005), at the University of Waterloo.


Recent Positions


From September 2004 to December 2006 I was a Postdoctoral Fellow with the David. R. Cheriton School of Computer Science, University of Waterloo.


Education


  • 2005: Ph.D. Degree in Computer Science, University of Toronto. Title of Thesis: "The Approximation Power of Priority Algorithms". Supervisor: Allan B. Borodin. [pdf]
  • 1999: M.Sc. in Computer Science, University of Toronto. Title of Thesis: "Efficient Online Algorithms for Multicasting with Bandwidth and Delay Guarantees". Supervisor: Irene Katzela.
  • 1997: B.Sc. in Computer Science and Engineering, Department of Computer Engineering and Informatics, University of Patras, Greece.