Researcher Portfolio
Prof. Dr. Mehlhorn, Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society
Researcher Profile
Position: Algorithms and Complexity, MPI for Informatics, Max Planck Society
Additional IDs: ORCID:
https://orcid.org/0000-0003-4020-4334
Researcher ID: https://pure.mpg.de/cone/persons/resource/persons45021
Publications
(1 - 25 of 581)
: Akrami, H., Ray Chaudhury, B., Hoefer, M., Mehlhorn, K., Schmalhofer, M., Shahkarami, G., Varricchio, G., Vermande, Q., & van Wijland, E. (2025). Maximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability. Mathematics of Operations Research. doi:10.1287/moor.2023.0204. [PubMan] : Caragiannis, I., Mehlhorn, K., & Rathi, N. (in press). Welfare-Optimal Serial Dictatorships have Polynomial Query Complexity. In Proceedings of the 39th AAAI Conference on Artificial Intelligence. Palo Alto, CA: AAAI. [PubMan] : Ansaripour, M., Danaei, A., & Mehlhorn, K. (2024). Gabow's Cardinality Matching Algorithm in General Graphs: Implementation and Experiments. Retrieved from https://arxiv.org/abs/2409.14849. [PubMan] : Afshinmehr, M., Danaei, A., Kazemi, M., Mehlhorn, K., & Rathi, N. (in press). EFX Allocations and Orientations on Bipartite Multi-Graphs: A Complete Picture. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems. New York, NY: ACM. [PubMan] : Ray Chaudhury, B., Garg, J., & Mehlhorn, K. (2024). EFX Exists for Three Agents. Journal of the ACM, 71(1): 4, pp. 1-27. doi:10.1145/3616009. [PubMan] : Afshinmehr, M., Ansaripour, M., Danaei, A., & Mehlhorn, K. (2024). Approximate EFX and Exact tEFX Allocations for Indivisible Chores: Improved Algorithms. Retrieved from https://arxiv.org/abs/2410.18655. [PubMan] : Ray Chaudhury, B., Garg, J., Mehlhorn, K., Mehta, R., & Misra, P. (2024). Improving Envy Freeness up to Any Good Guarantees Through Rainbow Cycle Number. Mathematics of Operations Research, 49(4), 2323-2340. doi:10.1287/moor.2021.0252. [PubMan] : Folz, F., Mehlhorn, K., & Morigi, G. (2024). Self-organized Transport in Noisy Dynamic Networks. Physical Review E, 110(4): 044310. doi:10.1103/PhysRevE.110.044310. [PubMan] : Afshinmehr, M., Kazemi, M., & Mehlhorn, K. (2024). MMS Approximations Under Additive Leveled Valuations. Retrieved from https://arxiv.org/abs/2410.02274. [PubMan] : Akrami, H., Alon, N., Ray Chaudhury, B., Garg, J., Mehlhorn, K., & Mehta, R. (2024). EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number. Operations Research, 1-14. doi:10.1287/opre.2023.0433. [PubMan] : Garg, J., Hoefer, M., & Mehlhorn, K. (2024). Satiation in Fisher Markets and Approximation of Nash Social Welfare. Mathematics of Operations Research, 49(2), 1109-1139. doi:10.1287/moor.2019.0129. [PubMan] : Mehlhorn, K. (2024). Maximizing Nash Social Welfare in 2-Value Instances: A Simpler Proof for the Half-Integer Case. Retrieved from https://arxiv.org/abs/2411.06924. [PubMan] : Akrami, H., Ray Chaudhury, B., Garg, J., Mehlhorn, K., & Mehta, R. (2023). Fair and Efficient Allocation of Indivisible Chores with Surplus. In E. Elkind (Ed. ), Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (pp. 2494-2502). IJCAI. doi:10.24963/ijcai.2023/277. [PubMan] : Folz, F., Mehlhorn, K., & Morigi, G. (2023). Noise-Induced Network Topologies. Physical Review Letters, 130(26): 267401. doi:10.1103/PhysRevLett.130.267401. [PubMan] : Akrami, H., Alon, N., Ray Chaudhury, B., Garg, J., Mehlhorn, K., & Mehta, R. (2023). EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number. In EC 2023 (pp. 61-61). New York, NY: ACM. [PubMan] : Akrami, H., Mehlhorn, K., Seddighin, M., & Shahkarami, G. (2023). Randomized and Deterministic Maximin-share Approximations for Fractionally Subadditive Valuations. In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, & S. Levine (Eds. ), Advances in Neural Information Processing Systems 36 (pp. 58821-58832). Curran Associates, Inc. [PubMan] : Gao, Y., Kamkari, H., Karrenbauer, A., Mehlhorn, K., & Sharifi, M. (2022). Physarum Inspired Dynamics to Solve Semi-Definite Programs. Retrieved from https://arxiv.org/abs/2111.02291. [PubMan] : Bonifaci, V., Facca, E., Folz, F., Karrenbauer, A., Kolev, P., Mehlhorn, K., Morigi, G., Shahkarami, G., & Vermande, Q. (2022). Physarum-inspired Multi-commodity Flow Dynamics. Theoretical Computer Science, 920, 1-20. doi:10.1016/j.tcs.2022.02.001. [PubMan] : Halperin, D., Har-Peled, S., Mehlhorn, K., Oh, E., & Sharir, M. (2022). The Maximum-Level Vertex in an Arrangement of Lines. Discrete & Computational Geometry, 67, 439-461. doi:10.1007/s00454-021-00338-9. [PubMan] : Ray Chaudhury, B., Cheung, Y. K., Garg, J., Garg, N., Hoefer, M., & Mehlhorn, K. (2022). Fair Division of Indivisible Goods for a Class of Concave Valuations. Journal of Artificial Intelligence Research, 74, 111-142. doi:10.1613/jair.1.12911. [PubMan] : Akrami, H., Alon, N., Ray Chaudhury, B., Garg, J., Mehlhorn, K., & Mehta, R. (2022). EFX Allocations: Simplifications and Improvements. Retrieved from https://arxiv.org/abs/2205.07638. [PubMan] : Akrami, H., Ray Chaudhury, B., Hoefer, M., Mehlhorn, K., Schmalhofer, M., Shahkarami, G., Varricchio, G., Vermande, Q., & van Wijland, E. (2022). Maximizing Nash Social Welfare in 2-Value Instances: The Half-Integer Case. Retrieved from https://arxiv.org/abs/2207.10949. [PubMan] : Akrami, H., Ray Chaudhury, B., Hoefer, M., Mehlhorn, K., Schmalhofer, M., Shahkarami, G., Varricchio, G., Vermande, Q., & van Wijland, E. (2022). Maximizing Nash Social Welfare in 2-Value Instances. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (pp. 4760-4767). Palo Alto, CA: AAAI. doi:10.1609/aaai.v36i5.20402. [PubMan] : Ray Chaudhury, B., Kavitha, T., Mehlhorn, K., & Sgouritsa, A. (2021). A Little Charity Guarantees Almost Envy-Freeness. SIAM Journal on Computing, 50(4), 1336-1358. doi:10.1137/20M1359134. [PubMan] : Akrami, H., Ray Chaudhury, B., Mehlhorn, K., Shahkarami, G., & Vermande, Q. (2021). Nash Social Welfare for 2-value Instances. Retrieved from https://arxiv.org/abs/2106.14816. [PubMan]