Kurt Mehlhorn

Kurt Mehlhorn

Auto-generated profile, based on publicly available information

Kurt Mehlhorn

Max Planck Institute for Informatics, Saarbrücken, Germany

Research Focus & Metrics

Academic Career Length

36Years (1991-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 May 2008 in Computational Geometry
Verified
Journal Article
Closed access
LKLutz Kettner
Lutz Kettner
KMKurt Mehlhorn
Kurt Mehlhorn
SPSylvain Pion
Sylvain Pion
SSStefan Schirra
Stefan Schirra
CYChee Yap
Chee Yap

1 December 2012 in Theoretical Computer Science
Verified
Journal Article
Closed access
NMNicole Megow
Nicole Megow
KMKurt Mehlhorn
Kurt Mehlhorn
PSPascal Schweitzer
Pascal Schweitzer

17 January 2012
Verified
Conference Paper
Closed access
VBVincenzo Bonifaci
Vincenzo Bonifaci
KMKurt Mehlhorn
Kurt Mehlhorn
GVGirish Varma
Girish Varma

11 February 2024 in Journal of the ACM
Verified
Journal Article
Open access
BCBhaskar Ray Chaudhury
Bhaskar Ray Chaudhury
JGJugal Garg
Jugal Garg
KMKurt Mehlhorn
Kurt Mehlhorn
We study the problem of distributing a set of indivisible goods among agents with additive valuations in a fair manner. The fairness notion under consideration is envy-freeness up to any good (EFX). Despite significant efforts by many researchers for several years, the existence of EFX allocations has not been settled beyond the simple case of two agents. In this article, we show constructively that an EFX allocation always exists for three agents. Furthermore, we falsify the conjecture of Caragiannis et al. by showing an instance with three agents for which there is a partial EFX allocation (some goods are not allocated) with higher Nash welfare than that of any complete EFX allocation.

15 February 2013 in Algorithmica
Verified
Journal Article
Closed access
PDF file
GCGiorgos Christodoulou
Giorgos Christodoulou
KMKurt Mehlhorn
Kurt Mehlhorn
EPEvangelia Pyrga
Evangelia Pyrga

13 October 2007 in Algorithmica
Verified
Journal Article
Open access
PDF file
TKTelikepalli Kavitha
Telikepalli Kavitha
KMKurt Mehlhorn
Kurt Mehlhorn
DMDimitrios Michail
Dimitrios Michail
KPKatarzyna Paluch
Katarzyna Paluch
We consider the problem of computing a minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over \(\mathbb{F}_{2}\) generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Minimum cycle basis are useful in a number of contexts, e.g. the analysis of electrical networks and structural engineering. The previous best algorithm for computing a minimum cycle basis has running time O(m ω n), where ω is the best exponent of matrix multiplication. It is presently known that ω0, we also design an 1+ε approximation algorithm. The running time of this algorithm is O((m ω /ε)log (W/ε)) for reasonably dense graphs, where W is the largest edge weight.