8 papers
Robustifying Sparse Matrix Multiplication
Karl Bringmann, Nick Fischer, Vasileios Nakos
In the seminal sparse matrix multiplication problem the goal is to compute the product of two matrices when the matrices are sparse, i.e., when the number of nonzeros…
Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
Karl Bringmann, Anita Dürr, Karol WÄgrzycki
Bin Packing with bins is a fundamental optimisation problem in which we are given a set of integers and a capacity and the goal is to partition the set into subsets…
Dynamic and Streaming Algorithms for Union Volume Estimation
Sujoy Bhore, Karl Bringmann, Timothy M. Chan +1
The union volume estimation problem asks to -approximate the volume of the union of given objects . In their seminal wor…
Polyline Simplification has Cubic Complexity
Karl Bringmann, Bhaskar Ray Chaudhury
In the classic polyline simplification problem we want to replace a given polygonal curve , consisting of vertices, by a subsequence of vertices from such that…
Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries
Karl Bringmann, Nofar Carmeli
We study the enumeration of answers to Unions of Conjunctive Queries (UCQs) with optimal time guarantees. More precisely, we wish to identify the queries that can be solved with li…
Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
Karl Bringmann, Kasper Green Larsen, André Nusser +2
Union volume estimation is a classical algorithmic problem. Given a family of objects , we want to approximate the volume of their union. In…