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


[101]

"Beating Bellman's Algorithm for Subset Sum"

Karl Bringmann, Nick Fischer, Vasileios Nakos

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

[100]

"Exploring the Approximability Landscape of 3SUM"

Karl Bringmann, Ahmed Ghazy, Marvin Künnemann

ESA'24: Proc. of the 32nd Annual European Symposium on Algorithms

[99]

"Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing"

Karl Bringmann, Anita Dürr, Adam Polak

ESA'24: Proc. of the 32nd Annual European Symposium on Algorithms

Best paper award of ESA Track A

[98]

"Knapsack with Small Items in Near-Quadratic Time"

Karl Bringmann

STOC'24: Proc. of the 56th ACM Symposium on the Theory of Computing

[97]

"Fine-Grained Complexity of Earth Mover's Distance under Translation"

Karl Bringmann, Frank Staals, Karol Węgrzycki, Geert van Wordragen

SoCG'24: Proc. of the 40th International Symposium on Computational Geometry

Invited to JoCG special issue

[96]

"The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds"

Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen

ITCS'24: Proc. of the 15th Innovations in Theoretical Computer Science conference

Invited to TheoretiCS

[95]

"Faster Sublinear-Time Edit Distance"

Karl Bringmann, Alejandro Cassis, Nick Fischer, Tomasz Kociumaka

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

[94]

"Approximating Subset Sum Ratio faster than Subset Sum"

Karl Bringmann

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

[93]

"The Time Complexity of Fully Sparse Matrix Multiplication"

Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann

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

[92]

"Dynamic Dynamic Time Warping"

Karl Bringmann, Nick Fischer, Ivor van der Hoog, Evangelos Kipouridis, Tomasz Kociumaka, Eva Rotenberg

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

[91]

"Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!"

Karl Bringmann, Alejandro Cassis, Nick Fischer

FOCS'23: Proc. of the 64th Annual IEEE Symposium on Foundations of Computer Science

[90]

"Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution"

Karl Bringmann, Alejandro Cassis

ESA'23: Proc. of the 31st Annual European Symposium on Algorithms

[89]

"Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics"

Amir Abboud, Karl Bringmann, Nick Fischer

STOC'23: Proc. of the 55th ACM Symposium on the Theory of Computing

Invited to SICOMP special issue

[88]

"Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms"

Karl Bringmann, Michael Kapralov, Mikhail Makarov, Vasileios Nakos, Amir Yagudin, Amir Zandieh

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

[87]

"Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution"

Karl Bringmann, Alejandro Cassis

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

[86]

"Improved Sublinear-Time Edit Distance for Preprocessed Strings"

Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos

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

[85]

"A Structural Investigation of the Approximability of Polynomial-Time Problems"

Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann

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

[84]

"Tight Fine-Grained Bounds for Direct Access on Join Queries"

Karl Bringmann, Nofar Carmeli, Stefan Mengel

PODS'22: Proc. of the 41st ACM Symposium on Principles of Database Systems

[83]

"Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves"

Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, Dániel Marx, André Nusser

SoCG'22: Proc. of the 38th International Symposium on Computational Geometry

[82]

"Towards sub-quadratic diameter computation in geometric intersection graphs"

Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, André Nusser, Zahra Parsaeian

SoCG'22: Proc. of the 38th International Symposium on Computational Geometry

[81]

"Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds"

Bahareh Banyassady, Mark de Berg, Karl Bringmann, Kevin Buchin, Henning Fernau, Dan Halperin, Irina Kostitsyna, Yoshio Okamoto, Stijn Slot

SoCG'22: Proc. of the 38th International Symposium on Computational Geometry

[80]

"Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond"

Amir Abboud, Karl Bringmann, Seri Khoury, Or Zamir

STOC'22: Proc. of the 54th ACM Symposium on the Theory of Computing

[79]

"Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime"

Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos

STOC'22: Proc. of the 54th ACM Symposium on the Theory of Computing

[78]

"Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution"

Karl Bringmann, Nick Fischer, Vasileios Nakos

SODA'22: Proc. of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms

[77]

"Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance"

Karl Bringmann, Anne Driemel, André Nusser, Ioannis Psarros

SODA'22: Proc. of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms

[76]

"Fine-Grained Completeness for Optimization in P"

Karl Bringmann, Alejandro Cassis, Nick Fischer, Marvin Künnemann

APPROX-RANDOM'21: Proc. of the 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems

[75]

"Fast n-fold Boolean Convolution via Additive Combinatorics"

Karl Bringmann, Vasileios Nakos

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

[74]

"Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal"

Karl Bringmann, Jasper Slusallek

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

[73]

"A Linear-Time n0.4-Approximation for Longest Common Subsequence"

Karl Bringmann, Vincent Cohen-Addad*, Debarati Das

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

*Vincent Cohen-Addad is author of the extended Arxiv version, but not of the ICALP proceedings version.

[72]

"Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution"

Karl Bringmann, Nick Fischer, Vasileios Nakos

STOC'21: Proc. of the 53rd ACM Symposium on the Theory of Computing

[71]

"Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation"

Karl Bringmann, André Nusser

SoCG'21: Proc. of the 37th International Symposium on Computational Geometry

Invited to JoCG special issue

[70]

"A Fine-Grained Perspective on Approximating Subset Sum and Partition"

Karl Bringmann, Vasileios Nakos

SODA'21: Proc. of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms

[69]

"On Near-Linear-Time Algorithms for Dense Subset Sum"

Karl Bringmann, Philip Wellnitz

SODA'21: Proc. of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms

[68]

"Fast and Simple Modular Subset Sum"

Kyriakos Axiotis, Arturs Backurs, Karl Bringmann, Ce Jin, Vasileios Nakos, Christos Tzamos, Hongxun Wu

SOSA@SODA'21: Proc. of the 4th SIAM Symposium on Simplicity in Algorithms

[67]

"Impossibility Results for Grammar-Compressed Linear Algebra"

Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann

NeurIPS'20: Proc. of the 34th Annual Conference on Neural Information Processing Systems

[66]

"When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance Under Translation"

Karl Bringmann, Marvin Künnemann, André Nusser

ESA'20: Proc. of the 28th Annual European Symposium on Algorithms

[65]

"Scheduling Lower Bounds via AND Subset Sum"

Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay

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

[64]

"Faster Minimization of Tardy Processing Time on a Single Machine"

Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay, Philip Wellnitz

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

[63]

"Top-k-Convolution and the Quest for Near-linear Output-sensitive Subset Sum"

Karl Bringmann, Vasileios Nakos

STOC'20: Proc. of the 52nd ACM Symposium on the Theory of Computing

[62]

"On Geometric Set Cover for Orthants"

Karl Bringmann, Sándor Kisfaludi-Bak, Michał Pilipczuk, Erik Jan van Leeuwen

ESA'19: Proc. of the 27th Annual European Symposium on Algorithms

[61]

"A Fine-Grained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties"

Karl Bringmann, Nick Fischer, Marvin Künnemann

CCC'19: Proc. of the 34th Conference on Computational Complexity

[60]

"Polyline Simplification has Cubic Complexity"

Karl Bringmann, Bhaskar Ray Chaudhury

SoCG'19: Proc. of the 35rd International Symposium on Computational Geometry

Invited to JoCG special issue

[59]

"Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance"

Karl Bringmann, Marvin Künnemann, André Nusser

SoCG'19: Proc. of the 35th International Symposium on Computational Geometry

[58]

"Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max"

Karl Bringmann, Marvin Künnemann, Karol Węgrzycki

STOC'19: Proc. of the 51st ACM Symposium on the Theory of Computing

[57]

"Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability"

Karl Bringmann, Marvin Künnemann, André Nusser

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

[56]

"Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts"

Karl Bringmann, Marvin Künnemann, Philip Wellnitz

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

[55]

"SETH-Based Lower Bounds for Subset Sum and Bicriteria Path"

Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay

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

Invited to HALG'20 and to TALG special issue

[54]

"A PTAS for l_p-Low Rank Approximation"

Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David Woodruff

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

[53]

"Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS"

Karl Bringmann, Bhaskar Ray Chaudhury

FSTTCS'18: Proc. of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science

[52]

"Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth"

Karl Bringmann, Thore Husfeldt, Måns Magnusson

IPEC'18: Proc. of the 13th International Symposium on Parameterized and Exact Computation

Invited to Algorithmica special issue

[51]

"Tighter Connections Between Formula-SAT and Shaving Logs"

Amir Abboud, Karl Bringmann

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

[50]

"More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture"

Amir Abboud, Karl Bringmann, Holger Dell, Jesper Nederlof

STOC'18: Proc. of the 50th ACM Symposium on the Theory of Computing

[49]

"Fast Fencing"

Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, Mikkel Thorup

STOC'18: Proc. of the 50th ACM Symposium on the Theory of Computing

[48]

"Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can)"

Karl Bringmann, Paweł Gawrychowski, Shay Mozes, Oren Weimann

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

[47]

"Multivariate Fine-Grained Complexity of Longest Common Subsequence"

Karl Bringmann, Marvin Künnemann

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

[46]

"Approximation Algorithms for l_0-Low Rank Approximation"

Karl Bringmann, Pavel Kolev, David Woodruff

NIPS'17: Proc. of the 31st Annual Conference on Neural Information Processing Systems

[45]

"A fast implementation of near neighbors queries for Fréchet distance (GIS Cup)"

Julian Baldus, Karl Bringmann

SIGSPATIAL'17: Proc. of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

Winner of ACM SIGSPATIAL Cup 2017

[44]

"Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve"

Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann

FOCS'17: Proc. of the 58th Annual IEEE Symposium on Foundations of Computer Science

[43]

"A Dichotomy for Regular Expression Membership Testing"

Karl Bringmann, Allan Grønlund, Kasper Green Larsen

FOCS'17: Proc. of the 58th Annual IEEE Symposium on Foundations of Computer Science

[42]

"A Note on Hardness of Diameter Approximation" (Brief Announcement)

Karl Bringmann, Sebastian Krinninger

DISC'17: Proc. of the 31st International Symposium on Distributed Computing

[41]

"Sampling Geometric Inhomogeneous Random Graphs in Linear Time"

Karl Bringmann, Ralph Keusch, Johannes Lengler

ESA'17: Proc. of the 25th Annual European Symposium on Algorithms

[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 57th Annual IEEE Symposium on Foundations of Computer Science

Invited to HALG'17 and to SICOMP special issue

[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 56th 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

Invited to IJCGA special issue

[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

Invited to CGTA special issue

[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

[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

[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 26th Annual Symposium on Computational Geometry

Invited to CGTA special issue

[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


[32]

"A Linear-Time n0.4-Approximation for Longest Common Subsequence"

Karl Bringmann, Vincent Cohen-Addad, Debarati Das

ACM Transactions on Algorithms, 2023

[31]

"Scheduling lower bounds via AND subset sum"

Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay

Journal of Computer and System Sciences, 2022

[30]

"Faster Minimization of Tardy Processing Time on a Single Machine"

Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay, Philip Wellnitz

Algorithmica, 2022

[29]

"Greedy Routing and the Algorithmic Small-world Phenomenon"

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

Journal of Computer and System Sciences, 2022

[28]

"SETH-based Lower Bounds for Subset Sum and Bicriteria Path"

Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay

ACM Transactions on Algorithms, 2022

Special issue of SODA'19

[27]

"Polyline Simplification has Cubic Complexity"

Karl Bringmann, Bhaskar Ray Chaudhury

Journal of Computational Geometry, 2021

Special issue of SoCG'19

[26]

"Discrete Fréchet Distance under Translation: Conditional Hardness and an Improved Algorithm"

Karl Bringmann, Marvin Künnemann, André Nusser

ACM Transactions on Algorithms, 2021

[25]

"Multivariate Analysis of Orthogonal Range Searching and Graph Distances"

Karl Bringmann, Thore Husfeldt, Måns Magnusson

Algorithmica, 2020

Special issue of IPEC'18

[24]

"Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can)"

Karl Bringmann, Pawel Gawrychowski, Shay Mozes, Oren Weimann

ACM Transactions on Algorithms, 2020

[23]

"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

SIAM Journal on Computing, 2019

Special issue of FOCS'16

[22]

"Geometric Inhomogeneous Random Graphs"

Karl Bringmann, Ralph Keusch, Johannes Lengler

Theoretical Computer Science, 2019

[21]

"On Algebraic Branching Programs of Small Width"

Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam

Journal of the ACM, 2018

[20]

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

Karl Bringmann, Tobias Friedrich, Anton Krohmer

Algorithmica, 2018

[19]

"A Note on Hardness of Diameter Approximation"

Karl Bringmann, Sebastian Krinninger

Information Processing Letters, 2018

[18]

"Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds"

Karl Bringmann, Marvin Künnemann

International Journal of Computational Geometry and Applications, 2017

Special Issue of ISAAC'15

[17]

"Efficient Sampling Methods for Discrete Distributions"

Karl Bringmann, Konstantinos Panagiotou

Algorithmica, 2017

[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 of 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

Special Issue of SoCG'10

[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