Department of Computer Science | Institute of Theoretical Computer Science

Theory of Combinatorial Algorithms

Prof. Emo Welzl

Publications in journals and refereed conference proceedings

  1. B. Gärtner, A. Krause, A. Kyrillidis, H. Tyagi, Algorithms for Learning Sparse Additive Models with Interactions in High Dimensions, Information and Inference: A Journal of the IMA, (2017, to appear)
  2. K. Fukuda, B. Gärtner, M. Szedlák, Combinatorial Redundancy Detection, Annals of Operations Research (2017, to appear).
  3. J. Dohrau, B. Gärtner, M.Kohler, J. Matoušek, E. Welzl, A zero-player graph game in NP ∩ coNP, A Journey through Discrete Mathematics. A Tribute to Jiří Matoušek (edited by Martin Loebl, Jaroslav Nešetřil and Robin Thomas, due to be published by Springer), (2017, to appear)
  4. B. Gärtner, A. N. Zehmakan. Color War: Cellular Automata with Majority Rule,In: Drewes F., Martín-Vide C., Truthe B. (eds) Language and Automata Theory and Applications. LATA 2017. Lecture Notes in Computer Science, vol 10168. Springer, Cham, pp 393-404
  5. S.U. Stich, C.L. Müller, B. Gärtner, Variable Metric Random Pursuit, Mathematical Programming, 156:1 (2016), 549-579.
    [abstract] [MathProg] [bibtex]
  6. J. Emiris, V. Fisikopoulos, B. Gärtner, Efficient edge-skeleton computation for polytopes defined by oracles, Journal of Symbolic Computation, 73:C (2016), 139-152.
    [abstract] [JoSC] [bibtex]
  7. H. Tyagi, S.U. Stich, B. Gärtner, On Two Continuum Armed Bandit Problems in High Dimensions, Theory of Computing Systems (TOCS), 58:1 (2016), 191-222.
    Preliminary version: H. Tyagi, B. Gärtner, Continuum armed bandit problem of few variables in high dimensions, Proc. 11th Workshop on Approximation and Online Algorithms (WAOA), (2014), LNCS 8447, 108-119.
    [abstract] [TOCS] [bibtex]
  8. B. Gärtner, J. Lengler, M. Szedlák, Random Sampling with Removal, 32nd International Symposium on Computational Geometry (SoCG 2016), 40:1–40:16.
  9. B. Gärtner, A. Thomas, The Niceness of Unique Sink Orientations, Proc. 20th International Workshop on Randomization and Computation (APPROX-RANDOM) (2016), 30:1-30:14.
  10. B. Gärtner, Sampling with Removal in LP-type Problems, Journal of Computational Geometry (JoCG), 6:2 (2015), 93-112.
    [abstract] [JoCG] [bibtex]
  11. B. Gärtner, A. Thomas, The Complexity of Recognizing Unique Sink Orientations, Proc. 32nd Symposium on Theoretical Aspects of Computer Science (STACS), (2015), 341-353.
    [abstract] [STACS] [bibtex]
  12. H. Tyagi, A. Krause, B. Gärtner, Efficient Sampling for Learning Sparse Additive Models in High Dimensions, Advances in Neural Information Processing Systems (NIPS) 27, (2014), 514-522.
    [abstract] [NIPS] [bibtex]
  13. J. Foniok, B. Gärtner, L. Klaus, M. Sprecher, Counting Unique Sink Orientations, Discrete Applied Mathematics (DAM), 163, Part 2 (2014), 155-164
    [abstract] [DAM] [arXiv] [bibtex]
  14. C. Ambühl, B. Gärtner, B. von Stengel, Optimal lower bounds for projective list update algorithms, ACM Transactions on Algorithms (TALG), 9:4 (2013), 31:1-31:18.
    [abstract] [TALG] [arXiv] [bibtex]
  15. S.U. Stich, C.L. Müller, B. Gärtner, Optimization of Convex Functions with Random Pursuit, SIAM Journal on Optimization, 23:2 (2013), 1284-1309.
    [abstract] [DOI] [arXiv] [bibtex]
  16. B. Gärtner, M. Sprecher, A Polynomial-Time Algorithm for the Tridiagonal and Hessenberg P-Matrix Linear Complementarity Problem, Operations Research Letters, 40:6 (2012), 484-486.
    [abstract] [ORL] [arXiv] [bibtex]
  17. B. Gärtner, M. Jaggi, C. Maria, An Exponential Lower Bound on the Complexity of Regularization Paths, Journal of Computational Geometry (JoCG), 3:1 (2012), 168-195.
    [abstract] [JoCG] [arXiv] [bibtex]
  18. Y. Brise, B. Gärtner, Clarkson's Algorithm for Violator Spaces, Computational Geometry - Theory and Applications, 42, 2011, 70-81.
    [abstract] [doi] [arXiv] [bibtex]
  19. J. Foniok, K. Fukuda, B. Gärtner, H.-J. Lüthi, Pivoting in Linear Complementarity: Two Polynomial-Time Cases, Discrete & Computational Geometry, 42:2 (2009), 187-205.
    [abstract] [doi] [arXiv] [bibtex]
  20. B. Gärtner, M. Jaggi, Coresets for Polytope Distance, Proc. 25th Annual Symposium on Computational Geometry (SoCG), (2009), 33-42.
    [abstract] [pdf] [doi] [bibtex]
  21. T. Galkovskyi, B. Gärtner, B. Rublev, The Domination Heuristic for LP-type problems, Proc. Tenth Workshop on Algorithm Engineering and Experiments (ALENEX), (2009), 74-84.
    [abstract] [pdf] [html] [bibtex]
  22. B. Gärtner, J. Matoušek, L. Rüst, P. Škovroň, Violator Spaces: Structure and Algorithms, Discrete Applied Mathematics (special issue In Memory of Leonid Khachiyan (1952 - 2005)), 15:11 (2008), 2124-2141.
    Preliminary version: Proc. 14th Annual European Symposium on Algorithms (ESA), (2006), 387-398.
    [abstract] [DOI] [pdf] [arXiv] [bibtex]
  23. B. Gärtner, W.D. Morris, L. Rüst, Unique Sink Orientations of Grids, Algorithmica, 51:2 (2008), 200-235.
    Preliminary version: Proc. 11th Conference on Integer Programming and Combinatorial Optimization (IPCO), LNCS 3509 © Springer-Verlag, (2005), 210-224.
    [abstract] [DOI] [pdf] [techreport 472][bibtex]
  24. B. Gärtner, V. Kaibel, Two new bounds for the Random-Edge simplex algorithm, SIAM Journal on Discrete Mathematics, 21 (2007), 178-190.
    [abstract] [DOI] [arXiv] [bibtex]
  25. B. Gärtner, I. Schurr, Linear programming and unique sink orientations, Proc. 17th Annual Symposium on Discrete Algorithms (SODA), (2006), 749-757.
    [abstract] [pdf] [bibtex]
  26. S. Felsner, B. Gärtner, F. Tschirschnitz, Grid orientations, (d,d+2)-polytopes, and arrangements of pseudolines, Discrete & Computational Geometry, 34:3 (2005), 411-437.
    [abstract] [pdf] [bibtex]
  27. B. Gärtner, Leo Rüst, Simple Stochastic Games and P-matrix Generalized Linear Complementarity Problems, Proc. 15th International Symposium on Fundamentals of Computation Theory (FCT), LNCS 3623, © Springer-Verlag, (2005), 209-220.
    [abstract] [pdf] [bibtex]
  28. K. Fischer, B. Gärtner, The Smallest Enclosing Ball of Balls - Combinatorial Structure and Algorithms, International Journal of Computational Geometry and Applications (IJCGA), 14(4-5) (2004), 341-378
    Preliminary version: Proc. 19th Annual ACM Symposium on Computational Geometry (SoCG), (2003), 292-301.
    [abstract] [pdf] [bibtex]
  29. B. Gärtner, József Solymosi, Pavel Valtr, F. Tschirschnitz, E. Welzl, One line and n points, Random Structures & Algorithms, 23:4 (2003), 453-471.
    Preliminary version: Proc. 33rd Annual ACM Symposium on Theory of Computing (STOC), (2001), 306-315.
    [pdf] [bibtex]
  30. K. Fischer, B. Gärtner, M. Kutz, Fast Smallest-Enclosing-Ball Computation in High Dimensions, Proc. 11th Annual European Symposium on Algorithms (ESA), (2003), 630-641.
    [abstract] [pdf] [bibtex]
  31. B. Gärtner, The Random-Facet Simplex Algorithm on Combinatorial Cubes, Random Structures & Algorithms, 20:3 (2002), 353-381.
    Preliminary version: Proc. 2nd Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), LNCS 1518 © Springer-Verlag, (1998), 82-96.
    [abstract] [pdf] [bibtex]
  32. B. Gärtner, E. Welzl, A Simple Sampling Lemma: Analysis and Applications in Geometric Optimization, Discrete & Computational Geometry 25:4 (2001), 569-590.
    Preliminary version: Proc. 16th Annual ACM Symposium on Computational Geometry (SoCG), (2000), 91-99.
    [abstract] [pdf] [bibtex]
  33. C. Ambühl, B. Gärtner, Bernhard von Stengel, A New Lower Bound for the List Update Problem in the Partial Cost Model, Theoretical Computer Science, 268 (2001), 3-16.
    [pdf] [bibtex]
  34. A. Dumitrescu, B. Gärtner, S. Pedroni, Enumerating Triangulation Paths, Computational Geometry - Theory and Applications 20, (2001), 3-12.
    Preliminary version: Proc. 12th Canadian Conference on Computational Geometry (CCCG), (2000), 233-238.
    [pdf] [bibtex]
  35. C. Ambühl, S. Chakraborty, B. Gärtner, Computing largest common point sets under approximate congruence, Proc. 8th Annual European Symposium on Algorithms (ESA), LNCS 1879 © Springer-Verlag, (2000), 52-63.
    [pdf] [bibtex]
  36. C. Ambühl, B. Gärtner, Bernhard von Stengel, Optimal projective algorithms for the list update problem, Proc. 27th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 1853 © Springer-Verlag, (2000), 305-316.
    [pdf] [bibtex]
  37. B. Gärtner, S. Schönherr, An Efficient, Exact, and Generic Quadratic Programming Solver for Geometric Optimization, Proc. 16th Annual ACM Symposium on Computational Geometry (SoCG), (2000), 110-118.
    [abstract] [pdf] [bibtex]
  38. B. Gärtner, Pitfalls in Computing with Pseudorandom Determinants, Proc. 16th Annual ACM Symposium on Computational Geometry (SoCG), (2000), 148-155.
    [abstract] [pdf] [bibtex]
  39. B. Gärtner, Fast and Robust Smallest Enclosing Balls, Proc. 7th Annual European Symposium on Algorithms (ESA), LNCS 1643 © Springer-Verlag, (1999), 325-338.
    [abstract] [pdf] [bibtex]
  40. B. Gärtner, Exact Arithmetic at Low Cost - A Case Study in Linear Programming, Computational Geometry - Theory and Applications, 13 (1999), 121-139.
    Preliminary version: Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), (1998), 157-166.
    [abstract] [pdf] [bibtex]
  41. B. Gärtner, S. Schönherr, Exact Primitives for Smallest Enclosing Ellipses, Information Processing Letters, 68 (1998), 33-38.
    Preliminary version: Proc. 13th Annual ACM Symposium on Computational Geometry (SoCG), (1997), 430-432.
    [abstract] [pdf] [bibtex]
  42. B. Gärtner, M. Henk, G. Ziegler, Randomized Simplex Algorithms on Klee-Minty Cubes, Combinatorica, 18:3 (1998), 349-372.
    Preliminary version: Proc. 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS), (1994), 502-510
    [abstract] [pdf] [bibtex]
  43. O. Aichholzer, D. Alberts, F. Aurenhammer, B. Gärtner, A Novel Type of Skeleton for Polygon, Journal of Universal Computer Science (JUCS), 1:12 (1995), 349-372.
    [abstract] [html] [bibtex]
  44. B. Gärtner, A Subexponential Algorithm for Abstract Optimization Problems, SIAM Journal on Computing, 24 (1995), 1018-1035.
    Preliminary version: Proc. 33rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), (1992), 464-472.
    [abstract] [pdf] [bibtex]
  45. B. Gärtner, E. Welzl, Vapnik-Chervonenkis Dimension and (Pseudo-)Hyperplane Arrangements, Discrete & Computational Geometry, 12:4 (1994), 399-432.
    [abstract] [pdf] [bibtex]