Elias Koutsoupias : Publications
Click here to download all publications in a single bibtex file
@article{KV13,
title = "A Lower Bound of 1+$\phi$ for Truthful Scheduling Mechanisms",
author = "Elias Koutsoupias and Angelina Vidali",
year = "2013",
journal = "Algorithmica",
number = "1",
pages = "211-223",
volume = "66",
}
@article{KP13,
title = "On the Competitive Ratio of Online Sampling Auctions",
author = "Elias Koutsoupias and George Pierrakos",
year = "2013",
journal = "ACM Trans. Economics and Comput.",
number = "2",
pages = "10",
volume = "1",
}
@inproceedings{FKKV13,
title = "Approaching utopia: strong truthfulness and externality-resistant mechanisms",
author = "Amos Fiat and Anna R. Karlin and Elias Koutsoupias and Angelina Vidali",
year = "2013",
booktitle = "ITCS",
note = "Also in CoRR abs/1208.3939",
pages = "221-230",
}
@inproceedings{BKKLRX13,
title = "Near-optimal multi-unit auctions with ordered bidders",
author = "Sayan Bhattacharya and Elias Koutsoupias and Janardhan Kulkarni and Stefano Leonardi and Tim Roughgarden and Xiaoming Xu",
year = "2013",
booktitle = "ACM Conference on Electronic Commerce",
note = "Also in CoRR abs/1212.2825",
pages = "91-102",
}
@article{BKV12,
title = "Competitive Analysis of Organization Networks or Multicast Acknowledgment: How Much to Wait?",
author = "Carlos Fisch Brito and Elias Koutsoupias and Shailesh Vaya",
year = "2012",
journal = "Algorithmica",
number = "4",
pages = "584-605",
volume = "64",
}
@inproceedings{KP12,
title = "Contention Issues in Congestion Games",
author = "Elias Koutsoupias and Katia Papakonstantinopoulou",
year = "2012",
booktitle = "ICALP (2)",
pages = "623-635",
}
@inproceedings{FKLMO12,
title = "Beyond myopic best response (in Cournot competition)",
author = "Amos Fiat and Elias Koutsoupias and Katrina Ligett and Yishay Mansour and Svetlana Olonetsky",
year = "2012",
booktitle = "SODA",
pages = "993-1005",
}
@inproceedings{GK12,
title = "Competitive Analysis of Maintaining Frequent Items of a Stream",
author = "Yiannis Giannakopoulos and Elias Koutsoupias",
year = "2012",
booktitle = "SWAT",
pages = "340-351",
}
@article{CKS11,
title = "On the Performance of Approximate Equilibria in Congestion Games",
author = "George Christodoulou and Elias Koutsoupias and Paul G. Spirakis",
year = "2011",
journal = "Algorithmica",
number = "1",
pages = "116-140",
volume = "61",
}
@inproceedings{Kou11b,
title = "Recent Developments in the Mechanism Design Problem for Scheduling",
author = "Elias Koutsoupias",
year = "2011",
booktitle = "FAW-AAIM",
pages = "6--7",
}
@inproceedings{Kou11,
title = "Scheduling without payments",
author = "Elias Koutsoupias",
year = "2011",
address = "Salerno - Amalfi Coast, Italy",
booktitle = "Symposium on Algorithmic Game Theory (SAGT)",
month = "17--19 oct",
pages = "143-153",
}
@inproceedings{KP10,
title = "On the Competitive Ratio of Online Sampling Auctions",
author = "Elias Koutsoupias and George Pierrakos",
year = "2010",
booktitle = "WINE",
month = "dec",
pages = "327-338",
}
@article{CKK10,
title = "Mechanism Design for Fractional Scheduling on Unrelated Machines",
author = "G. Christodoulou and E. Koutsoupias and A. Kov{\'a}cs",
year = "2010",
journal = "ACM Transactions on Algorithms",
number = "2",
volume = "6",
}
@article{CK09,
title = "Mechanism design for scheduling",
author = "George Christodoulou and Elias Koutsoupias",
year = "2009",
journal = "Bulletin of the European Association for Theoretical Computer Science (BEATCS)",
month = "feb",
pages = "39-59",
volume = "97",
}
@article{CKV09,
title = "A Lower Bound for Scheduling Mechanisms",
author = "George Christodoulou and Elias Koutsoupias and Angelina Vidali",
year = "2009",
journal = "Algorithmica",
number = "4",
pages = "729-740",
volume = "55",
}
@article{Kou09,
title = "The k-server problem",
author = "Elias Koutsoupias",
year = "2009",
journal = "Computer Science Review",
number = "2",
pages = "105-118",
volume = "3",
}
@article{KP09,
title = "Worst-case equilibria",
author = "Elias Koutsoupias and Christos H. Papadimitriou",
year = "2009",
journal = "Computer Science Review",
number = "2",
pages = "65-69",
volume = "3",
}
@article{CKN09,
title = "Coordination mechanisms",
author = "George Christodoulou and Elias Koutsoupias and Akash Nanavati",
year = "2009",
journal = "Theor. Comput. Sci.",
number = "36",
pages = "3327--3336",
volume = "410",
}
@article{FKKMS09,
title = "The structure and complexity of Nash equilibria for a selfish routing game",
author = "Dimitris Fotakis and Spyros C. Kontogiannis and Elias Koutsoupias and Marios Mavronicolas and Paul G. Spirakis",
year = "2009",
journal = "Theor. Comput. Sci.",
number = "36",
pages = "3305-3326",
volume = "410",
}
@inproceedings{CKS09,
title = "On the Performance of Approximate Equilibria in Congestion Games",
author = "G. Christodoulou and E. Koutsoupias and P. Spirakis",
year = "2009",
address = "Copenhagen, Denmark",
booktitle = "European Symposium, Copenhagen",
month = "7--9 sep",
note = "Also in arXiv:cs/0804.3160",
pages = "251--262",
}
@inproceedings{BK09,
title = "Competitive Analysis of Aggregate Max in Windowed Streaming",
author = "Luca Becchetti and Elias Koutsoupias",
year = "2009",
booktitle = "Proceedings of the 36th International Colloquium on Automata, Languages, and Programming (ICALP)",
pages = "156-170",
}
@inproceedings{CKV08,
title = "A characterization of 2-player mechanisms for scheduling",
author = "G. Christodoulou and E. Koutsoupias and A. Vidali",
year = "2008",
booktitle = "ESA 2008, 16th Annual European Symposium",
month = "sep",
}
@inproceedings{KV07,
title = "A Lower Bound of 1+phi for Truthful Scheduling Mechanisms",
author = "E. Koutsoupias and A. Vidali",
year = "2007",
address = "Krumlov, Czech Republic",
booktitle = "Mathematical Foundations of Computer Science (MFCS)",
month = "26-31 aug",
pages = "454-464",
}
@inproceedings{CKK07,
title = "Mechanism Design for Fractional Scheduling on Unrelated Machines",
author = "G. Christodoulou and E. Koutsoupias and A. Kovacs",
year = "2007",
address = "Wroclaw, Poland",
booktitle = "34th International Colloquium on Automata, Languages and Programming",
month = "9-13 jul",
pages = "40--52",
}
@inproceedings{CKV07,
title = "A lower bound for scheduling mechanisms.",
author = "G. Christodoulou and E. Koutsoupias and A. Vidali",
year = "2007",
address = "New Orleans, Louisiana, USA",
booktitle = "SODA",
month = "7--9 jan",
pages = "1163-1170",
}
@inproceedings{KPS07,
title = "Selfish Load Balancing Under Partial Knowledge",
author = "E. Koutsoupias and P. Panagopoulou and P. Spirakis",
year = "2007",
address = "Krumlov, Czech Republic",
booktitle = "Mathematical Foundations of Computer Science (MFCS)",
month = "26-31 aug",
pages = "609-620",
}
@inproceedings{KKPS05,
title = "Experiments with an Economic Model of the Worldwide Web.",
author = "Georgios Kouroupas and Elias Koutsoupias and Christos H. Papadimitriou and Martha Sideri",
year = "2005",
address = "Hong Kong, China",
booktitle = "WINE 2005",
month = "15-17 dec",
pages = "46-54",
url = "http://dx.doi.org/10.1007/11600930_6",
}
@inproceedings{GK05b,
title = "On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games.",
author = "George Christodoulou and Elias Koutsoupias",
year = "2005",
address = "Palma de Mallorca, Spain",
booktitle = "ESA 2005, 13th Annual European Symposium",
month = "3-6 oct",
pages = "59-70",
url = "http://dx.doi.org/10.1007/11561071_8",
}
@inproceedings{CK05,
title = "The price of anarchy of finite congestion games",
author = "G. Christodoulou and E. Koutsoupias",
year = "2005",
address = "Baltimore, MD, USA",
booktitle = "37th ACM Symposium on Theory of Computing",
month = "22--24 may",
pages = "67--73",
}
@article{Kou04,
title = "Coordination mechanisms for congestion games.",
author = "E. Koutsoupias",
year = "2004",
journal = "Sigact News",
month = "dec",
number = "4",
pages = "58--71",
volume = "35",
}
@article{BK04,
title = "On the Competitive Ratio of the Work Function Algorithm for the $k$-Server Problem",
author = "Y. Bartal and E. Koutsoupias",
year = "2004",
journal = "Theoretical Computer Science",
month = "20 sep",
note = "An early version appeared in STACS 2000",
number = "2-3",
pages = "337--345",
volume = "324",
}
@article{KT04,
title = "The CNN problem and other k-server variants",
author = "E. Koutsoupias and D. S. Taylor",
year = "2004",
journal = "Theoretical Computer Science",
month = "20 sep",
note = "An early version appeared in STACS 2000",
number = "2-3",
pages = "347--359",
volume = "324",
}
@inproceedings{BKV04,
title = "Competitive analysis of organization networks or multicast acknowledgement: how much to wait?",
author = "C. Brito and E. Koutsoupias and S. Vaya",
year = "2004",
address = "New Orleans, Louisiana, USA",
booktitle = "Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)",
month = "11--14 jan",
}
@inproceedings{CKN04,
title = "Coordination Mechanisms",
author = "G. Christodoulou and E. Koutsoupias and A. Nanavati.",
year = "2004",
address = "Turku, Finland",
booktitle = "Automata, Languages and Programming: 31st International Colloquium",
month = "12--16 jul",
pages = "345--357",
}
@inproceedings{Kou04b,
title = "Congestion Games and Coordination Mechanisms",
author = "E. Koutsoupias",
year = "2004",
address = "Prague, Czech Republic",
booktitle = "Mathematical Foundations of Computer Science 29th International Symposium",
month = "22--27 aug",
pages = "177--179",
}
@article{Kou03,
title = "Selfish task allocation",
author = "E. Koutsoupias",
year = "2003",
journal = "Bulletin of EATCS",
month = "oct",
pages = "79--88",
volume = "81",
}
@article{CKN03,
title = "More on Randomized On-line Algorithms for Caching",
author = "M. Chrobak and E. Koutsoupias and J. Noga",
year = "2003",
journal = "Theoretical Computer Science",
number = "3",
pages = "1997--2008",
volume = "290",
}
@article{KMS03,
title = "Approximate equilibria and ball fusion",
author = "E. Koutsoupias and M. Mavronikolas and P. Spirakis",
year = "2003",
journal = "Theory of Computing Systems",
number = "6",
pages = "683--693",
volume = "36",
}
@inproceedings{KN03b,
title = "The online matching problem on a line",
author = "E. Koutsoupias and A. Nanavati",
year = "2003",
address = "Budapest, Hungary",
booktitle = "1st Workshop on Approximation and Online Algorithms",
pages = "179--191",
}
@article{HKMPS02,
title = "On a model of indexability and its bounds for range queries",
author = "Joseph M. Hellerstein and Elias Koutsoupias and Daniel P. Miranker and Christos H. Papadimitriou and Vasilis Samoladas",
year = "2002",
issn = "0004-5411",
journal = "Journal of the ACM (JACM)",
number = "1",
pages = "35--55",
publisher = "ACM Press",
volume = "49",
doi = "http://doi.acm.org/10.1145/505241.505244",
}
@inproceedings{FKKMS02,
title = "The Structure and Complexity of Nash Equilibria for a Selfish Routing Game.",
author = "D. Fotakis and S. Kontogiannis and E. Koutsoupias and M. Mavronicolas and P. Spirakis",
year = "2002",
address = "Malaga, Spain",
booktitle = "Proceedings of the 29th International Colloquium on Automata, Languages, and Programming (ICALP)",
pages = "123--134",
}
@inproceedings{KMS02,
title = "Approximate equilibria and ball fusion",
author = "E. Koutsoupias and M. Mavronikolas and P. Spirakis",
year = "2002",
address = "Andros, Greece",
booktitle = "Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO)",
month = "10-12 jun",
pages = "223--235",
}
@inproceedings{FKP02,
title = "Heuristically Optimized Trade-offs: A New Paradigm for Power Laws in the Internet",
author = "A.Fabrikant and E. Koutsoupias and C. Papadimitriou",
year = "2002",
address = "Malaga, Spain",
booktitle = "Proceedings of the 29th International Colloquium on Automata, Languages, and Programming (ICALP)",
pages = "110--122",
}
@article{KP00,
title = "Beyond competitive analysis",
author = "E. Koutsoupias and C. H. Papadimitriou",
year = "2000",
journal = "SIAM Journal on Computing",
number = "1",
pages = "394--400",
volume = "30",
}
@inproceedings{BK00,
title = "On the Competitive Ratio of the Work Function Algorithm for the $k$-Server Problem",
author = "Y. Bartal and E. Koutsoupias",
year = "2000",
address = "Lille, France",
booktitle = "17th Annual Symposium on Theoretical Aspects of Computer Science",
month = "17--19 feb",
pages = "605--613",
}
@inproceedings{KT00,
title = "The {CNN} Problem and Other $k$-Server Variants",
author = "E. Koutsoupias and D. S. Taylor",
year = "2000",
address = "Lille, France",
booktitle = "17th Annual Symposium on Theoretical Aspects of Computer Science",
month = "17--19 feb",
note = "To appear in Theoretical Computer Science",
pages = "581--592",
}
@inproceedings{KKPS00,
title = "Combinatorial optimization in congestion control",
author = "R. Karp and E. Koutsoupias and C. Papadimitriou and S. Shenker",
year = "2000",
address = "Redondo Beach, CA",
booktitle = "Proceedings of the 41th Annual Symposium on Foundations of Computer Science",
month = "12--14 nov",
pages = "66--74",
}
@article{DKM99,
title = "Competitive implementation of parallel programs",
author = "X. Deng and E. Koutsoupias and P. MacKenzie",
year = "1999",
journal = "Algorithmica",
number = "1",
pages = "14--30",
volume = "23",
}
@article{GK99,
title = "Three-Processor Tasks Are Undecidable",
author = "E. Gafni and E. Koutsoupias",
year = "1999",
journal = "SIAM Journal on Computing",
number = "3",
pages = "970--983",
volume = "28",
}
@inproceedings{KP99,
title = "Worst-case equilibria",
author = "E. Koutsoupias and C. Papadimitriou",
year = "1999",
address = "Trier, Germany",
booktitle = "16th Annual Symposium on Theoretical Aspects of Computer Science",
month = "4--6 mar",
pages = "404--413",
}
@inproceedings{Kou99,
title = "Weak adversaries for the $k$-server problem",
author = "E. Koutsoupias",
year = "1999",
address = "New York City, NY",
booktitle = "Proceedings of the 40th Annual Symposium on Foundations of Computer Science",
month = "17--19 oct",
pages = "444--449",
}
@inproceedings{KT99,
title = "Indexing schemes for random points",
author = "E. Koutsoupias and D. S. Taylor",
year = "1999",
address = "Baltimore, Maryland",
booktitle = "Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms",
month = "17--19 jan",
pages = "596--602",
}
@inproceedings{KT98,
title = "Tight bounds for 2-dimensional indexing schemes",
author = "E. Koutsoupias and D. S. Taylor",
year = "1998",
address = "Seattle, Washington",
booktitle = "Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems",
month = "1--4 jun",
}
@inproceedings{HKP97,
title = "On the analysis of indexing schemes",
author = "J. M. Hellerstein and E. Koutsoupias and C. H. Papadimitriou",
year = "1997",
address = "Tucson, Arizona",
booktitle = "Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems",
month = "12--15 may",
pages = "249--256",
}
@article{KP96,
title = "The 2-evader problem",
author = "E. Koutsoupias and C. Papadimitriou",
year = "1996",
journal = "Information Processing Letters",
month = "mar",
number = "5",
pages = "249--252",
volume = "57",
}
@inproceedings{KPY96,
title = "Searching a fixed graph",
author = "E. Koutsoupias and C. Papadimitriou and M. Yannakakis",
year = "1996",
address = "Paderborn, Germany",
booktitle = "International Colloquium on Automata, Languages, and Programming",
month = "8--12 jul",
pages = "280--289",
}
@article{KP95,
title = "On the {$k$}-Server Conjecture",
author = "E. Koutsoupias and C. Papadimitriou",
year = "1995",
journal = "Journal of the ACM",
month = "sep",
number = "5",
pages = "971--983",
volume = "42",
}
@inproceedings{GK95,
title = "Three-processor tasks are undecidable",
author = "E. Gafni and E. Koutsoupias",
year = "1995",
address = "Ottawa, Ontario, Canada",
booktitle = "Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing",
month = "20--23 aug",
note = "Final version in Siam J. on Comp.",
pages = "271",
}
@inproceedings{GKP95,
title = "An approximation scheme for planar graph {TSP}",
author = "M. Grigni and E. Koutsoupias and C. Papadimitriou",
year = "1995",
address = "Milwaukee, Wisconsin",
booktitle = "Proceedings of the 36th Annual Symposium on Foundations of Computer Science",
month = "23--25 oct",
pages = "640--645",
}
@phdthesis{Kou94,
title = "On-line algorithms and the $k$-server conjecture",
author = "E. Koutsoupias",
year = "1994",
address = "La Jolla, California",
month = "jun",
school = "University of California, San Diego",
}
@inproceedings{KP94b,
title = "Beyond competitive analysis",
author = "E. Koutsoupias and C. H. Papadimitriou",
year = "1994",
address = "Santa Fe, New Mexico",
booktitle = "Proceeding 35th Annual Symposium on Foundations of Computer Science",
month = "20--22 nov",
note = "Final version in Siam J. on Comp.",
pages = "394--400",
}
@inproceedings{KP94a,
title = "On the {$k$}-server conjecture",
author = "E. Koutsoupias and C. Papadimitriou",
year = "1994",
address = "Montreal, Quebec, Canada",
booktitle = "Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing",
month = "23--25 may",
pages = "507--511",
}
@article{Kou93,
title = "Improvements on {K}hrapchenko's theorem",
author = "E. Koutsoupias",
year = "1993",
journal = "Theoretical Computer Science",
month = "aug",
number = "2",
pages = "399--403",
volume = "116",
}
@inproceedings{DK93,
title = "Competitive implementation of parallel programs",
author = "X. Deng and E. Koutsoupias",
year = "1993",
address = "Austin, Texas",
booktitle = "Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms",
month = "25--27 jan",
note = "Updated version \cite{DKM99}",
pages = "455--461",
}
@article{KP92,
title = "On the greedy algorithm for satisfiability",
author = "E. Koutsoupias and C. H. Papadimitriou",
year = "1992",
journal = "Information Processing Letters",
month = "aug",
number = "1",
pages = "53--55",
volume = "43",
}
@article{KPS92,
title = "On the optimal bisection of a polygon",
author = "E. Koutsoupias and C. H. Papadimitriou and M. Sideri",
year = "1992",
journal = "ORSA Journal on Computing",
month = "Fall",
number = "4",
pages = "435--438",
volume = "4",
}
@inproceedings{KPS90,
title = "On the optimal bisection of a polygon",
author = "E. Koutsoupias and C. H. Papadimitriou and M. Sideri",
year = "1990",
address = "Berkeley, California",
booktitle = "Proceedings of the Sixth Annual Symposium on Computational Geometry",
month = "6--8 jun",
pages = "198--202",
}