Chaudhury, Bhaskar Ray; Kavitha, Telikepalli; Mehlhorn, Kurt; Sgouritsa, Alkmini A little charity guarantees almost envy-freeness. (English) Zbl 1525.91102 SIAM J. Comput. 50, No. 4, 1336-1358 (2021). MSC: 91B32 PDFBibTeX XMLCite \textit{B. R. Chaudhury} et al., SIAM J. Comput. 50, No. 4, 1336--1358 (2021; Zbl 1525.91102) Full Text: DOI arXiv
Chaudhury, Bhaskar Ray; Kavitha, Telikepalli; Mehlhorn, Kurt; Sgouritsa, Alkmini A little charity guarantees almost envy-freeness. (English) Zbl 07304186 Chawla, Shuchi (ed.), Proceedings of the 31st annual ACM-SIAM symposium on discrete algorithms, SODA 2020, Salt Lake City, UT, USA, January 5–8, 2020. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2658-2672 (2020). MSC: 91B32 PDFBibTeX XMLCite \textit{B. R. Chaudhury} et al., in: Proceedings of the 31st annual ACM-SIAM symposium on discrete algorithms, SODA 2020, Salt Lake City, UT, USA, January 5--8, 2020. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2658--2672 (2020; Zbl 07304186) Full Text: DOI
Akrami, Hannaneh; Mehlhorn, Kurt; Odland, Tommy Ratio-balanced maximum flows. (English) Zbl 1461.05101 Inf. Process. Lett. 150, 13-17 (2019). MSC: 05C21 05C90 05C85 91B52 PDFBibTeX XMLCite \textit{H. Akrami} et al., Inf. Process. Lett. 150, 13--17 (2019; Zbl 1461.05101) Full Text: DOI arXiv
Afshani, Peyman; Agrawal, Manindra; Doerr, Benjamin; Doerr, Carola; Larsen, Kasper Green; Mehlhorn, Kurt The query complexity of a permutation-based variant of mastermind. (English) Zbl 1411.91153 Discrete Appl. Math. 260, 28-50 (2019). MSC: 91A46 68Q25 91-04 PDFBibTeX XMLCite \textit{P. Afshani} et al., Discrete Appl. Math. 260, 28--50 (2019; Zbl 1411.91153) Full Text: DOI arXiv
Chaudhury, Bhaskar Ray; Mehlhorn, Kurt Combinatorial algorithms for general linear Arrow-Debreu markets. (English) Zbl 1528.91036 Ganguly, Sumit (ed.) et al., 38th IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2018, Ahmedabad, India, December 11–13, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 122, Article 26, 16 p. (2018). MSC: 91B26 68Q25 91B52 PDFBibTeX XMLCite \textit{B. R. Chaudhury} and \textit{K. Mehlhorn}, LIPIcs -- Leibniz Int. Proc. Inform. 122, Article 26, 16 p. (2018; Zbl 1528.91036) Full Text: DOI arXiv
Chaudhury, Bhaskar Ray; Cheung, Yun Kuen; Garg, Jugal; Garg, Naveen; Hoefer, Martin; Mehlhorn, Kurt On fair division for indivisible items. (English) Zbl 1528.91043 Ganguly, Sumit (ed.) et al., 38th IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2018, Ahmedabad, India, December 11–13, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 122, Article 25, 17 p. (2018). MSC: 91B32 68W25 PDFBibTeX XMLCite \textit{B. R. Chaudhury} et al., LIPIcs -- Leibniz Int. Proc. Inform. 122, Article 25, 17 p. (2018; Zbl 1528.91043) Full Text: DOI arXiv
Croitoru, Cosmina; Mehlhorn, Kurt On testing substitutability. (English) Zbl 1458.68293 Inf. Process. Lett. 138, 19-21 (2018). MSC: 68W40 91B08 91B68 PDFBibTeX XMLCite \textit{C. Croitoru} and \textit{K. Mehlhorn}, Inf. Process. Lett. 138, 19--21 (2018; Zbl 1458.68293) Full Text: DOI arXiv
Garg, Jugal; Hoefer, Martin; Mehlhorn, Kurt Approximating the Nash social welfare with budget-additive valuations. (English) Zbl 1403.91210 Czumaj, Artur (ed.), Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7–10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-503-1/ebook). 2326-2340 (2018). MSC: 91B32 91B15 91-04 PDFBibTeX XMLCite \textit{J. Garg} et al., in: Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7--10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2326--2340 (2018; Zbl 1403.91210) Full Text: Link
Bei, Xiaohui; Garg, Jugal; Hoefer, Martin; Mehlhorn, Kurt Earning limits in Fisher markets with spending-constraint utilities. (English) Zbl 1403.91146 Bilò, Vittorio (ed.) et al., Algorithmic game theory. 10th international symposium, SAGT 2017, L’Aquila, Italy, September 12–14, 2017. Proceedings. Cham: Springer (ISBN 978-3-319-66699-0/pbk; 978-3-319-66700-3/ebook). Lecture Notes in Computer Science 10504, 67-79 (2017). MSC: 91B24 91-04 PDFBibTeX XMLCite \textit{X. Bei} et al., Lect. Notes Comput. Sci. 10504, 67--79 (2017; Zbl 1403.91146) Full Text: DOI
Duan, Ran; Garg, Jugal; Mehlhorn, Kurt An improved combinatorial polynomial algorithm for the linear Arrow-Debreu market. (English) Zbl 1417.91326 Krauthgamer, Robert (ed.), Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 90-106 (2016). MSC: 91B50 90C27 PDFBibTeX XMLCite \textit{R. Duan} et al., in: Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10--12, 2016. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 90--106 (2016; Zbl 1417.91326) Full Text: DOI arXiv
Bei, Xiaohui; Garg, Jugal; Hoefer, Martin; Mehlhorn, Kurt Computing equilibria in markets with budget-additive utilities. (English) Zbl 1397.91242 Sankowski, Piotr (ed.) et al., 24th annual European symposium on algorithms, ESA 2016, Aarhus, Denmark, August 22–24, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-015-6). LIPIcs – Leibniz International Proceedings in Informatics 57, Article 8, 14 p. (2016). MSC: 91B26 68Q17 68Q25 91B50 PDFBibTeX XMLCite \textit{X. Bei} et al., LIPIcs -- Leibniz Int. Proc. Inform. 57, Article 8, 14 p. (2016; Zbl 1397.91242) Full Text: DOI arXiv
Elbassioni, Khaled; Mehlhorn, Kurt; Ramezani, Fahimeh Towards more practical linear programming-based techniques for algorithmic mechanism design. (English) Zbl 1356.91050 Theory Comput. Syst. 59, No. 4, 641-663 (2016). MSC: 91B26 90C10 68W25 PDFBibTeX XMLCite \textit{K. Elbassioni} et al., Theory Comput. Syst. 59, No. 4, 641--663 (2016; Zbl 1356.91050) Full Text: DOI arXiv
Darwish, Omar; Mehlhorn, Kurt Improved balanced flow computation using parametric flow. (English) Zbl 1361.91050 Inf. Process. Lett. 116, No. 9, 560-563 (2016). MSC: 91B52 90B10 68Q25 PDFBibTeX XMLCite \textit{O. Darwish} and \textit{K. Mehlhorn}, Inf. Process. Lett. 116, No. 9, 560--563 (2016; Zbl 1361.91050) Full Text: DOI arXiv
Mehlhorn, Kurt On the implementation of combinatorial algorithms for the linear exchange market. (English) Zbl 1331.91088 Zaroliagis, Christos (ed.) et al., Algorithms, probability, networks, and games. Scientific papers and essays dedicated to Paul G. Spirakis on the occasion of his 60th birthday. Cham: Springer (ISBN 978-3-319-24023-7/pbk; 978-3-319-24024-4/ebook). Lecture Notes in Computer Science 9295, 87-94 (2015). MSC: 91B26 68Q25 91B52 PDFBibTeX XMLCite \textit{K. Mehlhorn}, Lect. Notes Comput. Sci. 9295, 87--94 (2015; Zbl 1331.91088) Full Text: DOI
Elbassioni, Khaled; Mehlhorn, Kurt; Ramezani, Fahimeh Towards more practical linear programming-based techniques for algorithmic mechanism design. (English) Zbl 1358.91058 Hoefer, Martin (ed.), Algorithmic game theory. 8th international symposium, SAGT 2015, Saarbrücken, Germany, September 28–30, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48432-6/pbk; 978-3-662-48433-3/pbk). Lecture Notes in Computer Science 9347, 98-109 (2015). MSC: 91B26 90C05 90C59 PDFBibTeX XMLCite \textit{K. Elbassioni} et al., Lect. Notes Comput. Sci. 9347, 98--109 (2015; Zbl 1358.91058) Full Text: DOI Link
Elbassioni, Khaled; Makino, Kazuhisa; Mehlhorn, Kurt; Ramezani, Fahimeh On randomized fictitious play for approximating saddle points over convex sets. (English) Zbl 1330.91012 Algorithmica 73, No. 2, 441-459 (2015). MSC: 91A05 68W20 90C05 90C27 PDFBibTeX XMLCite \textit{K. Elbassioni} et al., Algorithmica 73, No. 2, 441--459 (2015; Zbl 1330.91012) Full Text: DOI arXiv
Duan, Ran; Mehlhorn, Kurt A combinatorial polynomial algorithm for the linear Arrow-Debreu market. (English) Zbl 1329.91089 Inf. Comput. 243, 112-132 (2015). MSC: 91B52 68Q25 91B26 PDFBibTeX XMLCite \textit{R. Duan} and \textit{K. Mehlhorn}, Inf. Comput. 243, 112--132 (2015; Zbl 1329.91089) Full Text: DOI arXiv
Christodoulou, Giorgos; Mehlhorn, Kurt; Pyrga, Evangelia Improving the price of anarchy for selfish routing via coordination mechanisms. (English) Zbl 1291.91037 Algorithmica 69, No. 3, 619-640 (2014). MSC: 91A43 91A10 68M20 PDFBibTeX XMLCite \textit{G. Christodoulou} et al., Algorithmica 69, No. 3, 619--640 (2014; Zbl 1291.91037) Full Text: DOI arXiv
Duan, Ran; Mehlhorn, Kurt A combinatorial polynomial algorithm for the linear Arrow-Debreu market. (English) Zbl 1328.91198 Fomin, Fedor V. (ed.) et al., Automata, languages, and programming. 40th international colloquium, ICALP 2013, Riga, Latvia, July 8–12, 2013, Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-39205-4/pbk). Lecture Notes in Computer Science 7965, 425-436 (2013). MSC: 91B52 68Q25 91B26 PDFBibTeX XMLCite \textit{R. Duan} and \textit{K. Mehlhorn}, Lect. Notes Comput. Sci. 7965, 425--436 (2013; Zbl 1328.91198) Full Text: DOI arXiv
Manlove, David F. [Mehlhorn, Kurt] Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn. (English) Zbl 1283.68018 Series on Theoretical Computer Science 2. Hackensack, NJ: World Scientific (ISBN 978-981-4425-24-7/hbk; 978-981-4425-26-1/ebook). xxxi, 491 p. (2013). Reviewer: Vladimír Lacko (Košice) MSC: 68-02 68Wxx 05C70 91B68 90C35 PDFBibTeX XMLCite \textit{D. F. Manlove}, Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn. Hackensack, NJ: World Scientific (2013; Zbl 1283.68018) Full Text: DOI
Elbassioni, Khaled; Makino, Kazuhisa; Mehlhorn, Kurt; Ramezani, Fahimeh On randomized fictitious play for approximating saddle points over convex sets. (English) Zbl 1382.91007 Du, Ding-Zhu (ed.) et al., Computing and combinatorics. 19th international conference, COCOON 2013, Hangzhou, China, June 21–23, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38767-8/pbk). Lecture Notes in Computer Science 7936, 65-76 (2013). MSC: 91A05 68W20 90C05 90C27 PDFBibTeX XMLCite \textit{K. Elbassioni} et al., Lect. Notes Comput. Sci. 7936, 65--76 (2013; Zbl 1382.91007) Full Text: DOI arXiv
Christodoulou, George; Mehlhorn, Kurt; Pyrga, Evangelia Improving the price of anarchy for selfish routing via coordination mechanisms. (English) Zbl 1346.91021 Demetrescu, Camil (ed.) et al., Algorithms – ESA 2011. 19th annual European symposium, Saarbrücken, Germany, September 5–9, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-23718-8/pbk). Lecture Notes in Computer Science 6942, 119-130 (2011). MSC: 91A43 68M20 PDFBibTeX XMLCite \textit{G. Christodoulou} et al., Lect. Notes Comput. Sci. 6942, 119--130 (2011; Zbl 1346.91021) Full Text: DOI arXiv
Kavitha, Telikepalli; Mehlhorn, Kurt; Michail, Dimitrios; Paluch, Katarzyna E. Strongly stable matchings in time \(O(nm)\) and extension to the hospitals-residents problem. (English) Zbl 1321.05207 ACM Trans. Algorithms 3, No. 2, Article No. 15, 18 p. (2007). MSC: 05C70 05C85 68Q25 91B68 PDFBibTeX XMLCite \textit{T. Kavitha} et al., ACM Trans. Algorithms 3, No. 2, Article No. 15, 18 p. (2007; Zbl 1321.05207) Full Text: DOI
Abraham, David J.; Irving, Robert W.; Kavitha, Telikepalli; Mehlhorn, Kurt Popular matchings. (English) Zbl 1154.91033 SIAM J. Comput. 37, No. 4, 1030-1045 (2007). MSC: 91B68 05C70 68Q25 PDFBibTeX XMLCite \textit{D. J. Abraham} et al., SIAM J. Comput. 37, No. 4, 1030--1045 (2007; Zbl 1154.91033) Full Text: DOI
Abraham, David J.; Irving, Robert W.; Kavitha, Telikepalli; Mehlhorn, Kurt Popular matchings. (English) Zbl 1297.68087 Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2005, Vancouver, BC, Canada, January 23–25, 2005. New York, NY: ACM Press (ISBN 0-89871-585-7). 424-432 (2005). MSC: 68Q25 91B68 PDFBibTeX XMLCite \textit{D. J. Abraham} et al., in: Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2005, Vancouver, BC, Canada, January 23--25, 2005. New York, NY: ACM Press. 424--432 (2005; Zbl 1297.68087)
Abraham, David J.; Cechlárová, Katarína; Manlove, David F.; Mehlhorn, Kurt Pareto optimality in house allocation problems. (English) Zbl 1115.90049 Deng, Xiaotie (ed.) et al., Algorithms and computation. 16th international symposium, ISAAC 2005, Sanya, Hainan, China, December 19–21, 2005. Proceedings. Berlin: Springer (ISBN 3-540-30935-7/pbk). Lecture Notes in Computer Science 3827, 1163-1175 (2005). MSC: 90C29 91A12 91B32 PDFBibTeX XMLCite \textit{D. J. Abraham} et al., Lect. Notes Comput. Sci. 3827, 1163--1175 (2005; Zbl 1115.90049) Full Text: DOI
Kavitha, Telikepalli; Mehlhorn, Kurt; Michail, Dimitrios; Paluch, Katarzyna Strongly stable matchings in time \(O(nm)\) and extension to the hospitals-residents problem. (English) Zbl 1122.68459 Diekert, Volker (ed.) et al., STACS 2004. 21st annual symposium on theoretical aspects of computer science, Montpellier, France, March 25–27, 2004. Proceedings. Berlin: Springer (ISBN 3-540-21236-1/pbk). Lecture Notes in Computer Science 2996, 222-233 (2004). MSC: 68Q25 05C70 91B68 PDFBibTeX XMLCite \textit{T. Kavitha} et al., Lect. Notes Comput. Sci. 2996, 222--233 (2004; Zbl 1122.68459) Full Text: DOI
Abraham, David J.; Cechlárová, Katarína; Manlove, David F.; Mehlhorn, Kurt Pareto optimality in house allocation problems. (English) Zbl 1116.90393 Fleischer, Rudolf (ed.) et al., Algorithms and computation. 15th international symposium, ISAAC 2004, Hong Kong, China, December 20–22, 2004. Proceedings. Berlin: Springer (ISBN 3-540-24131-0/pbk). Lecture Notes in Computer Science 3341, 3-15 (2004). MSC: 90C29 91A12 91B32 PDFBibTeX XMLCite \textit{D. J. Abraham} et al., Lect. Notes Comput. Sci. 3341, 3--15 (2004; Zbl 1116.90393) Full Text: DOI
Mehlhorn, K.; Näher, St.; Rauch, M. On the complexity of a game related to the dictionary problem. (English) Zbl 0711.68034 SIAM J. Comput. 19, No. 5, 902-906 (1990). MSC: 68P05 91A05 68Q25 PDFBibTeX XMLCite \textit{K. Mehlhorn} et al., SIAM J. Comput. 19, No. 5, 902--906 (1990; Zbl 0711.68034) Full Text: DOI