Self-Improving Algorithms (2009)
Ailon, Nir, Chazelle, Bernard, Clarkson, Kenneth L., Liu, Ding, Mulzer, Wolfgang, Seshadhri, C.
We investigate ways in which an algorithm can improve its expected performance by fine-tuning itself automatically with respect to an arbitrary, unknown input distribution. We give such...
A triangulation of a planar point set S is a maximal plane straight-line graph with vertex set S. In the minimum-weight triangulation (MWT) problem, we are looking for a triangulation of a given...
ABSTRACT Markov Incremental Constructions ∗ (2009)
Bernard Chazelle, Wolfgang Mulzer
A classic result asserts that many geometric structures can be constructed optimally by successively inserting their constituent parts in random order. These randomized incremental constructions...
ABSTRACT Markov Incremental Constructions ∗ (2008)
Bernard Chazelle, Wolfgang Mulzer
A classic result asserts that many geometric structures can be constructed optimally by successively inserting their constituent parts in random order. These randomized incremental constructions...
A triangulation of a planar point set S is a maximal plane straight-line graph with vertex set S. Intheminimum weight triangulation (MWT) problem, we are looking for a triangulation of a given point...
A triangulation of a planar point set S is a maximal plane straight-line graph with vertex set S. In the minimum weight triangulation (MWT) problem, we are looking for a triangulation of a given...
A triangulation of a planar point set S is a maximal plane straight-line graph with vertex set S. In the minimum-weight triangulation (MWT) problem, we are looking for a triangulation of a given...
Contents 2 Szemeredi’s Regularity Lemma, and Szemeredi’s Theorem for k=3 (2007)
Rajsekar Manokaran, Indraneel Mukherjee, Wolfgang Mulzer, Aaron Roth, David Steurer, Aravindan Vijayaraghavan, ...
A mini course on additive combinatorics
Minimum-weight triangulation is NP-hard (2006)
Mulzer, Wolfgang, Rote, Guenter
A triangulation of a planar point set S is a maximal plane straight-line graph with vertex set S. In the minimum-weight triangulation (MWT) problem, we are looking for a triangulation of a given...
Minimum weight triangulation is NP-hard (2006)
Wolfgang Mulzer, Günter Rote, Wolfgang Mulzer, Günter Rote
A triangulation of a planar point set S is a maximal plane straight-line graph with vertex set S. In the minimum weight triangulation (MWT) problem, we are looking for a triangulation of a given...
Minimum weight triangulation is NP-hard (2006)
Wolfgang Mulzer, Günter Rote, Wolfgang Mulzer, Günter Rote
A triangulation of a planar point set S is a maximal plane straight-line graph with vertex set S. In the minimum-weight triangulation (MWT) problem, we are looking for a triangulation of a given...
Minimum Dilation Triangulations (2005)
Christian Knauer, Christian Knauer, Wolfgang Mulzer, Wolfgang Mulzer
Given a planar graph G, the graph theoretic dilation of G is defined as the maximum ratio of the shortest-path distance and the Euclidean distance between any two vertices of G. Given a planar point...