Kurt Mehlhorn
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Kurt Mehlhorn has a total of 114 co-authors. Here are the top co-authors by number of shared publications:
- Martin Dietzfelbinger
Technische Universität Ilmenau
12 shared publications - Peter Sanders
Karlsruhe Institute of Technology, Karlsruhe, Germany
12 shared publications - Jugal Garg
Department of Industrial & Enterprise Engineering University of Illinois at Urbana-Champaign USA
8 shared publications - Telikepalli Kavitha
Tata Institute of Fundamental Research, Mumbai, India
6 shared publications - Khaled Elbassioni
Khalifa University
5 shared publications - Martin Hoefer
Dept. of Computer Science RWTH Aachen University
4 shared publications
Latest Publications
- 1 May 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 51 (2) , 853-876
Maximizing Nash Social Welfare in Two-Value Instances: Delineating Tractability
We study the problem of allocating a set of indivisible goods among a set of agents with two-value additive valuations. In this setting, each good is valued either 1 or [ ] for some fixed coprime numbers [ ] such that [ ]. Our goal is to find an allocation that maximizes the Nash social welfare (NSW), that is, the geometric mean of the valuations of the agents. In this work, we give a complete characterization of polynomial-time tractability of NSW maximization that solely depends on the value of q. We start by providing a rather simple polynomial-time algorithm to find a maximum NSW allocation when the valuation functions are integral, that is, [ ]. We then exploit more involved techniques to get an algorithm that produces a maximum NSW allocation for the half-integral case, that is, [ ]. Finally, we show it is NP-hard to compute an allocation with maximum NSW whenever [ ]. Funding: M. Hoefer and G. Varricchio were supported by the DFG [Grant Ho 3831/5-1].
- 1 May 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 51 (2) , 853-876
Maximizing Nash Social Welfare in Two-Value Instances: Delineating Tractability
We study the problem of allocating a set of indivisible goods among a set of agents with two-value additive valuations. In this setting, each good is valued either 1 or [ ] for some fixed coprime numbers [ ] such that [ ]. Our goal is to find an allocation that maximizes the Nash social welfare (NSW), that is, the geometric mean of the valuations of the agents. In this work, we give a complete characterization of polynomial-time tractability of NSW maximization that solely depends on the value of q. We start by providing a rather simple polynomial-time algorithm to find a maximum NSW allocation when the valuation functions are integral, that is, [ ]. We then exploit more involved techniques to get an algorithm that produces a maximum NSW allocation for the half-integral case, that is, [ ]. Finally, we show it is NP-hard to compute an allocation with maximum NSW whenever [ ]. Funding: M. Hoefer and G. Varricchio were supported by the DFG [Grant Ho 3831/5-1].
- Open Access
- 13 April 2026
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 51 (3) , 39
Improving order with queues
Given a sequence of n numbers and k parallel First-in-First-Out (FIFO) queues, how close can one bring the sequence to sorted order? It is known that k queues suffice to sort the sequence if the Longest Decreasing Subsequence (LDS) of the input sequence is at most k . But, what if the number of queues is too small for sorting completely? We give a simple algorithm, based on Patience Sort, that reduces the LDS by $$k - 1$$ . We also show, that the algorithm is optimal, i.e., for any $$L > 0$$ there exists a sequence of LDS L such that the LDS cannot be reduced below $$L - k + 1$$ with k queues. Merging two sorted queues is at the core of Merge Sort. In contrast, two sequences of LDS two cannot always be merged into a sequence of LDS two. We characterize when it is possible and give an algorithm to decide whether it is possible. Merging into a sequence of LDS three is always possible. A down-step in a sequence is an item immediately followed by a smaller item. We give an optimal algorithm for reducing the number of down-steps. The algorithm is online. Our research was inspired by an application in car manufacturing.- 13 April 2026
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 51 (3) , 39
Open AccessImproving order with queues
Given a sequence of n numbers and k parallel First-in-First-Out (FIFO) queues, how close can one bring the sequence to sorted order? It is known that k queues suffice to sort the sequence if the Longest Decreasing Subsequence (LDS) of the input sequence is at most k . But, what if the number of queues is too small for sorting completely? We give a simple algorithm, based on Patience Sort, that reduces the LDS by $$k - 1$$ . We also show, that the algorithm is optimal, i.e., for any $$L > 0$$ there exists a sequence of LDS L such that the LDS cannot be reduced below $$L - k + 1$$ with k queues. Merging two sorted queues is at the core of Merge Sort. In contrast, two sequences of LDS two cannot always be merged into a sequence of LDS two. We characterize when it is possible and give an algorithm to decide whether it is possible. Merging into a sequence of LDS three is always possible. A down-step in a sequence is an item immediately followed by a smaller item. We give an optimal algorithm for reducing the number of down-steps. The algorithm is online. Our research was inspired by an application in car manufacturing. - Open Access
- 16 February 2026
- Published by Springer Nature in Journal of Automated Reasoning
- Vol. 70 (1)
A Formal Correctness Proof of Edmonds’ Blossom Shrinking Algorithm
We present the first formal correctness proof of Edmonds’ blossom shrinking algorithm for maximum cardinality matching in general graphs. We focus on formalising the mathematical structures and properties that allow the algorithm to run in worst-case polynomial running time. We formalise Berge’s lemma, blossoms and their properties, and a mathematical model of the algorithm, showing that it is totally correct. We provide the first detailed proofs of many of the facts underlying the algorithm’s correctness.
- 16 February 2026
- Published by Springer Nature in Journal of Automated Reasoning
- Vol. 70 (1)
Open AccessA Formal Correctness Proof of Edmonds’ Blossom Shrinking Algorithm
We present the first formal correctness proof of Edmonds’ blossom shrinking algorithm for maximum cardinality matching in general graphs. We focus on formalising the mathematical structures and properties that allow the algorithm to run in worst-case polynomial running time. We formalise Berge’s lemma, blossoms and their properties, and a mathematical model of the algorithm, showing that it is totally correct. We provide the first detailed proofs of many of the facts underlying the algorithm’s correctness.
- Open Access
EFX Allocations Exist on Triangle-Free Multi-Graphs
We study the fair allocation of indivisible goods among agents, with a focus on limiting envy. A central open question in this area is the existence of EFX allocations-allocations in which any envy of any agent i towards any agent j vanishes upon the removal of any single good from j's bundle. Establishing the existence of such allocations has proven notoriously difficult in general, but progress has been made for restricted valuation classes. Christodoulou et al. [2023] proved existence for graphical valuations, where goods correspond to edges in a graph, agents to nodes, and each agent values only incident edges. The graph was required to be simple, i.e., for any pair of agents, there could be at most one good that both agents value. The problem remained open, however, for multi-graph valuations, where for a pair of agents several goods may have value to both. In this setting, Sgouritsa and Sotiriou [2025] established existence whenever the shortest cycle with non-parallel edges has length at least six, while Afshinmehr et al. [2025] proved existence when the graph contains no odd cycles. In this paper, we strengthen these results by proving that EFX allocations always exist in multi-graphs that contain no cycle of length three. Assuming monotone valuations, we further provide a pseudo-polynomial time algorithm for computing such an allocation, which runs in polynomial time when agents have cancelable valuations, a strict superclass of additive valuation functions. Accordingly, our results stand as one of the only cases where EFX allocations exist for an arbitrary number of agents.
Open AccessEFX Allocations Exist on Triangle-Free Multi-Graphs
We study the fair allocation of indivisible goods among agents, with a focus on limiting envy. A central open question in this area is the existence of EFX allocations-allocations in which any envy of any agent i towards any agent j vanishes upon the removal of any single good from j's bundle. Establishing the existence of such allocations has proven notoriously difficult in general, but progress has been made for restricted valuation classes. Christodoulou et al. [2023] proved existence for graphical valuations, where goods correspond to edges in a graph, agents to nodes, and each agent values only incident edges. The graph was required to be simple, i.e., for any pair of agents, there could be at most one good that both agents value. The problem remained open, however, for multi-graph valuations, where for a pair of agents several goods may have value to both. In this setting, Sgouritsa and Sotiriou [2025] established existence whenever the shortest cycle with non-parallel edges has length at least six, while Afshinmehr et al. [2025] proved existence when the graph contains no odd cycles. In this paper, we strengthen these results by proving that EFX allocations always exist in multi-graphs that contain no cycle of length three. Assuming monotone valuations, we further provide a pseudo-polynomial time algorithm for computing such an allocation, which runs in polynomial time when agents have cancelable valuations, a strict superclass of additive valuation functions. Accordingly, our results stand as one of the only cases where EFX allocations exist for an arbitrary number of agents.
- Open Access
- 11 April 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 39 (13) , 13675-13682
Welfare-Optimal Serial Dictatorships Have Polynomial Query Complexity
Serial dictatorship is a simple mechanism for coordinating agents in solving combinatorial optimization problems according to their preferences. The most representative such problem is one-sided matching, in which a set of n agents have values for a set of n items, and the objective is to compute a matching of the agents to the items of maximum total value (a.k.a., social welfare). Following the recent framework of Caragiannis and Rathi (2023), we consider a model in which the agent-item values are not available upfront but become known by querying agent sequences. In particular, when the agents are asked to act in a sequence, they respond by picking their favorite item that has not been picked by agents who acted before and reveal their value for it. Can we compute an agent sequence that induces a social welfare-optimal matching? We answer this question affirmatively and present an algorithm that uses polynomial number (specifically, O(n^5) of queries). This solves the main open problem stated by Caragiannis and Rathi (2023). Our analysis uses a potential function argument that measures progress towards learning the underlying edge-weight information. Furthermore, the algorithm has a truthful implementation by adapting the paradigm of VCG payments.
- 11 April 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 39 (13) , 13675-13682
Open AccessWelfare-Optimal Serial Dictatorships Have Polynomial Query Complexity
Serial dictatorship is a simple mechanism for coordinating agents in solving combinatorial optimization problems according to their preferences. The most representative such problem is one-sided matching, in which a set of n agents have values for a set of n items, and the objective is to compute a matching of the agents to the items of maximum total value (a.k.a., social welfare). Following the recent framework of Caragiannis and Rathi (2023), we consider a model in which the agent-item values are not available upfront but become known by querying agent sequences. In particular, when the agents are asked to act in a sequence, they respond by picking their favorite item that has not been picked by agents who acted before and reveal their value for it. Can we compute an agent sequence that induces a social welfare-optimal matching? We answer this question affirmatively and present an algorithm that uses polynomial number (specifically, O(n^5) of queries). This solves the main open problem stated by Caragiannis and Rathi (2023). Our analysis uses a potential function argument that measures progress towards learning the underlying edge-weight information. Furthermore, the algorithm has a truthful implementation by adapting the paradigm of VCG payments.
- 1 March 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 73 (2) , 738-751
EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number
A Simpler Approach to the EFX Problem Envy-freeness up to any item (EFX) has emerged as a compelling fairness notion in discrete fair division. However, its existence remains one of the biggest open problems in the field. In a breakthrough, Chaudhury et al. (2020) establish the existence of EFX allocations for three agents with additive valuations through intricate case analysis. The paper “EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number” by Akrami, Alon, Chaudhury, Garg, Mehlhorn, and Mehta offers a simpler approach for improving the EFX guarantee. They demonstrate the existence of EFX allocations for three agents when at least one has additive valuations (whereas the other two have general monotone valuations). Additionally, they nearly resolve a conjecture regarding the rainbow cycle number, leading to an (almost) tight bound for the existence of approximate EFX allocations with few unallocated items achievable through this approach.
- 1 March 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 73 (2) , 738-751
EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number
A Simpler Approach to the EFX Problem Envy-freeness up to any item (EFX) has emerged as a compelling fairness notion in discrete fair division. However, its existence remains one of the biggest open problems in the field. In a breakthrough, Chaudhury et al. (2020) establish the existence of EFX allocations for three agents with additive valuations through intricate case analysis. The paper “EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number” by Akrami, Alon, Chaudhury, Garg, Mehlhorn, and Mehta offers a simpler approach for improving the EFX guarantee. They demonstrate the existence of EFX allocations for three agents when at least one has additive valuations (whereas the other two have general monotone valuations). Additionally, they nearly resolve a conjecture regarding the rainbow cycle number, leading to an (almost) tight bound for the existence of approximate EFX allocations with few unallocated items achievable through this approach.
- 1 November 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 49 (4) , 2323-2340
Improving Envy Freeness up to Any Good Guarantees Through Rainbow Cycle Number
- 1 November 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 49 (4) , 2323-2340
Improving Envy Freeness up to Any Good Guarantees Through Rainbow Cycle Number
- Open Access
Approximate EFX and Exact tEFX Allocations for Indivisible Chores: Improved Algorithms
We explore the fair distribution of a set of $m$ indivisible chores among $n$ agents, where each agent's costs are evaluated using a monotone cost function. Our focus lies on two fairness criteria: envy-freeness up to any item (EFX) and a relaxed notion, namely envy-freeness up to the transfer of any item (tEFX). We demonstrate that a 2-approximate EFX allocation exists and is computable in polynomial time for three agents with subadditive cost functions, improving upon the previous $(2 + \sqrt{6})$ approximation for additive cost functions. This result requires extensive case analysis. Christoforidis et al. (IJCAI'24) independently claim the same approximation for additive cost functions; however, we provide a counter-example to their algorithm. We expand the number of agents to any number to get the same approximation guarantee with the assumption of partially identical ordering (IDO) for the cost functions. Additionally, we establish that a tEFX allocation is achievable for three agents if one has an additive 2-ratio bounded cost function, while the others may have general monotone cost functions. This is an improvement from the prior requirement of two agents with additive 2-ratio bounded cost functions. This allocation can also be extended to agent groups with identical valuations. Further, we show various analyses of EFX allocations for chores, such as the relaxations for additive $α$-ratio-bounded cost functions.Open AccessApproximate EFX and Exact tEFX Allocations for Indivisible Chores: Improved Algorithms
We explore the fair distribution of a set of $m$ indivisible chores among $n$ agents, where each agent's costs are evaluated using a monotone cost function. Our focus lies on two fairness criteria: envy-freeness up to any item (EFX) and a relaxed notion, namely envy-freeness up to the transfer of any item (tEFX). We demonstrate that a 2-approximate EFX allocation exists and is computable in polynomial time for three agents with subadditive cost functions, improving upon the previous $(2 + \sqrt{6})$ approximation for additive cost functions. This result requires extensive case analysis. Christoforidis et al. (IJCAI'24) independently claim the same approximation for additive cost functions; however, we provide a counter-example to their algorithm. We expand the number of agents to any number to get the same approximation guarantee with the assumption of partially identical ordering (IDO) for the cost functions. Additionally, we establish that a tEFX allocation is achievable for three agents if one has an additive 2-ratio bounded cost function, while the others may have general monotone cost functions. This is an improvement from the prior requirement of two agents with additive 2-ratio bounded cost functions. This allocation can also be extended to agent groups with identical valuations. Further, we show various analyses of EFX allocations for chores, such as the relaxations for additive $α$-ratio-bounded cost functions. - 21 October 2024
- Published by American Physical Society (APS) in Physical Review E
- Vol. 110 (4) , 044310
Self-organized transport in noisy dynamic networks
We present a numerical study of multicommodity transport in a noisy, nonlinear network. The nonlinearity determines the dynamics of the edge capacities, which can be amplified or suppressed depending on the local current flowing across an edge. We consider network self-organization for three different nonlinear functions: For all three we identify parameter regimes where noise leads to self-organization into more robust topologies, that are not found by the sole noiseless dynamics. Moreover, the interplay between noise and specific functional behavior of the nonlinearity gives rise to different features, such as (i) continuous or discontinuous responses to the demand strength and (ii) either single or multistable solutions. Our study shows the crucial role of the activation function on noise-assisted phenomena.
- 21 October 2024
- Published by American Physical Society (APS) in Physical Review E
- Vol. 110 (4) , 044310
Self-organized transport in noisy dynamic networks
We present a numerical study of multicommodity transport in a noisy, nonlinear network. The nonlinearity determines the dynamics of the edge capacities, which can be amplified or suppressed depending on the local current flowing across an edge. We consider network self-organization for three different nonlinear functions: For all three we identify parameter regimes where noise leads to self-organization into more robust topologies, that are not found by the sole noiseless dynamics. Moreover, the interplay between noise and specific functional behavior of the nonlinearity gives rise to different features, such as (i) continuous or discontinuous responses to the demand strength and (ii) either single or multistable solutions. Our study shows the crucial role of the activation function on noise-assisted phenomena.
- Open Access
MMS Approximations Under Additive Leveled Valuations
We study the problem of fairly allocating indivisible goods to a set of agents with additive leveled valuations. A valuation function is called leveled if and only if bundles of larger size have larger value than bundles of smaller size. The economics literature has well studied such valuations. We use the maximin-share (MMS) and EFX as standard notions of fairness. We show that an algorithm introduced by Christodoulou et al. ([11]) constructs an allocation that is EFX and $\frac{\lfloor \frac{m}{n} \rfloor}{\lfloor \frac{m}{n} \rfloor + 1}\text{-MMS}$. In the paper, it was claimed that the allocation is EFX and $\frac{2}{3}\text{-MMS}$. However, the proof of the MMS-bound is incorrect. We give a counter-example to their proof and then prove a stronger approximation of MMS.Open AccessMMS Approximations Under Additive Leveled Valuations
We study the problem of fairly allocating indivisible goods to a set of agents with additive leveled valuations. A valuation function is called leveled if and only if bundles of larger size have larger value than bundles of smaller size. The economics literature has well studied such valuations. We use the maximin-share (MMS) and EFX as standard notions of fairness. We show that an algorithm introduced by Christodoulou et al. ([11]) constructs an allocation that is EFX and $\frac{\lfloor \frac{m}{n} \rfloor}{\lfloor \frac{m}{n} \rfloor + 1}\text{-MMS}$. In the paper, it was claimed that the allocation is EFX and $\frac{2}{3}\text{-MMS}$. However, the proof of the MMS-bound is incorrect. We give a counter-example to their proof and then prove a stronger approximation of MMS.