1 citations · 1 across the 3 of their papers we have counts for
5 papers · 1 filter
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…
Near-Optimal Directed Low-Diameter Decompositions
Karl Bringmann, Nick Fischer, Bernhard Haeupler +1
Low Diameter Decompositions (LDDs) are invaluable tools in the design of combinatorial graph algorithms. While historically they have been applied mainly to undirected graphs, in t…
Beating Bellman's Algorithm for Subset Sum
Karl Bringmann, Nick Fischer, Vasileios Nakos
Bellman's algorithm for Subset Sum is one of the earliest and simplest examples of dynamic programming, dating back to 1957. For a given set of integers and a target , i…
Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
Karl Bringmann, Anita Dürr, Adam Polak
We present a pseudopolynomial-time algorithm for the Knapsack problem that has running time , where is the number of items, is the knap…