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, S. Haslebacher, H. Hoang. A subexponential algorithm for ARRIVAL, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), LIPIcs 198, 69:1-96:14.
    [DROPS]
  2. B. Gärtner, A. N. Zehmakan. Majority Rule Cellular Automata. Theoretical Computer Science 889, 2021, pp.41-59
    [TCS]
  3. K. Clarkson, B. Gärtner, J. Lengler, M. Szedlák. Random Sampling with Removal, Discrete and Computational Geometry 64(3), 2020, pp.700-733
    Conference version: 32nd International Symposium on Computational Geometry (SoCG 2016), 40:1–40:16.
    [DCG][DROPS]
  4. B. Gärtner, A. N. Zehmakan. Threshold Behavior of Democratic Opinion Dynamic, Journal of Statistical Physics 178, 2020, pp. 1442-1466
    [Journal of Statistical Physics]
  5. R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner. The Crossing Tverberg Theorem, Proc. 35th International Symposium on Computational Geometry (SoCG 2019), LIPICS Vol. 129, 2019
    [LIPICS]
  6. B. Cohn, B. Gärtner, M. Szedlák, F. J. Valero-Cuevas. Feasibility Theory Reconciles and Informs Alternative Approaches to Neuromuscular Control, Front. Comput. Neurosci. 11, 2018
    [Frontiersin]
  7. B. Gärtner, T. D. Hansen, P. Hubáček, K. Král, H. Mosaad, V. Slívová. ARRIVAL: Next Stop in CLS, 45th International Colloquium on Automata, Languages, and Programming (ICALP), 2018, pp 60:1-60:13,
    [DROPS] [arxiv]
  8. B. Gärtner, A. N. Zehmakan. Majority Model on Random Regular Graphs, LATIN 2018: Theoretical Informatics, Lecture Notes in Computer Science, vol 10807, Springer, 2018, pp 572-583
    [LNCS] [arxiv]
  9. 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 7(2), pp. 183-249, 2018
    [IaI] [arxiv]
  10. K. Fukuda, B. Gärtner, M. Szedlák, Combinatorial Redundancy Detection, Annals of Operations Research 265(1), 2018, pp. 47–65
    [ANOR] [arxiv]
  11. 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, published by Springer), 2017, pp. 367-374
    [Springer] [arxiv]
  12. 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, 2017, pp 393-404
    [LNCS]
  13. S.U. Stich, C.L. Müller, B. Gärtner, Variable Metric Random Pursuit, Mathematical Programming, 156:1 (2016), 549-579.
    [abstract] [MathProg] [bibtex]
  14. 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]
  15. 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.
    Conference 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]
  16. 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.
    [DROPS]
  17. B. Gärtner, Sampling with Removal in LP-type Problems, Journal of Computational Geometry (JoCG), 6:2 (2015), 93-112.
    [abstract] [JoCG] [bibtex]
  18. 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]
  19. 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]
  20. 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]
  21. 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]
  22. 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]
  23. 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]
  24. 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]
  25. Y. Brise, B. Gärtner, Clarkson's Algorithm for Violator Spaces, Computational Geometry - Theory and Applications, 42, 2011, 70-81.
    [abstract] [doi] [arXiv] [bibtex]
  26. 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]
  27. B. Gärtner, M. Jaggi, Coresets for Polytope Distance, Proc. 25th Annual Symposium on Computational Geometry (SoCG), (2009), 33-42.
    [abstract] [pdf] [doi] [bibtex]
  28. 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]
  29. 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.
    Conference version: Proc. 14th Annual European Symposium on Algorithms (ESA), (2006), 387-398.
    [abstract] [DOI] [pdf] [arXiv] [bibtex]
  30. B. Gärtner, W.D. Morris, L. Rüst, Unique Sink Orientations of Grids, Algorithmica, 51:2 (2008), 200-235.
    Conference version: Proc. 11th Conference on Integer Programming and Combinatorial Optimization (IPCO), LNCS 3509 © Springer-Verlag, (2005), 210-224.
    [abstract] [DOI] [pdf] [techreport 472][bibtex]
  31. 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]
  32. 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]
  33. 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]
  34. 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]
  35. 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
    Conference version: Proc. 19th Annual ACM Symposium on Computational Geometry (SoCG), (2003), 292-301.
    [abstract] [pdf] [bibtex]
  36. 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.
    Conference version: Proc. 33rd Annual ACM Symposium on Theory of Computing (STOC), (2001), 306-315.
    [pdf] [bibtex]
  37. 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]
  38. B. Gärtner, The Random-Facet Simplex Algorithm on Combinatorial Cubes, Random Structures & Algorithms, 20:3 (2002), 353-381.
    Conference version: Proc. 2nd Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), LNCS 1518 © Springer-Verlag, (1998), 82-96.
    [abstract] [pdf] [bibtex]
  39. B. Gärtner, E. Welzl, A Simple Sampling Lemma: Analysis and Applications in Geometric Optimization, Discrete & Computational Geometry 25:4 (2001), 569-590.
    Conference version: Proc. 16th Annual ACM Symposium on Computational Geometry (SoCG), (2000), 91-99.
    [abstract] [pdf] [bibtex]
  40. 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]
  41. A. Dumitrescu, B. Gärtner, S. Pedroni, Enumerating Triangulation Paths, Computational Geometry - Theory and Applications 20, (2001), 3-12.
    Conference version: Proc. 12th Canadian Conference on Computational Geometry (CCCG), (2000), 233-238.
    [pdf] [bibtex]
  42. 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]
  43. 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]
  44. 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]
  45. B. Gärtner, Pitfalls in Computing with Pseudorandom Determinants, Proc. 16th Annual ACM Symposium on Computational Geometry (SoCG), (2000), 148-155.
    [abstract] [pdf] [bibtex]
  46. 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]
  47. B. Gärtner, Exact Arithmetic at Low Cost - A Case Study in Linear Programming, Computational Geometry - Theory and Applications, 13 (1999), 121-139.
    Conference version: Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), (1998), 157-166.
    [abstract] [pdf] [bibtex]
  48. B. Gärtner, S. Schönherr, Exact Primitives for Smallest Enclosing Ellipses, Information Processing Letters, 68 (1998), 33-38.
    Conference version: Proc. 13th Annual ACM Symposium on Computational Geometry (SoCG), (1997), 430-432.
    [abstract] [pdf] [bibtex]
  49. B. Gärtner, M. Henk, G. Ziegler, Randomized Simplex Algorithms on Klee-Minty Cubes, Combinatorica, 18:3 (1998), 349-372.
    Conference version: Proc. 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS), (1994), 502-510
    [abstract] [pdf] [bibtex]
  50. 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]
  51. B. Gärtner, A Subexponential Algorithm for Abstract Optimization Problems, SIAM Journal on Computing, 24 (1995), 1018-1035.
    Conference version: Proc. 33rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), (1992), 464-472.
    [abstract] [pdf] [bibtex]
  52. B. Gärtner, E. Welzl, Vapnik-Chervonenkis Dimension and (Pseudo-)Hyperplane Arrangements, Discrete & Computational Geometry, 12:4 (1994), 399-432.
    [abstract] [pdf] [bibtex]