up

Publications - Elias Koutsoupias


TOPICS
Internet, Games, Power Laws
Online Algorithms
Approximation Algorithms
Indexing Schemes
Miscellaneous

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   Pdf   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   Pdf   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   Pdf   BibTeX 
 

George Christodoulou, Elias Koutsoupias, Akash Nanavati: Coordination mechanisms. Theor. Comput. Sci. 410(36): 3327-3336, 2009.
Abstract  Postscript   Pdf   BibTeX 
 

G. Christodoulou, E. Koutsoupias, and P. Spirakis. On the performance of approximate equilibria in congestion games. In ESA 2009: 251-262.
Abstract  Postscript   Pdf   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   Pdf   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   Pdf   BibTeX 
 

E. Koutsoupias, P. Panagopoulou, and P. Spirakis. Selfish Load Balancing Under Partial Knowledge. MFCS 2007: 609-620
Abstract  Postscript   Pdf   BibTeX 
 

E. Koutsoupias and A. Vidali. A Lower Bound of 1+phi for Truthful Scheduling Mechanisms. MFCS, 2007: 454-464.
Abstract  Postscript   Pdf   BibTeX 
 

G. Christodoulou, E. Koutsoupias, and A. Kovacs. Mechanism Design for Fractional Scheduling on Unrelated Machines. ICALP 2007: 40-52
Abstract  Postscript   Pdf   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   Pdf   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   Pdf   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   Pdf   BibTeX 
 

E. Koutsoupias. Coordination mechanisms for congestion games. Sigact News, Vol. 35, No. 4, December 2004, pages 58--71.
Abstract  Postscript   Pdf   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   Pdf   BibTeX 
 

E. Koutsoupias. Selfish task allocation. Bulletin of EATCS, Number 81, pages 79--88, October 2003.
Abstract  Postscript   Pdf   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   Pdf   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   Pdf   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   Pdf   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   Pdf   BibTeX 
 

Online Algorithms

Luca Becchetti, Elias Koutsoupias: Competitive Analysis of Aggregate Max in Windowed Streaming. In ICALP (1) 2009: 156-170.
Abstract  Postscript   Pdf   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   Pdf   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   Pdf   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   Pdf   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   Pdf   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   Pdf   BibTeX 
 

E. Koutsoupias and C. Papadimitriou. Beyond competitive analysis. SIAM Journal on Computing, 30(1):300--317, 2000.
Abstract  Postscript   Pdf   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   Pdf   BibTeX 
 

X. Deng, E. Koutsoupias, and P. MacKenzie. Competitive implementation of parallel programs. Algorithmica, 23(1):14--30, 1999.
Abstract  Postscript   Pdf   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   Pdf   BibTeX 
 

E. Koutsoupias and C. Papadimitriou. The 2-evader problem. Information Processing Letters 57(5):249--252, March 1996.
Abstract  Postscript   Pdf   BibTeX 
 

E. Koutsoupias and C. Papadimitriou. On the k-server conjecture. Journal of the ACM, 42(5):971--983, September 1995.
Abstract  Postscript   Pdf   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   Pdf   BibTeX 
 

Approximation Algorithms

G. Christodoulou, E. Koutsoupias, and A. Vidali. A lower bound for scheduling mechanisms. SODA 2007: 1163-1170.
Abstract  Postscript   Pdf   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   Pdf   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   Pdf   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   Pdf   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   Pdf   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   Pdf   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   Pdf   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   Pdf   BibTeX 
 

Miscellaneous

E. Gafni and E. Koutsoupias. Three-processor tasks are undecidable. SIAM Journal on Computing, 28(3):970--983, 1999.
Abstract  Postscript   Pdf   BibTeX 
 

E. Koutsoupias. Improvements on Khrapchenko's theorem. Theoretical Computer Science, 116(2):399--403, August 1993.
Abstract  Postscript   Pdf   BibTeX 
 

E. Koutsoupias and C. H. Papadimitriou. On the greedy algorithm for satisfiability. Information Processing Letters, 43(1):53--55, August 1992.
Abstract  Postscript   Pdf   BibTeX 
 



Elias Koutsoupias / elias_at_di.uoa.gr