Karol Węgrzycki | DeepAI

DeepAI AI Chat

Featured Co-authors

Michał Pilipczuk
62 publications
Karl Bringmann
49 publications
Dániel Marx
44 publications
Jesper Nederlof
25 publications
Lars Rohwedder
23 publications
Adam Polak
21 publications
Sándor Kisfaludi-Bak
20 publications
MIchal Wlodarczyk
19 publications
Marvin Künnemann
19 publications
Ariel Kulik
18 publications
Francois Dross
14 publications

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

0 Marvin Künnemann, et al. ∙

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

0 Jana Cslovjecsek, et al. ∙

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

0 Francois Dross, et al. ∙

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

0 Barış Can Esmer, et al. ∙

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

0 Jesper Nederlof, et al. ∙

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

0 Marco Caoduro, et al. ∙

∙ 05/01/2022

Dynamic data structures for parameterized string problems

We revisit classic string problems considered in the area of parameteriz...

0 Jedrzej Olkowski, et al. ∙

∙ 01/23/2022

Bounding generalized coloring numbers of planar graphs using coin models

We study Koebe orderings of planar graphs: vertex orderings obtained by ...

0 Jesper Nederlof, et al. ∙

∙ 05/09/2021

Knapsack and Subset Sum with Small Items

Knapsack and Subset Sum are fundamental NP-hard problems in combinatoria...

0 Adam Polak, et al. ∙

∙ 05/04/2021

Isolation schemes for problems on decomposable graphs

The Isolation Lemma of Mulmuley, Vazirani and Vazirani [Combinatorica'87...

0 Jesper Nederlof, et al. ∙

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

0 Sándor Kisfaludi-Bak, et al. ∙

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

0 Jesper Nederlof, et al. ∙

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

0 Jesper Nederlof, et al. ∙

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

0 Jesper Nederlof, et al. ∙

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

0 Karl Bringmann, et al. ∙

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

0 Marcin Mucha, et al. ∙

∙ 04/06/2018

Subquadratic Approximation Scheme for Partition

The subject of this paper is the time complexity of approximating Knapsa...

0 Marcin Mucha, et al. ∙

∙ 12/03/2016

RecSys Challenge 2016: job recommendations based on preselection of offers and gradient boosting

We present the Mim-Solution's approach to the RecSys Challenge 2016, whi...

0 Andrzej Pacuk, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world