research
∙
05/02/2023
Coverability in VASS Revisited: Improving Rackoff's Bound to Obtain Conditional Optimality
Seminal results establish that the coverability problem for Vector Addit...
share
research
∙
12/03/2022
Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments
In the Maximum Weight Independent Set of Rectangles problem (MWISR) we a...
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...
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
∙
05/01/2022
Dynamic data structures for parameterized string problems
We revisit classic string problems considered in the area of parameteriz...
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
∙
05/09/2021
Knapsack and Subset Sum with Small Items
Knapsack and Subset Sum are fundamental NP-hard problems in combinatoria...
research
∙
05/04/2021
Isolation schemes for problems on decomposable graphs
The Isolation Lemma of Mulmuley, Vazirani and Vazirani [Combinatorica'87...
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
Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors
We present an 𝒪^⋆(2^0.5n) time and 𝒪^⋆(2^0.249999n) space randomized alg...
research
∙
07/16/2020
A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
In the Bin Packing problem one is given n items with weights w_1,…,w_n a...
research
∙
02/11/2020
Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
For many algorithmic problems on graphs of treewidth t, a standard dynam...
research
∙
07/25/2019
Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max
Zwick's (1+ε)-approximation algorithm for the All Pairs Shortest Path (A...
research
∙
05/07/2019
Equal-Subset-Sum Faster Than the Meet-in-the-Middle
In the Equal-Subset-Sum problem, we are given a set S of n integers and ...
research
∙
04/06/2018
Subquadratic Approximation Scheme for Partition
The subject of this paper is the time complexity of approximating Knapsa...
research
∙
12/03/2016