K. Bringmann

activity

20082026

most citedApproximating the volume of unions and intersections of high-dimensional geometric objects

96 citations · 442 across the 64 of their papers we have counts for

collaborators

Showing 2024Show all

4 papers · 1 filter

cs.DS2024

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 $n$ integers $X$ and a target $t$ , i…

cs.CG2024

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 $O_{1}, \dots, O_{n} \subseteq R^{d}$ , we want to approximate the volume of their union. In…

cs.DS2024

A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends

Karl Bringmann, Egor Gorbachev

In an $m$ -edge host graph $G$ , all triangles can be listed in time $O (m^{1.5})$ [Itai, Rodeh '78], and all $k$ -cycles can be listed in time $O (m^{2 - 1/ ⌈ k /2 ⌉} + t)$ whe…

cs.DS2024

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 $O (n + t p_{m a x})$ , where $n$ is the number of items, $t$ is the knap…