101 citations · 211 across the 45 of their papers we have counts for
5 papers · 1 filter
A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market
Ran Duan, Kurt Mehlhorn
We present the first combinatorial polynomial time algorithm for computing the equilibrium of the Arrow-Debreu market model with linear utilities.
The Cost of Address Translation
Tomasz Jurkiewicz, Kurt Mehlhorn
Modern computers are not random access machines (RAMs). They have a memory hierarchy, multiple cores, and virtual memory. In this paper, we address the computational cost of addres…
Certifying 3-Edge-Connectivity
Kurt Mehlhorn, Adrian Neumann, Jens M. Schmidt
We present a certifying algorithm that tests graphs for 3-edge-connectivity; the algorithm works in linear time. If the input graph is not 3-edge-connected, the algorithm returns a…
Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms
George Christodoulou, Kurt Mehlhorn, Evangelia Pyrga
We reconsider the well-studied Selfish Routing game with affine latency functions. The Price of Anarchy for this class of games takes maximum value 4/3; this maximum is attained al…
Remarks on Category-Based Routing in Social Networks
Karl Bringmann, Kurt Mehlhorn, Adrian Neumann
It is well known that individuals can route messages on short paths through social networks, given only simple information about the target and using only local knowledge about the…