17 citations · 29 across the 8 of their papers we have counts for
4 papers · 1 filter
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 points in -dimensional Euclidean space, for any fixed constant . We determine the optimal dependence on…
Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors
Jesper Nederlof, Karol Węgrzycki
We present an time and space randomized algorithm for solving worst-case Subset Sum instances with integers. Th…
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 items with weights and bins with capacities . The goal is to find a partition of the items into set…
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 , a standard dynamic programming approach gives an algorithm with time and space complexity $2^{\mathcal{O}(t)}\cdot n^{\mat…