Publications in journals and refereed conference proceedings

No. Title Reference Year Preliminary version Resources
28 Clarkson's Algorithm for Violator Spaces (with Y. Brise) Computational Geometry - Theory and Applications 42, 2011, pp. 70-81 2011 [abstract] [doi] [arXiv] [bibtex]
27 Pivoting in Linear Complementarity: Two Polynomial-Time Cases (with J. Foniok, K. Fukuda, and H.-J. Lüthi) Discrete & Computational Geometry 42(2), 2009, pp. 187-205 2009 [abstract] [doi] [arXiv] [bibtex]
26 Coresets for Polytope Distance (with M. Jaggi) Proc. 25th Annual Symposium on Computational Geometry (SoCG), pp. 33-42 2009 [abstract] [pdf] [doi] [bibtex]
25 The Domination Heuristic for LP-type problems (with T. Galkovskyi and B. Rublev) Proc. Tenth Workshop on Algorithm Engineering and Experiments (ALENEX), 2009, pp. 74-84 2009 [abstract] [pdf] [html] [bibtex]
24 Violator Spaces: Structure and Algorithms (with J. Matoušek, L. Rüst, P. Škovroň) Discrete Applied Mathematics 15(11) (special issue In Memory of Leonid Khachiyan (1952 - 2005 )), 2008, pp. 2124-2141 2008 Proc. 14th Annual European Symposium on Algorithms (ESA), pp. 387--398 [abstract] [DOI] [pdf] [arXiv] [bibtex]
23 Unique Sink Orientations of Grids (with Leo Rüst and Walter D. Morris) Algorithmica 51(2), 2008, pp. 200-235 2008 Proc. 11th Conference on Integer Programming and Combinatorial Optimization (IPCO), Lecture Notes in Computer Science 3509 © Springer-Verlag, pp. 210-224 [abstract] [DOI] [pdf] [techreport 472][bibtex]
22 Two new bounds for the Random-Edge simplex algorithm (with Volker Kaibel) SIAM Journal on Discrete Mathematics 21, 2007, pp. 178-190 2007 [abstract] [DOI] [arXiv] [bibtex]
21 Linear programming and unique sink orientations (with Ingo Schurr) Proc. 17th Annual Symposium on Discrete Algorithms (SODA), pp. 749--757 2006 [abstract] [pdf] [bibtex]
20 Grid orientations, (d,d+2)-polytopes, and arrangements of pseudolines (with Stefan Felsner and Falk Tschirschnitz) Discrete & Computational Geometry 34(3), 2005, pp. 411--437 2005 [abstract] [pdf] [bibtex]
19 Simple Stochastic Games and P-matrix Generalized Linear Complementarity Problems (with Leo Rüst) Proc. 15th International Symposium on Fundamentals of Computation Theory (FCT), Lecture Notes in Computer Science 3623 © Springer-Verlag, pp. 209-220. 2005 [abstract] [pdf] [bibtex]
18 The Smallest Enclosing Ball of Balls - Combinatorial Structure and Algorithms (with Kaspar Fischer) International Journal of Computational Geometry and Applications (IJCGA) 14(4-5), pp. 341-378 2004 Proc. 19th Annual ACM Symposium on Computational Geometry (SCG), pp. 292-301 [abstract] [pdf] [bibtex]
17 One line and n points (with Falk Tschirschnitz, József Solymosi, Pavel Valtr and Emo Welzl) Random Structures & Algorithms 23(4), pp. 453-471 2003 Proc. 33rd Annual ACM Symposium on Theory of Computing (STOC), pp. 306-315 , 2001 [ps.gz] [pdf] [bibtex]
16 Fast Smallest-Enclosing-Ball Computation in High Dimensions (with Kaspar Fischer and Martin Kutz) Proc. 11th Annual European Symposium on Algorithms (ESA), pp. 630-641 2003 [abstract] [ps.gz] [pdf] [bibtex]
15 The Random-Facet Simplex Algorithm on Combinatorial Cubes Random Structure and Algorithms 20(3), pp. 353-381 2002 Proc. 2nd Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), Lecture Notes in Computer Science 1518 © Springer-Verlag, pp. 82-96, 1998 [abstract] [ps.gz] [pdf] [bibtex]
14 A Simple Sampling Lemma: Analysis and Applications in Geometric Optimization (with Emo Welzl) Discrete & Computational Geometry 25(4), 2001, pp. 569--590 2001 Proc. 16th Annual ACM Symposium on Computational Geometry (SCG), pp. 91-99, 2000 [abstract] [ps.gz] [pdf] [bibtex]
13 A New Lower Bound for the List Update Problem in the Partial Cost Model (with Christoph Ambühl and Bernhard von Stengel) Theoretical Computer Science 268, pp. 3-16 2001 [ps.gz] [pdf] [bibtex]
12 Enumerating Triangulation Paths (with Adrian Dumitrescu, Samuele Pedroni and Emo Welzl) Computational Geometry - Theory and Applications 20, pp. 3-12 2001 Proc. 12th Canadian Conference on Computational Geometry (CCCG), pp. 233-238, 2000 [ps.gz] [pdf] [bibtex]
11 Computing largest common point sets under approximate congruence (with Christoph Ambühl and Samarjit Chakraborty) Proc. 8th Annual European Symposium on Algorithms (ESA), Lecture Notes in Computer Science 1879 © Springer-Verlag, pp. 52-63 2000 [ps.gz] [pdf] [bibtex]
10 Optimal projective algorithms for the list update problem (with Christoph Ambühl and Bernhard von Stengel) Proc. 27th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science 1853 © Springer-Verlag, pp. 305-316 2000 [ps.gz] [pdf] [bibtex]
9 An Efficient, Exact, and Generic Quadratic Programming Solver for Geometric Optimization (with Sven Schönherr ) Proc. 16th Annual ACM Symposium on Computational Geometry (SCG), pp. 110-118 2000 [abstract] [ps.gz] [pdf] [bibtex]
8 Pitfalls in Computing with Pseudorandom Determinants Proc. 16th Annual ACM Symposium on Computational Geometry (SCG), pp. 148-155 2000 [abstract] [ps.gz] [pdf] [bibtex]
7 Fast and Robust Smallest Enclosing Balls Proc. 7th Annual European Symposium on Algorithms (ESA), Lecture Notes in Computer Science 1643 © Springer-Verlag, pp. 325-338 1999 [abstract] [ps.gz] [pdf] [bibtex]
6 Exact Arithmetic at Low Cost - A Case Study in Linear Programming Computational Geometry - Theory and Applications 13 pp. 121-139 1999 Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 157-166 [abstract] [ps.gz] [pdf] [bibtex]
5 Exact Primitives for Smallest Enclosing Ellipses (with Sven Schönherr ) Information Processing Letters 68, pp. 33-38 1998 Proc. 13th Annual ACM Symposium on Computational Geometry (SCG), pp. 430-432, 1997 [abstract] [ps.gz] [pdf] [bibtex]
4 Randomized Simplex Algorithms on Klee-Minty Cubes (with Martin Henk and Günter Ziegler ) Combinatorica 18(3), 349-372 1998 Proc. 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 502-510 [abstract] [ps.gz] [pdf] [bibtex]
3 A Novel Type of Skeleton for Polygon (with Oswin Aichholzer, David Alberts and Franz Aurenhammer) Journal of Universal Computer Science (JUCS) 1(12) 1995 [abstract] [html] [bibtex]
2 A Subexponential Algorithm for Abstract Optimization Problems SIAM Journal on Computing 24, pp. 1018-1035 1995 Proc. 33rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 464-472 [abstract] [ps.gz] [pdf] [bibtex]
1 Vapnik-Chervonenkis Dimension and (Pseudo-)Hyperplane Arrangements (with Emo Welzl) Discrete & Computational Geometry 12(4), pp. 399-432 1994 [abstract] [ps.gz] [pdf] [bibtex]

Other publications / Manuscripts

Title Reference Year Sources
Strong LP-type Problems Manuscript 2002 [ps.gz]
Linear Programming via Unique Sinks Manuscript 2002 [ps.gz]
Computing the Width of a Point Set in 3-Space (with Thomas Herrmann) Proc. 13th Canadian Conference on Computational Geometry, pp. 101-104 2001 [ps.gz]
Explicit and Implicit Enforcing - Randomized Optimization Lectures of the Graduate Program Computational Discrete Mathematics, Lecture Notes in Computer Science 2122 © Springer-Verlag, pp. 26-49 2001 [ps.gz] [pdf]
Ein Reinfall mit Computer-Zufallszahlen (in German) Mitteilungen der Deutschen Mathematiker-Vereinigung (DMV), Ausgabe 2, pp. 55-60 1999 [ps.gz]
Abstract Objective Function Graphs on the 3-cube - A Classification by Realizability (with Volker Kaibel) Technical Report TR 296, Department of Computer Science, ETH Zürich 1998 [abstract] [ps.gz] [pdf]
Smallest Enclosing Ellipses - Fast and Exact (with Sven Schönherr) Technical Report B-97-03, Mathematics Department, Freie Universität Berlin 1997 [abstract] [ps.gz] [pdf]
Linear Programming - Randomization and Abstract Frameworks (with Emo Welzl) Invited paper, Proc. 13th Annual Symp. on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science 1064, © Springer-Verlag, pp. 669-687 1996 [abstract] [ps.gz] [pdf]

Theses

Title Reference Year Sources
Randomized Optimization by Simplex-Type Methods PhD thesis (Doktorarbeit), Institute for Computer Science, Mathematics Department, Freie Universität Berlin 1995 [html]
Set Systems of Bounded Vapnik-Chervonenkis Dimension and a Relation to Arrangements Master thesis (Diplomarbeit), Institute for Computer Science, Mathematics Department, Freie Universität Berlin 1991 [summary] [ps-file]