Jesper Nederlof

activity

20112026

most citedOn Problems as Hard as CNFSAT

121 citations · 181 across the 38 of their papers we have counts for

collaborators

Showing 2020Show all

4 papers · 1 filter

cs.CG2020

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP

Sándor Kisfaludi-Bak, Jesper Nederlof, Karol Węgrzycki

We revisit the classic task of finding the shortest tour of $n$ points in $d$ -dimensional Euclidean space, for any fixed constant $d \geq 2$ . We determine the optimal dependence on…

cs.DS2020

Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors

Jesper Nederlof, Karol Węgrzycki

We present an $O^{⋆} (2^{0.5 n})$ time and $O^{⋆} (2^{0.249999 n})$ space randomized algorithm for solving worst-case Subset Sum instances with $n$ integers. Th…

cs.DS2020★ 3 cited

A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics

Jesper Nederlof, Jakub Pawlewicz, Céline M. F. Swennenhuis +1

In the Bin Packing problem one is given $n$ items with weights $w_{1}, \dots, w_{n}$ and $m$ bins with capacities $c_{1}, \dots, c_{m}$ . The goal is to find a partition of the items into set…

cs.DS2020

Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space

Jesper Nederlof, Michał Pilipczuk, Céline M. F. Swennenhuis +1

For many algorithmic problems on graphs of treewidth $t$ , a standard dynamic programming approach gives an algorithm with time and space complexity $2^{\mathcal{O}(t)}\cdot n^{\mat…