Decoration
max planck institut
informatik
mpii logo Minerva of the Max Planck Society

Karl Bringmann: Publications

Copyright notice: The respective pre-print or author-prepared version of a paper is provided for timely communication among scholars, without permission for further distribution. The definitive version of a paper is the published version.


Conference Papers


[40]

"Greedy Routing and the Algorithmic Small-World Phenomenom"

Karl Bringmann, Ralph Keusch, Johannes Lengler, Yannic Maus, Anisur Molla

PODC'17: Proc. of the 36th ACM Symposium on Principles of Distributed Computing

[39]

"On Algebraic Branching Programs of Small Width"

Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam

CCC'17: Proc. of the 32th Conference on Computational Complexity

[38]

"Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs"

Karl Bringmann, Thomas Dueholm Hansen, Sebastian Krinninger

ICALP'17: Proc. of the 44th International Colloquium on Automata, Languages, and Programming

[37]

"Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars"

Karl Bringmann, Philip Wellnitz

CPM'17: Proc. of the 28th Annual Symposium on Combinatorial Pattern Matching

[36]

"Maximum Volume Subset Selection for Anchored Boxes"

Karl Bringmann, Sergio Cabello, Michael T.M. Emmerich

SoCG'17: Proc. of the 33rd International Symposium on Computational Geometry

[35]

"A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum"

Karl Bringmann

SODA'17: Proc. of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms

[34]

"Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product"

Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams

FOCS'16: Proc. of the 56th Annual IEEE Symposium on Foundations of Computer Science

[33]

"Hitting Set for Hypergraphs of Low VC-dimension"

Karl Bringmann, László Kozma, Shay Moran, N. S. Narayanaswamy

ESA'16: Proc. of the 24th Annual European Symposium on Algorithms

[32]

"Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping"

Karl Bringmann, Marvin Künnemann

FOCS'15: Proc. of the 55th Annual IEEE Symposium on Foundations of Computer Science

[31]

"Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds"

Karl Bringmann, Marvin Künnemann

ISAAC'15: Proc. of the 26th International Symposium on Algorithms and Computation

[30]

"Ultra-Fast Load Balancing on Scale-Free Networks"

Karl Bringmann, Tobias Friedrich, Martin Hoefer, Ralf Rothenberger, Thomas Sauerwald

ICALP'15: Proc. of the 42th International Colloquium on Automata, Languages, and Programming

[29]

"Efficient Computation of Two-dimensional Solution Sets Maximizing the Epsilon-Indicator"

Karl Bringmann, Tobias Friedrich, Patrick Klitzke

CEC'15: Proc. of the 2015 IEEE Congress on Evolutionary Computation

[28]

"Approximability of the Discrete Fréchet Distance"

Karl Bringmann, Wolfgang Mulzer

SoCG'15: Proc. of the 31st International Symposium on Computational Geometry

[27]

"Parameterized Complexity Dichotomy for Steiner Multicut"

Karl Bringmann, Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen

STACS'15: Proc. of the 32nd Symposium on Theoretical Aspects of Computer Science

[26]

"Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails"

Karl Bringmann

FOCS'14: Proc. of the 55th Annual IEEE Symposium on Foundations of Computer Science

[25]

"De-anonymization of Heterogeneous Random Graphs in Quasilinear Time"

Karl Bringmann, Tobias Friedrich, Anton Krohmer

ESA'14: Proc. of the 22nd Annual European Symposium on Algorithms

[24]

"Generic Postprocessing via Subset Selection for Hypervolume and Epsilon-Indicator"

Karl Bringmann, Tobias Friedrich, Patrick Klitzke

PPSN'14: Proc. of the 13th International Conference on Parallel Problem Solving from Nature

[23]

"Internal DLA: Efficient Simulation of a Physical Growth Model"

Karl Bringmann, Fabian Kuhn, Konstantinos Panagiotou, Ueli Peter, Henning Thomas

ICALP'14: Proc. of the 41th International Colloquium on Automata, Languages and Programming

[22]

"Two-dimensional Subset Selection for Hypervolume and Epsilon-Indicator"

Karl Bringmann, Tobias Friedrich, Patrick Klitzke

GECCO'14: 16th Annual Conference on Genetic and Evolutionary Computation

[21]

"Balls into bins via local search: cover time and maximum load"

Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer, He Sun

STACS'14: Proc. of the 31st Symposium on Theoretical Aspects of Computer Science

[20]

"Counting Triangulations Approximately"

Victor Alvarez, Karl Bringmann, Saurabh Ray, Raimund Seidel

CCCG'13: Proc. of the 25th Canadian Conference on Computational Geometry

[19]

"Bringing Order to Special Cases of Klee’s Measure Problem"

Karl Bringmann

MFCS'13: Proc. of the 38th International Symposium on Mathematical Foundations of Computer Science

[18]

"Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems"

Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao

MFCS'13: Proc. of the 38th International Symposium on Mathematical Foundations of Computer Science

[17]

"Exact and Efficient Generation of Geometric Random Variates and Random Graphs"

Karl Bringmann, Tobias Friedrich

ICALP'13: Proc. of the 40th International Colloquium on Automata, Languages and Programming

[16]

"Online Checkpointing with Improved Worst-Case Guarantees"

Karl Bringmann, Benjamin Doerr, Adrian Neumann, Jakub Sliacan

ICALP'13: Proc. of the 40th International Colloquium on Automata, Languages and Programming

[15]

"Minimizing maximum (weighted) flow-time on related and unrelated machines"

S. Anand, Karl Bringmann, Tobias Friedrich, Naveen Garg, Amit Kumar

ICALP'13: Proc. of the 40th International Colloquium on Automata, Languages and Programming

[14]

"Parameterized Average-Case Complexity of the Hypervolume Indicator"

Karl Bringmann, Tobias Friedrich

GECCO'13: Proc. of the 15th Annual Conference on Genetic and Evolutionary Computation

(Nominated for best paper award)

[13]

"Succinct Sampling from Discrete Distributions"

Karl Bringmann, Kasper Green Larsen

STOC'13: Proc. of the 45th ACM Symposium on the Theory of Computing

[12]

"Efficient Sampling Methods for Discrete Distributions"

Karl Bringmann, Konstantinos Panagiotou

ICALP'12: Proc. of the 39th International Colloquium on Automata, Languages and Programming

[11]

"Convergence of Hypervolume-Based Archiving Algorithms II: Competitiveness"

Karl Bringmann, Tobias Friedrich

GECCO'12: Proc. of the 14th Annual Conference on Genetic and Evolutionary Computation

[10]

"Counting Crossing Free Structures"

Victor Alvarez, Karl Bringmann, Radu Curticapean, Saurabh Ray

SoCG'12: Proc. of the 2012 Annual Symposium on Computational Geometry

[9]

"Approximation-Guided Evolutionary Multi-Objective Optimization"

Karl Bringmann, Tobias Friedrich, Frank Neumann, Markus Wagner

IJCAI'11: Proc. of the 22nd International Joint Conferences on Artificial Intelligence

[8]

"Convergence of Hypervolume-Based Archiving Algorithms I: Effectiveness"

Karl Bringmann, Tobias Friedrich

GECCO'11: Proc. of the 13th Annual Conference on Genetic and Evolutionary Computation

(Nominated for best paper award)

[7]

"The Logarithmic Hypervolume Indicator"

Tobias Friedrich, Karl Bringmann, Thomas Voß, Christian Igel

FOGA'11: Proc. of the 11th ACM Foundations of Genetic Algorithms

[6]

"Klee's measure problem on fat boxes in time O(n(d+2)/3)"

Karl Bringmann

SoCG'10: Proc. of the 2010 Annual Symposium on Computational Geometry

[5]

"Tight Bounds for the Approximation Ratio of the Hypervolume Indicator"

Karl Bringmann, Tobias Friedrich

PPSN'10: Proc. of the 11th International Conference on Parallel Problem Solving From Nature

[4]

"The Maximum Hypervolume Set Yields Near-optimal Approximation"

Karl Bringmann, Tobias Friedrich

GECCO'10: Proc. of the 12th Annual Conference on Genetic and Evolutionary Computation

(Winner of best paper award)

[3]

"Approximating the Least Hypervolume Contributor: NP-hard in General, but Fast in Practice"

Karl Bringmann, Tobias Friedrich

EMO'09: Proc. of the 5th International Conference on Evolutionary Multi-Criterion Optimization

[2]

"Don't be Greedy when Calculating Hypervolume Contributions"

Karl Bringmann, Tobias Friedrich

FOGA'09: Proc. of the 10th ACM Foundations of Genetic Algorithms

[1]

"Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects"

Karl Bringmann, Tobias Friedrich

ISAAC'08: Proc. of the 19th International Symposium on Algorithms and Computation


Journal Papers


[16]

"Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines"

S. Anand, Karl Bringmann, Tobias Friedrich, Naveen Garg, Amit Kumar

Algorithmica, 2017

[15]

"Parameterized Complexity Dichotomy for Steiner Multicut"

Karl Bringmann, Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen

Journal of Computer and System Sciences, 2016

[14]

"Approximability of the Discrete Fréchet Distance"

Karl Bringmann, Wolfgang Mulzer

Journal of Computational Geometry, 2016

[13]

"Balls into Bins via Local Search: Cover Time and Maximum Load"

Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer, He Sun

Random Structures and Algorithms, 2016

[12]

"Online Checkpointing with Improved Worst-Case Guarantees"

Karl Bringmann, Benjamin Doerr, Adrian Neumann, Jakub Sliacan

INFORMS Journal on Computing, 2015

[11]

"Efficient Optimization of Many Objectives by Approximation-Guided Evolution"

Markus Wagner, Karl Bringmann, Tobias Friedrich, Frank Neumann

European Journal of Operational Research, 2015

[10]

"Counting Triangulations and Other Crossing-Free Structures via Onion Layers"

Victor Alvarez, Karl Bringmann, Radu Curticapean, Saurabh Ray

Discrete & Computational Geometry, 2015

[9]

"Counting Triangulations and other Crossing-Free Structures Approximately"

Victor Alvarez, Karl Bringmann, Saurabh Ray, Raimund Seidel

Computational Geometry: Theory and Applications, 2015

Special Issue on the 25th Canadian Conference on Computational Geometry (CCCG'13)

[8]

"Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems"

Karl Bringmann, Christian Engels, Bodo Manthey, B. V. Raghavendra Rao

Algorithmica, 2015

[7]

"Convergence of Hypervolume-Based Archiving Algorithms"

Karl Bringmann, Tobias Friedrich

IEEE Trans. Evolutionary Computation, 2014

[6]

"Speeding Up Many-Objective Optimization by Monte Carlo Approximations"

Karl Bringmann, Tobias Friedrich, Christian Igel, Thomas Voß

Artificial Intelligence, 2013

[5]

"Approximation Quality of the Hypervolume Indicator"

Karl Bringmann, Tobias Friedrich

Artificial Intelligence, 2013

[4]

"An improved algorithm for Klee's measure problem on fat boxes"

Karl Bringmann

Computational Geometry: Theory and Applications, 2012

[3]

"Approximating the least hypervolume contributor: NP-hard in general, but fast in practice"

Karl Bringmann, Tobias Friedrich

Theoretical Computer Science, 2012

[2]

"An Efficient Algorithm for Computing Hypervolume Contributions"

Karl Bringmann, Tobias Friedrich

Evolutionary Computation, 2010

[1]

"Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects"

Karl Bringmann, Tobias Friedrich

Computational Geometry: Theory and Applications, 2010