Elias Koutsoupias : Publications

Journal papers

• [1]

  A Lower Bound of 1+φ for Truthful Scheduling Mechanisms

  Elias Koutsoupias and Angelina Vidali

  In Algorithmica. Vol. 66. No. 1. Pages 211−223. 2013.

  Details about A Lower Bound of 1+φ for Truthful Scheduling Mechanisms | BibTeX data for A Lower Bound of 1+φ for Truthful Scheduling Mechanisms

• [2]

  On the Competitive Ratio of Online Sampling Auctions

  Elias Koutsoupias and George Pierrakos

  In ACM Trans. Economics and Comput.. Vol. 1. No. 2. Pages 10. 2013.

  Details about On the Competitive Ratio of Online Sampling Auctions | BibTeX data for On the Competitive Ratio of Online Sampling Auctions

• [3]

  Competitive Analysis of Organization Networks or Multicast Acknowledgment: How Much to Wait?

  Carlos Fisch Brito‚ Elias Koutsoupias and Shailesh Vaya

  In Algorithmica. Vol. 64. No. 4. Pages 584−605. 2012.

  Details about Competitive Analysis of Organization Networks or Multicast Acknowledgment: How Much to Wait? | BibTeX data for Competitive Analysis of Organization Networks or Multicast Acknowledgment: How Much to Wait?

• [4]

  On the Performance of Approximate Equilibria in Congestion Games

  George Christodoulou‚ Elias Koutsoupias and Paul G. Spirakis

  In Algorithmica. Vol. 61. No. 1. Pages 116−140. 2011.

  Details about On the Performance of Approximate Equilibria in Congestion Games | BibTeX data for On the Performance of Approximate Equilibria in Congestion Games

• [5]

  Mechanism Design for Fractional Scheduling on Unrelated Machines

  G. Christodoulou‚ E. Koutsoupias and A. Kovács

  In ACM Transactions on Algorithms. Vol. 6. No. 2. 2010.

  Details about Mechanism Design for Fractional Scheduling on Unrelated Machines | BibTeX data for Mechanism Design for Fractional Scheduling on Unrelated Machines

• [6]

  Mechanism design for scheduling

  George Christodoulou and Elias Koutsoupias

  In Bulletin of the European Association for Theoretical Computer Science (BEATCS). Vol. 97. Pages 39−59. February, 2009.

  Details about Mechanism design for scheduling | BibTeX data for Mechanism design for scheduling

• [7]

  A Lower Bound for Scheduling Mechanisms

  George Christodoulou‚ Elias Koutsoupias and Angelina Vidali

  In Algorithmica. Vol. 55. No. 4. Pages 729−740. 2009.

  Details about A Lower Bound for Scheduling Mechanisms | BibTeX data for A Lower Bound for Scheduling Mechanisms

• [8]

  The k−server problem

  Elias Koutsoupias

  In Computer Science Review. Vol. 3. No. 2. Pages 105−118. 2009.

  Details about The k−server problem | BibTeX data for The k−server problem

• [9]

  Worst−case equilibria

  Elias Koutsoupias and Christos H. Papadimitriou

  In Computer Science Review. Vol. 3. No. 2. Pages 65−69. 2009.

  Details about Worst−case equilibria | BibTeX data for Worst−case equilibria

• [10]

  Coordination mechanisms

  George Christodoulou‚ Elias Koutsoupias and Akash Nanavati

  In Theor. Comput. Sci.. Vol. 410. No. 36. Pages 3327–3336. 2009.

  Details about Coordination mechanisms | BibTeX data for Coordination mechanisms

• [11]

  The structure and complexity of Nash equilibria for a selfish routing game

  Dimitris Fotakis‚ Spyros C. Kontogiannis‚ Elias Koutsoupias‚ Marios Mavronicolas and Paul G. Spirakis

  In Theor. Comput. Sci.. Vol. 410. No. 36. Pages 3305−3326. 2009.

  Details about The structure and complexity of Nash equilibria for a selfish routing game | BibTeX data for The structure and complexity of Nash equilibria for a selfish routing game

• [12]

  Coordination mechanisms for congestion games.

  E. Koutsoupias

  In Sigact News. Vol. 35. No. 4. Pages 58–71. December, 2004.

  Details about Coordination mechanisms for congestion games. | BibTeX data for Coordination mechanisms for congestion games.

• [13]

  On the Competitive Ratio of the Work Function Algorithm for the k−Server Problem

  Y. Bartal and E. Koutsoupias

  In Theoretical Computer Science. Vol. 324. No. 2−3. Pages 337–345. 2004.

  An early version appeared in STACS 2000

  Details about On the Competitive Ratio of the Work Function Algorithm for the k−Server Problem | BibTeX data for On the Competitive Ratio of the Work Function Algorithm for the k−Server Problem

• [14]

  The CNN problem and other k−server variants

  E. Koutsoupias and D. S. Taylor

  In Theoretical Computer Science. Vol. 324. No. 2−3. Pages 347–359. 2004.

  An early version appeared in STACS 2000

  Details about The CNN problem and other k−server variants | BibTeX data for The CNN problem and other k−server variants

• [15]

  Selfish task allocation

  E. Koutsoupias

  In Bulletin of EATCS. Vol. 81. Pages 79–88. October, 2003.

  Details about Selfish task allocation | BibTeX data for Selfish task allocation

• [16]

  More on Randomized On−line Algorithms for Caching

  M. Chrobak‚ E. Koutsoupias and J. Noga

  In Theoretical Computer Science. Vol. 290. No. 3. Pages 1997–2008. 2003.

  Details about More on Randomized On−line Algorithms for Caching | BibTeX data for More on Randomized On−line Algorithms for Caching

• [17]

  Approximate equilibria and ball fusion

  E. Koutsoupias‚ M. Mavronikolas and P. Spirakis

  In Theory of Computing Systems. Vol. 36. No. 6. Pages 683–693. 2003.

  Details about Approximate equilibria and ball fusion | BibTeX data for Approximate equilibria and ball fusion

• [18]

  On a model of indexability and its bounds for range queries

  Joseph M. Hellerstein‚ Elias Koutsoupias‚ Daniel P. Miranker‚ Christos H. Papadimitriou and Vasilis Samoladas

  In Journal of the ACM (JACM). Vol. 49. No. 1. Pages 35–55. 2002.

  Details about On a model of indexability and its bounds for range queries | BibTeX data for On a model of indexability and its bounds for range queries | DOI (http://doi.acm.org/10.1145/505241.505244)

• [19]

  Beyond competitive analysis

  E. Koutsoupias and C. H. Papadimitriou

  In SIAM Journal on Computing. Vol. 30. No. 1. Pages 394–400. 2000.

  Details about Beyond competitive analysis | BibTeX data for Beyond competitive analysis

• [20]

  Competitive implementation of parallel programs

  X. Deng‚ E. Koutsoupias and P. MacKenzie

  In Algorithmica. Vol. 23. No. 1. Pages 14–30. 1999.

  Details about Competitive implementation of parallel programs | BibTeX data for Competitive implementation of parallel programs

• [21]

  Three−Processor Tasks Are Undecidable

  E. Gafni and E. Koutsoupias

  In SIAM Journal on Computing. Vol. 28. No. 3. Pages 970–983. 1999.

  Details about Three−Processor Tasks Are Undecidable | BibTeX data for Three−Processor Tasks Are Undecidable

• [22]

  The 2−evader problem

  E. Koutsoupias and C. Papadimitriou

  In Information Processing Letters. Vol. 57. No. 5. Pages 249–252. March, 1996.

  Details about The 2−evader problem | BibTeX data for The 2−evader problem

• [23]

  On the k−Server Conjecture

  E. Koutsoupias and C. Papadimitriou

  In Journal of the ACM. Vol. 42. No. 5. Pages 971–983. September, 1995.

  Details about On the k−Server Conjecture | BibTeX data for On the k−Server Conjecture

• [24]

  Improvements on Khrapchenko's theorem

  E. Koutsoupias

  In Theoretical Computer Science. Vol. 116. No. 2. Pages 399–403. August, 1993.

  Details about Improvements on Khrapchenko's theorem | BibTeX data for Improvements on Khrapchenko's theorem

• [25]

  On the optimal bisection of a polygon

  E. Koutsoupias‚ C. H. Papadimitriou and M. Sideri

  In ORSA Journal on Computing. Vol. 4. No. 4. Pages 435–438. 1992.

  Details about On the optimal bisection of a polygon | BibTeX data for On the optimal bisection of a polygon

• [26]

  On the greedy algorithm for satisfiability

  E. Koutsoupias and C. H. Papadimitriou

  In Information Processing Letters. Vol. 43. No. 1. Pages 53–55. August, 1992.

  Details about On the greedy algorithm for satisfiability | BibTeX data for On the greedy algorithm for satisfiability

Conference papers

• [1]

  Approaching utopia: strong truthfulness and externality−resistant mechanisms

  Amos Fiat‚ Anna R. Karlin‚ Elias Koutsoupias and Angelina Vidali

  In ITCS. Pages 221−230. 2013.

  Also in CoRR abs/1208.3939

  Details about Approaching utopia: strong truthfulness and externality−resistant mechanisms | BibTeX data for Approaching utopia: strong truthfulness and externality−resistant mechanisms

• [2]

  Near−optimal multi−unit auctions with ordered bidders

  Sayan Bhattacharya‚ Elias Koutsoupias‚ Janardhan Kulkarni‚ Stefano Leonardi‚ Tim Roughgarden and Xiaoming Xu

  In ACM Conference on Electronic Commerce. Pages 91−102. 2013.

  Also in CoRR abs/1212.2825

  Details about Near−optimal multi−unit auctions with ordered bidders | BibTeX data for Near−optimal multi−unit auctions with ordered bidders

• [3]

  Contention Issues in Congestion Games

  Elias Koutsoupias and Katia Papakonstantinopoulou

  In ICALP (2). Pages 623−635. 2012.

  Details about Contention Issues in Congestion Games | BibTeX data for Contention Issues in Congestion Games

• [4]

  Beyond myopic best response (in Cournot competition)

  Amos Fiat‚ Elias Koutsoupias‚ Katrina Ligett‚ Yishay Mansour and Svetlana Olonetsky

  In SODA. Pages 993−1005. 2012.

  Details about Beyond myopic best response (in Cournot competition) | BibTeX data for Beyond myopic best response (in Cournot competition)

• [5]

  Competitive Analysis of Maintaining Frequent Items of a Stream

  Yiannis Giannakopoulos and Elias Koutsoupias

  In SWAT. Pages 340−351. 2012.

  Details about Competitive Analysis of Maintaining Frequent Items of a Stream | BibTeX data for Competitive Analysis of Maintaining Frequent Items of a Stream

• [6]

  Recent Developments in the Mechanism Design Problem for Scheduling

  Elias Koutsoupias

  In FAW−AAIM. Pages 6–7. 2011.

  Details about Recent Developments in the Mechanism Design Problem for Scheduling | BibTeX data for Recent Developments in the Mechanism Design Problem for Scheduling

• [7]

  Scheduling without payments

  Elias Koutsoupias

  In Symposium on Algorithmic Game Theory (SAGT). Pages 143−153. Salerno − Amalfi Coast‚ Italy. 2011.

  Details about Scheduling without payments | BibTeX data for Scheduling without payments

• [8]

  On the Competitive Ratio of Online Sampling Auctions

  Elias Koutsoupias and George Pierrakos

  In WINE. Pages 327−338. December, 2010.

  Details about On the Competitive Ratio of Online Sampling Auctions | BibTeX data for On the Competitive Ratio of Online Sampling Auctions

• [9]

  On the Performance of Approximate Equilibria in Congestion Games

  G. Christodoulou‚ E. Koutsoupias and P. Spirakis

  In European Symposium‚ Copenhagen. Pages 251–262. Copenhagen‚ Denmark. 2009.

  Also in arXiv:cs/0804.3160

  Details about On the Performance of Approximate Equilibria in Congestion Games | BibTeX data for On the Performance of Approximate Equilibria in Congestion Games

• [10]

  Competitive Analysis of Aggregate Max in Windowed Streaming

  Luca Becchetti and Elias Koutsoupias

  In Proceedings of the 36th International Colloquium on Automata‚ Languages‚ and Programming (ICALP). Pages 156−170. 2009.

  Details about Competitive Analysis of Aggregate Max in Windowed Streaming | BibTeX data for Competitive Analysis of Aggregate Max in Windowed Streaming

• [11]

  A characterization of 2−player mechanisms for scheduling

  G. Christodoulou‚ E. Koutsoupias and A. Vidali

  In ESA 2008‚ 16th Annual European Symposium. September, 2008.

  Details about A characterization of 2−player mechanisms for scheduling | BibTeX data for A characterization of 2−player mechanisms for scheduling

• [12]

  A Lower Bound of 1+phi for Truthful Scheduling Mechanisms

  E. Koutsoupias and A. Vidali

  In Mathematical Foundations of Computer Science (MFCS). Pages 454−464. Krumlov‚ Czech Republic. 2007.

  Details about A Lower Bound of 1+phi for Truthful Scheduling Mechanisms | BibTeX data for A Lower Bound of 1+phi for Truthful Scheduling Mechanisms

• [13]

  Mechanism Design for Fractional Scheduling on Unrelated Machines

  G. Christodoulou‚ E. Koutsoupias and A. Kovacs

  In 34th International Colloquium on Automata‚ Languages and Programming. Pages 40–52. Wroclaw‚ Poland. 2007.

  Details about Mechanism Design for Fractional Scheduling on Unrelated Machines | BibTeX data for Mechanism Design for Fractional Scheduling on Unrelated Machines

• [14]

  A lower bound for scheduling mechanisms.

  G. Christodoulou‚ E. Koutsoupias and A. Vidali

  In SODA. Pages 1163−1170. New Orleans‚ Louisiana‚ USA. 2007.

  Details about A lower bound for scheduling mechanisms. | BibTeX data for A lower bound for scheduling mechanisms.

• [15]

  Selfish Load Balancing Under Partial Knowledge

  E. Koutsoupias‚ P. Panagopoulou and P. Spirakis

  In Mathematical Foundations of Computer Science (MFCS). Pages 609−620. Krumlov‚ Czech Republic. 2007.

  Details about Selfish Load Balancing Under Partial Knowledge | BibTeX data for Selfish Load Balancing Under Partial Knowledge

• [16]

  Experiments with an Economic Model of the Worldwide Web.

  Georgios Kouroupas‚ Elias Koutsoupias‚ Christos H. Papadimitriou and Martha Sideri

  In WINE 2005. Pages 46−54. Hong Kong‚ China. 2005.

  Details about Experiments with an Economic Model of the Worldwide Web. | BibTeX data for Experiments with an Economic Model of the Worldwide Web. | Link to Experiments with an Economic Model of the Worldwide Web.

• [17]

  On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games.

  George Christodoulou and Elias Koutsoupias

  In ESA 2005‚ 13th Annual European Symposium. Pages 59−70. Palma de Mallorca‚ Spain. 2005.

  Details about On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games. | BibTeX data for On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games. | Link to On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games.

• [18]

  The price of anarchy of finite congestion games

  G. Christodoulou and E. Koutsoupias

  In 37th ACM Symposium on Theory of Computing. Pages 67–73. Baltimore‚ MD‚ USA. 2005.

  Details about The price of anarchy of finite congestion games | BibTeX data for The price of anarchy of finite congestion games

• [19]

  Competitive analysis of organization networks or multicast acknowledgement: how much to wait?

  C. Brito‚ E. Koutsoupias and S. Vaya

  In Proceedings of the ACM−SIAM Symposium on Discrete Algorithms (SODA). New Orleans‚ Louisiana‚ USA. 2004.

  Details about Competitive analysis of organization networks or multicast acknowledgement: how much to wait? | BibTeX data for Competitive analysis of organization networks or multicast acknowledgement: how much to wait?

• [20]

  Coordination Mechanisms

  G. Christodoulou‚ E. Koutsoupias and A. Nanavati.

  In Automata‚ Languages and Programming: 31st International Colloquium. Pages 345–357. Turku‚ Finland. 2004.

  Details about Coordination Mechanisms | BibTeX data for Coordination Mechanisms

• [21]

  Congestion Games and Coordination Mechanisms

  E. Koutsoupias

  In Mathematical Foundations of Computer Science 29th International Symposium. Pages 177–179. Prague‚ Czech Republic. 2004.

  Details about Congestion Games and Coordination Mechanisms | BibTeX data for Congestion Games and Coordination Mechanisms

• [22]

  The online matching problem on a line

  E. Koutsoupias and A. Nanavati

  In 1st Workshop on Approximation and Online Algorithms. Pages 179–191. Budapest‚ Hungary. 2003.

  Details about The online matching problem on a line | BibTeX data for The online matching problem on a line

• [23]

  The Structure and Complexity of Nash Equilibria for a Selfish Routing Game.

  D. Fotakis‚ S. Kontogiannis‚ E. Koutsoupias‚ M. Mavronicolas and P. Spirakis

  In Proceedings of the 29th International Colloquium on Automata‚ Languages‚ and Programming (ICALP). Pages 123–134. Malaga‚ Spain. 2002.

  Details about The Structure and Complexity of Nash Equilibria for a Selfish Routing Game. | BibTeX data for The Structure and Complexity of Nash Equilibria for a Selfish Routing Game.

• [24]

  Approximate equilibria and ball fusion

  E. Koutsoupias‚ M. Mavronikolas and P. Spirakis

  In Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO). Pages 223–235. Andros‚ Greece. 2002.

  Details about Approximate equilibria and ball fusion | BibTeX data for Approximate equilibria and ball fusion

• [25]

  Heuristically Optimized Trade−offs: A New Paradigm for Power Laws in the Internet

  A.Fabrikant‚ E. Koutsoupias and C. Papadimitriou

  In Proceedings of the 29th International Colloquium on Automata‚ Languages‚ and Programming (ICALP). Pages 110–122. Malaga‚ Spain. 2002.

  Details about Heuristically Optimized Trade−offs: A New Paradigm for Power Laws in the Internet | BibTeX data for Heuristically Optimized Trade−offs: A New Paradigm for Power Laws in the Internet

• [26]

  On the Competitive Ratio of the Work Function Algorithm for the k−Server Problem

  Y. Bartal and E. Koutsoupias

  In 17th Annual Symposium on Theoretical Aspects of Computer Science. Pages 605–613. Lille‚ France. 2000.

  Details about On the Competitive Ratio of the Work Function Algorithm for the k−Server Problem | BibTeX data for On the Competitive Ratio of the Work Function Algorithm for the k−Server Problem

• [27]

  The CNN Problem and Other k−Server Variants

  E. Koutsoupias and D. S. Taylor

  In 17th Annual Symposium on Theoretical Aspects of Computer Science. Pages 581–592. Lille‚ France. 2000.

  To appear in Theoretical Computer Science

  Details about The CNN Problem and Other k−Server Variants | BibTeX data for The CNN Problem and Other k−Server Variants

• [28]

  Combinatorial optimization in congestion control

  R. Karp‚ E. Koutsoupias‚ C. Papadimitriou and S. Shenker

  In Proceedings of the 41th Annual Symposium on Foundations of Computer Science. Pages 66–74. Redondo Beach‚ CA. 2000.

  Details about Combinatorial optimization in congestion control | BibTeX data for Combinatorial optimization in congestion control

• [29]

  Worst−case equilibria

  E. Koutsoupias and C. Papadimitriou

  In 16th Annual Symposium on Theoretical Aspects of Computer Science. Pages 404–413. Trier‚ Germany. 1999.

  Details about Worst−case equilibria | BibTeX data for Worst−case equilibria

• [30]

  Weak adversaries for the k−server problem

  E. Koutsoupias

  In Proceedings of the 40th Annual Symposium on Foundations of Computer Science. Pages 444–449. New York City‚ NY. 1999.

  Details about Weak adversaries for the k−server problem | BibTeX data for Weak adversaries for the k−server problem

• [31]

  Indexing schemes for random points

  E. Koutsoupias and D. S. Taylor

  In Proceedings of the 10th Annual ACM−SIAM Symposium on Discrete Algorithms. Pages 596–602. Baltimore‚ Maryland. 1999.

  Details about Indexing schemes for random points | BibTeX data for Indexing schemes for random points

• [32]

  Tight bounds for 2−dimensional indexing schemes

  E. Koutsoupias and D. S. Taylor

  In Proceedings of the Seventeenth ACM SIGACT−SIGMOD−SIGART Symposium on Principles of Database Systems. Seattle‚ Washington. 1998.

  Details about Tight bounds for 2−dimensional indexing schemes | BibTeX data for Tight bounds for 2−dimensional indexing schemes

• [33]

  On the analysis of indexing schemes

  J. M. Hellerstein‚ E. Koutsoupias and C. H. Papadimitriou

  In Proceedings of the Sixteenth ACM SIGACT−SIGMOD−SIGART Symposium on Principles of Database Systems. Pages 249–256. Tucson‚ Arizona. 1997.

  Details about On the analysis of indexing schemes | BibTeX data for On the analysis of indexing schemes

• [34]

  Searching a fixed graph

  E. Koutsoupias‚ C. Papadimitriou and M. Yannakakis

  In International Colloquium on Automata‚ Languages‚ and Programming. Pages 280–289. Paderborn‚ Germany. 1996.

  Details about Searching a fixed graph | BibTeX data for Searching a fixed graph

• [35]

  Three−processor tasks are undecidable

  E. Gafni and E. Koutsoupias

  In Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing. Pages 271. Ottawa‚ Ontario‚ Canada. 1995.

  Final version in Siam J. on Comp.

  Details about Three−processor tasks are undecidable | BibTeX data for Three−processor tasks are undecidable

• [36]

  An approximation scheme for planar graph TSP

  M. Grigni‚ E. Koutsoupias and C. Papadimitriou

  In Proceedings of the 36th Annual Symposium on Foundations of Computer Science. Pages 640–645. Milwaukee‚ Wisconsin. 1995.

  Details about An approximation scheme for planar graph TSP | BibTeX data for An approximation scheme for planar graph TSP

• [37]

  Beyond competitive analysis

  E. Koutsoupias and C. H. Papadimitriou

  In Proceeding 35th Annual Symposium on Foundations of Computer Science. Pages 394–400. Santa Fe‚ New Mexico. 1994.

  Final version in Siam J. on Comp.

  Details about Beyond competitive analysis | BibTeX data for Beyond competitive analysis

• [38]

  On the k−server conjecture

  E. Koutsoupias and C. Papadimitriou

  In Proceedings of the Twenty−Sixth Annual ACM Symposium on the Theory of Computing. Pages 507–511. Montreal‚ Quebec‚ Canada. 1994.

  Details about On the k−server conjecture | BibTeX data for On the k−server conjecture

• [39]

  Competitive implementation of parallel programs

  X. Deng and E. Koutsoupias

  In Proceedings of the 4th ACM−SIAM Symposium on Discrete Algorithms. Pages 455–461. Austin‚ Texas. 1993.

  Updated version DKM99

  Details about Competitive implementation of parallel programs | BibTeX data for Competitive implementation of parallel programs

• [40]

  On the optimal bisection of a polygon

  E. Koutsoupias‚ C. H. Papadimitriou and M. Sideri

  In Proceedings of the Sixth Annual Symposium on Computational Geometry. Pages 198–202. Berkeley‚ California. 1990.

  Details about On the optimal bisection of a polygon | BibTeX data for On the optimal bisection of a polygon

Theses

• [1]

  On−line algorithms and the k−server conjecture

  E. Koutsoupias

  PhD Thesis University of California‚ San Diego. La Jolla‚ California. June, 1994.

  Details about On−line algorithms and the k−server conjecture | BibTeX data for On−line algorithms and the k−server conjecture