Elias Koutsoupias : Publications

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

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

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

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

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?

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

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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

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.

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.

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

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.

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

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

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?

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

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

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

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

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

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

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)

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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