Publications - Elias Koutsoupias
Internet, Games, Power Laws
George Christodoulou and Elias Koutsoupias: Mechanism design for scheduling. Bulletin of the European Association for Theoretical Computer Science (BEATCS) 97:39-59, February 2009.
| Abstract | Postscript | BibTeX |
George Christodoulou, Elias Koutsoupias, Angelina Vidali: A Lower Bound for Scheduling Mechanisms. Algorithmica 55(4): 729-740 (2009). G. Christodoulou, E. Koutsoupias, and A. Vidali. A lower bound for scheduling mechanisms. SODA 2007: 1163-1170.
| Abstract | Postscript | BibTeX |
Elias Koutsoupias, Christos H. Papadimitriou: Worst-case equilibria. Computer Science Review 3(2): 65-69, 2009. E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In 16th Annual Symposium on Theoretical Aspects of Computer Science}, pages 404--413, Trier, Germany, 4--6 March 1999.
| Abstract | Postscript | BibTeX |
George Christodoulou, Elias Koutsoupias, Akash Nanavati: Coordination mechanisms. Theor. Comput. Sci. 410(36): 3327-3336, 2009.
| Abstract | Postscript | BibTeX |
G. Christodoulou, E. Koutsoupias, and P. Spirakis. On the performance of approximate equilibria in congestion games. In ESA 2009: 251-262.
| Abstract | Postscript | BibTeX |
D. Fotakis, S. Kontogiannis, E. Koutsoupias, M. Mavronicolas, and P. Spirakis. The Structure and Complexity of Nash Equilibria for a Selfish Routing Game. Theoretical Computer Science, 410(36): 3305-3326, 2009.
| Abstract | Postscript | BibTeX |
G. Christodoulou, E. Koutsoupias, and A. Vidali. A characterization of 2-player mechanisms for scheduling. In ESA, Karlsruhe, Germany, 15-17 September 2008.
| Abstract | Postscript | BibTeX |
E. Koutsoupias, P. Panagopoulou, and P. Spirakis. Selfish Load Balancing Under Partial Knowledge. MFCS 2007: 609-620
| Abstract | Postscript | BibTeX |
E. Koutsoupias and A. Vidali. A Lower Bound of 1+phi for Truthful Scheduling Mechanisms. MFCS, 2007: 454-464.
| Abstract | Postscript | BibTeX |
G. Christodoulou, E. Koutsoupias, and A. Kovacs. Mechanism Design for Fractional Scheduling on Unrelated Machines. ICALP 2007: 40-52
| Abstract | Postscript | BibTeX |
Georgios Kouroupas, Elias Koutsoupias, Christos H. Papadimitriou, and Martha Sideri. Experiments with an Economic Model of the Worldwide Web. WINE 2005 (Internet and Network Economics: First International Workshop), pages 46-54, Hong Kong, China, December 15-17, 2005.
| Abstract | Postscript | BibTeX |
G. Christodoulou and E. Koutsoupias. On the price of anarchy and stability of correlated equilibria of linear congestion games. ESA 2005, 13th Annual European Symposium, pages 59-70, Palma de Mallorca, Spain, October 3-6, 2005.
| Abstract | Postscript | BibTeX |
G. Christodoulou and E. Koutsoupias. The price of anarchy of finite congestion games. STOC, pages 67--73, Baltimore, MD,USA, 22--24 May, 2005.
| Abstract | Postscript | BibTeX |
E. Koutsoupias. Coordination mechanisms for congestion games. Sigact News, Vol. 35, No. 4, December 2004, pages 58--71.
| Abstract | Postscript | BibTeX |
C. Brito, E. Koutsoupias, and S. Vaya. Competitive analysis of organization networks or multicast acknowledgement: how much to wait? In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 627--635, New Orleans, Louisiana, USA, January 11-14, 2004.
| Abstract | Postscript | BibTeX |
E. Koutsoupias. Selfish task allocation. Bulletin of EATCS, Number 81, pages 79--88, October 2003.
| Abstract | Postscript | BibTeX |
E. Koutsoupias, M. Mavronikolas, and P. Spirakis. Approximate equilibria and ball fusion. Theory of Computing Systems 36(6), pages 683--693, 2003.
| Abstract | Postscript | BibTeX |
A. Fabrikant, E. Koutsoupias, and C. Papadimitriou. Heuristically Optimized Trade-offs: A New Paradigm for Power Laws in the Internet. In Proceedings of the 29th International Colloquium on Automata, Languages, and Programming (ICALP), pages 110--122, Malaga, Spain, July 2002.
| Abstract | Postscript | BibTeX |
R. Karp, E. Koutsoupias, C. Papadimitriou, and S. Shenker. Combinatorial optimization in congestion control. In Proceedings of the 41th Annual Symposium on Foundations of Computer Science, pages 66--74, Redondo Beach, CA, 12--14 November 2000.
| Abstract | Postscript | BibTeX |
E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In 16th Annual Symposium on Theoretical Aspects of Computer Science}, pages 404--413, Trier, Germany, 4--6 March 1999.
| Abstract | Postscript | BibTeX |
Online Algorithms
Luca Becchetti, Elias Koutsoupias: Competitive Analysis of Aggregate Max in Windowed Streaming. In ICALP (1) 2009: 156-170.
| Abstract | Postscript | BibTeX |
C. Brito, E. Koutsoupias, and S. Vaya. Competitive analysis of organization networks or multicast acknowledgement: how much to wait? In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 627--635, New Orleans, Louisiana, USA, January 11-14, 2004.
| Abstract | Postscript | BibTeX |
E. Koutsoupias and D. S. Taylor. The CNN problem and other k-server variants. In Theoretical Computer Science, 324(2-3):347--359, September 2004.
| Abstract | Postscript | BibTeX |
Y. Bartal and E. Koutsoupias. On the competitive ratio of the work function algorithm for the k-server problem. In Theoretical Computer Science, 324(2-3):337--345, September 2004.
| Abstract | Postscript | BibTeX |
E. Koutsoupias and A. Nanavati. The online matching problem on a line. Workshop on approximation and online algorithms, pages 179--191, Budapest 2003.
| Abstract | Postscript | BibTeX |
M. Chrobak, E. Koutsoupias, and J. Noga. More on Randomized On-line Algorithms for Caching. Theoretical Computer Science. 290(3): 1997-2008, 2003.
| Abstract | Postscript | BibTeX |
E. Koutsoupias and C. Papadimitriou. Beyond competitive analysis. SIAM Journal on Computing, 30(1):300--317, 2000.
| Abstract | Postscript | BibTeX |
E. Koutsoupias. Weak adversaries for the k-server problem. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, New York City, NY, pages 444--449, 17--19 October 1999.
| Abstract | Postscript | BibTeX |
X. Deng, E. Koutsoupias, and P. MacKenzie. Competitive implementation of parallel programs. Algorithmica, 23(1):14--30, 1999.
| Abstract | Postscript | BibTeX |
E. Koutsoupias, C. Papadimitriou, and M. Yannakakis. Searching a fixed graph. In International Colloquium on Automata, Languages, and Programming, pages 280--289, Paderborn, Germany, 8--12 July 1996.
| Abstract | Postscript | BibTeX |
E. Koutsoupias and C. Papadimitriou. The 2-evader problem. Information Processing Letters 57(5):249--252, March 1996.
| Abstract | Postscript | BibTeX |
E. Koutsoupias and C. Papadimitriou. On the k-server conjecture. Journal of the ACM, 42(5):971--983, September 1995.
| Abstract | Postscript | BibTeX |
E. Koutsoupias. On-line algorithms and the k-server conjecture. PhD thesis, University of California, San Diego, La Jolla, California, June 1994.
| Abstract | Postscript | BibTeX |
Approximation Algorithms
G. Christodoulou, E. Koutsoupias, and A. Vidali. A lower bound for scheduling mechanisms. SODA 2007: 1163-1170.
| Abstract | Postscript | BibTeX |
E. Koutsoupias, C. Papadimitriou, and M. Yannakakis. Searching a fixed graph. In International Colloquium on Automata, Languages, and Programming, pages 280--289, Paderborn, Germany, 8--12 July 1996.
| Abstract | Postscript | BibTeX |
M. Grigni, E. Koutsoupias, and C. Papadimitriou. An approximation scheme for planar graph TSP. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pages 640--645, Milwaukee, Wisconsin, 23--25 October 1995.
| Abstract | Postscript | BibTeX |
E. Koutsoupias, C. H. Papadimitriou, and M. Sideri. On the optimal bisection of a polygon. ORSA Journal on Computing, 4(4):435--438, Fall 1992.
| Abstract | Postscript | BibTeX |
Indexing Schemes
J. M. Hellerstein, E. Koutsoupias, D. P. Miranker, C. H. Papadimitriou, and V. Samoladas. On a model of indexability and its bounds for range queries. Journal of the ACM (JACM) 49(1):35--55, 2002.
| Abstract | Postscript | BibTeX |
E. Koutsoupias and D. S. Taylor. Indexing schemes for random points. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 596--602, Baltimore, Maryland, 17--19 January 1999.
| Abstract | Postscript | BibTeX |
E. Koutsoupias and D. S. Taylor. Tight bounds for 2-dimensional indexing schemes. In Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Seattle, Washington, June 1--4, 1998.
| Abstract | Postscript | BibTeX |
J. M. Hellerstein, E. Koutsoupias, and C. H. Papadimitriou. On the Analysis of Indexing Schemes. In Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 249--256, Tucson, Arizona, 12--15 May 1997.
| Abstract | Postscript | BibTeX |
Miscellaneous
E. Gafni and E. Koutsoupias. Three-processor tasks are undecidable. SIAM Journal on Computing, 28(3):970--983, 1999.
| Abstract | Postscript | BibTeX |
E. Koutsoupias. Improvements on Khrapchenko's theorem. Theoretical Computer Science, 116(2):399--403, August 1993.
| Abstract | Postscript | BibTeX |
E. Koutsoupias and C. H. Papadimitriou. On the greedy algorithm for satisfiability. Information Processing Letters, 43(1):53--55, August 1992.
| Abstract | Postscript | BibTeX |
Elias Koutsoupias / elias_at_di.uoa.gr