Dr. Annamaria Kovacs

Photo
Institut für Informatik
Room 305
Robert-Mayer-Straße 11-15
60325 Frankfurt am Main
Germany
 
panni@ae.cs.uni-frankfurt.de
+49-69-798-28814

Research interests

  • Combinatorial Optimization
  • Scheduling Problems
  • Algorithmic Mechanism Design
  • Graph Problems

Publications

1
George Christodoulou, Annamária Kovács, and Michael Schapira. Bayesian combinatorial auctions. J. ACM, 63(2):11:1–11:19, 2016. View Online doi:10.1145/2835172 @article{DBLP:journals/jacm/0001KS16, author = "Christodoulou, George and Kov{\'{a}}cs, Annam{\'{a}}ria and Schapira, Michael", biburl = "https://dblp.org/rec/journals/jacm/0001KS16.bib", doi = "10.1145/2835172", journal = "J. {ACM}", number = "2", pages = "11:1--11:19", title = "Bayesian Combinatorial Auctions", url = "https://doi.org/10.1145/2835172", volume = "63", year = "2016" }
2
George Christodoulou, Annamária Kovács, Alkmini Sgouritsa, and Bo Tang. Tight bounds for the price of anarchy of simultaneous first-price auctions. ACM Trans. Economics and Comput., 4(2):9:1–9:33, 2016. View Online doi:10.1145/2847520 @article{DBLP:journals/teco/0001KST16, author = "Christodoulou, George and Kov{\'{a}}cs, Annam{\'{a}}ria and Sgouritsa, Alkmini and Tang, Bo", biburl = "https://dblp.org/rec/journals/teco/0001KST16.bib", doi = "10.1145/2847520", journal = "{ACM} Trans. Economics and Comput.", number = "2", pages = "9:1--9:33", title = "Tight Bounds for the Price of Anarchy of Simultaneous First-Price Auctions", url = "https://doi.org/10.1145/2847520", volume = "4", year = "2016" }
3
Annamária Kovács and Angelina Vidali. A characterization of n-player strongly monotone scheduling mechanisms. In Qiang Yang and Michael J. Wooldridge, editors, Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, 568–574. AAAI Press, 2015. View Online @inproceedings{DBLP:conf/ijcai/KovacsV15, author = "Kov{\'{a}}cs, Annam{\'{a}}ria and Vidali, Angelina", editor = "Yang, Qiang and Wooldridge, Michael J.", biburl = "https://dblp.org/rec/conf/ijcai/KovacsV15.bib", booktitle = "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, {IJCAI} 2015, Buenos Aires, Argentina, July 25-31, 2015", pages = "568--574", publisher = "{AAAI} Press", title = "A Characterization of n-Player Strongly Monotone Scheduling Mechanisms", url = "http://ijcai.org/Abstract/15/086", year = "2015" }
4
Annamária Kovács, Ulrich Meyer, and Carmine Ventre. Mechanisms with monitoring for truthful RAM allocation. In Evangelos Markakis and Guido Schäfer, editors, Web and Internet Economics - 11th International Conference, WINE 2015, Amsterdam, The Netherlands, December 9-12, 2015, Proceedings, volume 9470 of Lecture Notes in Computer Science, 398–412. Springer, 2015. View Online doi:10.1007/978-3-662-48995-6_29 @inproceedings{DBLP:conf/wine/KovacsMV15, author = "Kov{\'{a}}cs, Annam{\'{a}}ria and Meyer, Ulrich and Ventre, Carmine", editor = {Markakis, Evangelos and Sch{\"{a}}fer, Guido}, biburl = "https://dblp.org/rec/conf/wine/KovacsMV15.bib", booktitle = "Web and Internet Economics - 11th International Conference, {WINE} 2015, Amsterdam, The Netherlands, December 9-12, 2015, Proceedings", doi = "10.1007/978-3-662-48995-6\_29", pages = "398--412", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "Mechanisms with Monitoring for Truthful {RAM} Allocation", url = "https://doi.org/10.1007/978-3-662-48995-6\_29", volume = "9470", year = "2015" }
5
Annamária Kovács, Ulrich Meyer, Gabriel Moruz, and Andrei Negoescu. The optimal structure of algorithms for α-paging. Inf. Process. Lett., 115(12):932–938, 2015. View Online doi:10.1016/j.ipl.2015.07.011 @article{DBLP:journals/ipl/KovacsMMN15, author = "Kov{\'{a}}cs, Annam{\'{a}}ria and Meyer, Ulrich and Moruz, Gabriel and Negoescu, Andrei", biburl = "https://dblp.org/rec/journals/ipl/KovacsMMN15.bib", doi = "10.1016/j.ipl.2015.07.011", journal = "Inf. Process. Lett.", number = "12", pages = "932--938", title = "The optimal structure of algorithms for {\(\alpha\)}-paging", url = "https://doi.org/10.1016/j.ipl.2015.07.011", volume = "115", year = "2015" }
6
George Christodoulou and Annamária Kovács. A deterministic truthful PTAS for scheduling related machines. SIAM J. Comput., 42(4):1572–1595, 2013. View Online doi:10.1137/120866038 @article{DBLP:journals/siamcomp/0001K13, author = "Christodoulou, George and Kov{\'{a}}cs, Annam{\'{a}}ria", biburl = "https://dblp.org/rec/journals/siamcomp/0001K13.bib", doi = "10.1137/120866038", journal = "{SIAM} J. Comput.", number = "4", pages = "1572--1595", title = "A Deterministic Truthful {PTAS} for Scheduling Related Machines", url = "https://doi.org/10.1137/120866038", volume = "42", year = "2013" }
7
George Christodoulou, Annamária Kovács, and Rob van Stee. A truthful constant approximation for maximizing the minimum load on related machines. Theor. Comput. Sci., 489-490:88–98, 2013. View Online doi:10.1016/j.tcs.2013.04.003 @article{DBLP:journals/tcs/0001KS13, author = "Christodoulou, George and Kov{\'{a}}cs, Annam{\'{a}}ria and van Stee, Rob", biburl = "https://dblp.org/rec/journals/tcs/0001KS13.bib", doi = "10.1016/j.tcs.2013.04.003", journal = "Theor. Comput. Sci.", pages = "88--98", title = "A truthful constant approximation for maximizing the minimum load on related machines", url = "https://doi.org/10.1016/j.tcs.2013.04.003", volume = "489-490", year = "2013" }
8
Gabriel Moruz and Andrei Negoescu. Improved space bounds for strongly competitive randomized paging algorithms. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, volume 7965 of Lecture Notes in Computer Science, 757–768. Springer, 2013. View Online doi:10.1007/978-3-642-39206-1_64 @inproceedings{DBLP:conf/icalp/MoruzN13, author = "Moruz, Gabriel and Negoescu, Andrei", editor = "Fomin, Fedor V. and Freivalds, Rusins and Kwiatkowska, Marta Z. and Peleg, David", biburl = "https://dblp.org/rec/conf/icalp/MoruzN13.bib", booktitle = "Automata, Languages, and Programming - 40th International Colloquium, {ICALP} 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part {I}", doi = "10.1007/978-3-642-39206-1\_64", pages = "757--768", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "Improved Space Bounds for Strongly Competitive Randomized Paging Algorithms", url = "https://doi.org/10.1007/978-3-642-39206-1\_64", volume = "7965", year = "2013" }
9
George Christodoulou and Annamária Kovács. A global characterization of envy-free truthful scheduling of two tasks. In Ning Chen, Edith Elkind, and Elias Koutsoupias, editors, Internet and Network Economics - 7th International Workshop, WINE 2011, Singapore, December 11-14, 2011. Proceedings, volume 7090 of Lecture Notes in Computer Science, 84–96. Springer, 2011. View Online doi:10.1007/978-3-642-25510-6_8 @inproceedings{DBLP:conf/wine/ChristodoulouK11, author = "Christodoulou, George and Kov{\'{a}}cs, Annam{\'{a}}ria", editor = "Chen, Ning and Elkind, Edith and Koutsoupias, Elias", biburl = "https://dblp.org/rec/conf/wine/ChristodoulouK11.bib", booktitle = "Internet and Network Economics - 7th International Workshop, {WINE} 2011, Singapore, December 11-14, 2011. Proceedings", doi = "10.1007/978-3-642-25510-6\_8", pages = "84--96", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "A Global Characterization of Envy-Free Truthful Scheduling of Two Tasks", url = "https://doi.org/10.1007/978-3-642-25510-6\_8", volume = "7090", year = "2011" }
10
George Christodoulou and Annamária Kovács. A deterministic truthful PTAS for scheduling related machines. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, 1005–1016. SIAM, 2010. View Online doi:10.1137/1.9781611973075.81 @inproceedings{DBLP:conf/soda/ChristodoulouK10, author = "Christodoulou, George and Kov{\'{a}}cs, Annam{\'{a}}ria", editor = "Charikar, Moses", biburl = "https://dblp.org/rec/conf/soda/ChristodoulouK10.bib", booktitle = "Proceedings of the Twenty-First Annual {ACM-SIAM} Symposium on Discrete Algorithms, {SODA} 2010, Austin, Texas, USA, January 17-19, 2010", doi = "10.1137/1.9781611973075.81", pages = "1005--1016", publisher = "{SIAM}", title = "A Deterministic Truthful {PTAS} for Scheduling Related Machines", url = "https://doi.org/10.1137/1.9781611973075.81", year = "2010" }
11
George Christodoulou, Annamária Kovács, and Rob van Stee. A truthful constant approximation for maximizing the minimum load on related machines. In Amin Saberi, editor, Internet and Network Economics - 6th International Workshop, WINE 2010, Stanford, CA, USA, December 13-17, 2010. Proceedings, volume 6484 of Lecture Notes in Computer Science, 182–193. Springer, 2010. View Online doi:10.1007/978-3-642-17572-5_15 @inproceedings{DBLP:conf/wine/ChristodoulouKS10, author = "Christodoulou, George and Kov{\'{a}}cs, Annam{\'{a}}ria and van Stee, Rob", editor = "Saberi, Amin", biburl = "https://dblp.org/rec/conf/wine/ChristodoulouKS10.bib", booktitle = "Internet and Network Economics - 6th International Workshop, {WINE} 2010, Stanford, CA, USA, December 13-17, 2010. Proceedings", doi = "10.1007/978-3-642-17572-5\_15", pages = "182--193", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "A Truthful Constant Approximation for Maximizing the Minimum Load on Related Machines", url = "https://doi.org/10.1007/978-3-642-17572-5\_15", volume = "6484", year = "2010" }
12
George Christodoulou, Elias Koutsoupias, and Annamária Kovács. Mechanism design for fractional scheduling on unrelated machines. ACM Trans. Algorithms, 6(2):38:1–38:18, 2010. View Online doi:10.1145/1721837.1721854 @article{DBLP:journals/talg/ChristodoulouKK10, author = "Christodoulou, George and Koutsoupias, Elias and Kov{\'{a}}cs, Annam{\'{a}}ria", biburl = "https://dblp.org/rec/journals/talg/ChristodoulouKK10.bib", doi = "10.1145/1721837.1721854", journal = "{ACM} Trans. Algorithms", number = "2", pages = "38:1--38:18", title = "Mechanism design for fractional scheduling on unrelated machines", url = "https://doi.org/10.1145/1721837.1721854", volume = "6", year = "2010" }
13
Annamária Kovács. New approximation bounds for lpt scheduling. Algorithmica, 57(2):413–433, 2010. View Online doi:10.1007/s00453-008-9224-9 @article{DBLP:journals/algorithmica/Kovacs10, author = "Kov{\'{a}}cs, Annam{\'{a}}ria", biburl = "https://dblp.org/rec/journals/algorithmica/Kovacs10.bib", doi = "10.1007/s00453-008-9224-9", journal = "Algorithmica", number = "2", pages = "413--433", title = "New Approximation Bounds for Lpt Scheduling", url = "https://doi.org/10.1007/s00453-008-9224-9", volume = "57", year = "2010" }
14
Annamária Kovács, Ulrich Meyer, Gabriel Moruz, and Andrei Negoescu. Online paging for flash memory devices. In Yingfei Dong, Ding-Zhu Du, and Oscar H. Ibarra, editors, Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings, volume 5878 of Lecture Notes in Computer Science, 352–361. Springer, 2009. View Online doi:10.1007/978-3-642-10631-6_37 @inproceedings{DBLP:conf/isaac/KovacsMN09, author = "Kov{\'{a}}cs, Annam{\'{a}}ria and Meyer, Ulrich and Moruz, Gabriel and Negoescu, Andrei", editor = "Dong, Yingfei and Du, Ding{-}Zhu and Ibarra, Oscar H.", biburl = "https://dblp.org/rec/conf/isaac/KovacsMN09.bib", booktitle = "Algorithms and Computation, 20th International Symposium, {ISAAC} 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings", doi = "10.1007/978-3-642-10631-6\_37", pages = "352--361", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "Online paging for flash memory devices", url = "https://doi.org/10.1007/978-3-642-10631-6\_37", volume = "5878", year = "2009" }
15
Annamária Kovács. Tighter approximation bounds for LPT scheduling in two special cases. J. Discrete Algorithms, 7(3):327–340, 2009. View Online doi:10.1016/j.jda.2008.11.004 @article{DBLP:journals/jda/Kovacs09, author = "Kov{\'{a}}cs, Annam{\'{a}}ria", biburl = "https://dblp.org/rec/journals/jda/Kovacs09.bib", doi = "10.1016/j.jda.2008.11.004", journal = "J. Discrete Algorithms", number = "3", pages = "327--340", title = "Tighter approximation bounds for {LPT} scheduling in two special cases", url = "https://doi.org/10.1016/j.jda.2008.11.004", volume = "7", year = "2009" }
16
George Christodoulou, Annamária Kovács, and Michael Schapira. Bayesian combinatorial auctions. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, volume 5125 of Lecture Notes in Computer Science, 820–832. Springer, 2008. View Online doi:10.1007/978-3-540-70575-8_67 @inproceedings{DBLP:conf/icalp/ChristodoulouKS08, author = "Christodoulou, George and Kov{\'{a}}cs, Annam{\'{a}}ria and Schapira, Michael", editor = "Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg, Leslie Ann and Halld{\'{o}}rsson, Magn{\'{u}}s M. and Ing{\'{o}}lfsd{\'{o}}ttir, Anna and Walukiewicz, Igor", biburl = "https://dblp.org/rec/conf/icalp/ChristodoulouKS08.bib", booktitle = "Automata, Languages and Programming, 35th International Colloquium, {ICALP} 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part {I:} Tack {A:} Algorithms, Automata, Complexity, and Games", doi = "10.1007/978-3-540-70575-8\_67", pages = "820--832", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "Bayesian Combinatorial Auctions", url = "https://doi.org/10.1007/978-3-540-70575-8\_67", volume = "5125", year = "2008" }
17
Annamaria Kovacs. Fast Algorithms for Two Scheduling Problems. PhD thesis, Universität des Saarlandes, 2007. @phdthesis{AnnamariaKovacsPhD2007, author = "Kovacs, Annamaria", school = "Universität des Saarlandes", title = "Fast Algorithms for Two Scheduling Problems", year = "2007" }
18
George Christodoulou, Elias Koutsoupias, and Annamária Kovács. Mechanism design for fractional scheduling on unrelated machines. In Lars Arge, Christian Cachin, Tomasz Jurdzinski, and Andrzej Tarlecki, editors, Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings, volume 4596 of Lecture Notes in Computer Science, 40–52. Springer, 2007. View Online doi:10.1007/978-3-540-73420-8_6 @inproceedings{DBLP:conf/icalp/ChristodoulouKK07, author = "Christodoulou, George and Koutsoupias, Elias and Kov{\'{a}}cs, Annam{\'{a}}ria", editor = "Arge, Lars and Cachin, Christian and Jurdzinski, Tomasz and Tarlecki, Andrzej", biburl = "https://dblp.org/rec/conf/icalp/ChristodoulouKK07.bib", booktitle = "Automata, Languages and Programming, 34th International Colloquium, {ICALP} 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings", doi = "10.1007/978-3-540-73420-8\_6", pages = "40--52", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "Mechanism Design for Fractional Scheduling on Unrelated Machines", url = "https://doi.org/10.1007/978-3-540-73420-8\_6", volume = "4596", year = "2007" }
19
Annamária Kovács. Tighter approximation bounds for LPT scheduling in two special cases. In Tiziana Calamoneri, Irene Finocchi, and Giuseppe F. Italiano, editors, Algorithms and Complexity, 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006, Proceedings, volume 3998 of Lecture Notes in Computer Science, 187–198. Springer, 2006. View Online doi:10.1007/11758471_20 @inproceedings{DBLP:conf/ciac/Kovacs06, author = "Kov{\'{a}}cs, Annam{\'{a}}ria", editor = "Calamoneri, Tiziana and Finocchi, Irene and Italiano, Giuseppe F.", biburl = "https://dblp.org/rec/conf/ciac/Kovacs06.bib", booktitle = "Algorithms and Complexity, 6th Italian Conference, {CIAC} 2006, Rome, Italy, May 29-31, 2006, Proceedings", doi = "10.1007/11758471\_20", pages = "187--198", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "Tighter Approximation Bounds for {LPT} Scheduling in Two Special Cases", url = "https://doi.org/10.1007/11758471\_20", volume = "3998", year = "2006" }
20
Annamária Kovács. Fast monotone 3-approximation algorithm for scheduling related machines. In Gerth Stølting Brodal and Stefano Leonardi, editors, Algorithms - ESA 2005, 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005, Proceedings, volume 3669 of Lecture Notes in Computer Science, 616–627. Springer, 2005. View Online doi:10.1007/11561071_55 @inproceedings{DBLP:conf/esa/Kovacs05, author = "Kov{\'{a}}cs, Annam{\'{a}}ria", editor = "Brodal, Gerth St{\o}lting and Leonardi, Stefano", biburl = "https://dblp.org/rec/conf/esa/Kovacs05.bib", booktitle = "Algorithms - {ESA} 2005, 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005, Proceedings", doi = "10.1007/11561071\_55", pages = "616--627", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "Fast Monotone 3-Approximation Algorithm for Scheduling Related Machines", url = "https://doi.org/10.1007/11561071\_55", volume = "3669", year = "2005" }
21
Annamária Kovács. Polynomial time preemptive sum-multicoloring on paths. In Lu\'ıs Caires, Giuseppe F. Italiano, Lu\'ıs Monteiro, Catuscia Palamidessi, and Moti Yung, editors, Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, volume 3580 of Lecture Notes in Computer Science, 840–852. Springer, 2005. View Online doi:10.1007/11523468_68 @inproceedings{DBLP:conf/icalp/Kovacs05, author = "Kov{\'{a}}cs, Annam{\'{a}}ria", editor = "Caires, Lu{\'{\i}}s and Italiano, Giuseppe F. and Monteiro, Lu{\'{\i}}s and Palamidessi, Catuscia and Yung, Moti", biburl = "https://dblp.org/rec/conf/icalp/Kovacs05.bib", booktitle = "Automata, Languages and Programming, 32nd International Colloquium, {ICALP} 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings", doi = "10.1007/11523468\_68", pages = "840--852", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "Polynomial Time Preemptive Sum-Multicoloring on Paths", url = "https://doi.org/10.1007/11523468\_68", volume = "3580", year = "2005" }
22
Annamária Kovács. Sum-multicoloring on paths. In Volker Diekert and Michel Habib, editors, STACS 2004, 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, Proceedings, volume 2996 of Lecture Notes in Computer Science, 68–80. Springer, 2004. View Online doi:10.1007/978-3-540-24749-4_7 @inproceedings{DBLP:conf/stacs/Kovacs04, author = "Kov{\'{a}}cs, Annam{\'{a}}ria", editor = "Diekert, Volker and Habib, Michel", biburl = "https://dblp.org/rec/conf/stacs/Kovacs04.bib", booktitle = "{STACS} 2004, 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, Proceedings", doi = "10.1007/978-3-540-24749-4\_7", pages = "68--80", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "Sum-Multicoloring on Paths", url = "https://doi.org/10.1007/978-3-540-24749-4\_7", volume = "2996", year = "2004" }
23
Annamaria Kovacs. Applications of model theory in set theoretical topology. Master's thesis, ELTE Budapest, 1995. @MastersThesis{AnnamariaKovacsMaster1995, author = "Kovacs, Annamaria", title = "Applications of model theory in set theoretical topology", school = "ELTE Budapest", year = "1995" }