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 2024 · cs.DSShow all

3 papers · 2 filters

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.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…