research
∙
09/19/2022
Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours
In this paper, we study problems of connecting classes of points via non...
share
research
∙
09/04/2022
Computing Generalized Convolutions Faster Than Brute Force
In this paper, we consider a general notion of convolution. Let D be a f...
research
∙
08/04/2022
Makespan Scheduling of Unit Jobs with Precedence Constraints in O(1.995^n) time
In a classical scheduling problem, we are given a set of n jobs of unit ...
research
∙
05/30/2022
Independence number of intersection graphs of axis-parallel segments
We prove that for any triangle-free intersection graph of n axis-paralle...
research
∙
01/23/2022
Bounding generalized coloring numbers of planar graphs using coin models
We study Koebe orderings of planar graphs: vertex orderings obtained by ...
research
∙
11/07/2020
A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
We revisit the classic task of finding the shortest tour of n points in ...
research
∙
10/16/2020
