33 citations · 104 across the 16 of their papers we have counts for
20 papers
A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints
Jesper Nederlof, Céline M. F. Swennenhuis, Karol Węgrzycki
In a classical scheduling problem, we are given a set of jobs of unit length along with precedence constraints, and the goal is to find a schedule of these jobs on identica…
A polynomial-time -approximation algorithm for maximum independent set of connected subgraphs in a planar graph
Jana Cslovjecsek, Michał Pilipczuk, Karol Węgrzycki
In the Maximum Independent Set of Objects problem, we are given an -vertex planar graph and a family of objects, where each object is a connected subgraph…
Separator Theorem and Algorithms for Planar Hyperbolic Graphs
Sándor Kisfaludi-Bak, Jana Masaříková, Erik Jan van Leeuwen +2
The hyperbolicity of a graph, informally, measures how close a graph is (metrically) to a tree. Hence, it is intuitively similar to treewidth, but the measures are formally incompa…
Makespan Scheduling of Unit Jobs with Precedence Constraints in time
Jesper Nederlof, Céline M. F. Swennenhuis, Karol Węgrzycki
In a classical scheduling problem, we are given a set of jobs of unit length along with precedence constraints and the goal is to find a schedule of these jobs on identical…
Independence number of intersection graphs of axis-parallel segments
Marco Caoduro, Jana Cslovjecsek, Michał Pilipczuk +1
We prove that for any triangle-free intersection graph of axis-parallel segments in the plane, the independence number of this graph is at least . W…
Bounding generalized coloring numbers of planar graphs using coin models
Jesper Nederlof, Michał Pilipczuk, Karol Węgrzycki
We study Koebe orderings of planar graphs: vertex orderings obtained by modelling the graph as the intersection graph of pairwise internally-disjoint discs in the plane, and orderi…
Isolation schemes for problems on decomposable graphs
Jesper Nederlof, Michał Pilipczuk, Céline M. F. Swennenhuis +1
The Isolation Lemma of Mulmuley, Vazirani and Vazirani [Combinatorica'87] provides a self-reduction scheme that allows one to assume that a given instance of a problem has a unique…
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…
Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max
Karl Bringmann, Marvin Künnemann, Karol Węgrzycki
Zwick's -approximation algorithm for the All Pairs Shortest Path (APSP) problem runs in time , where i…
Equal-Subset-Sum Faster Than the Meet-in-the-Middle
Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz +1
In the Equal-Subset-Sum problem, we are given a set of integers and the problem is to decide if there exist two disjoint nonempty subsets , whose elements…
A Subquadratic Approximation Scheme for Partition
Marcin Mucha, Karol Węgrzycki, Michał Włodarczyk
The subject of this paper is the time complexity of approximating Knapsack, Subset Sum, Partition, and some other related problems. The main result is an $\widetilde{O}(n+1/\vareps…
Why Do Cascade Sizes Follow a Power-Law?
Karol Węgrzycki, Piotr Sankowski, Andrzej Pacuk +1
We introduce random directed acyclic graph and use it to model the information diffusion network. Subsequently, we analyze the cascade generation model (CGM) introduced by Leskovec…
On problems equivalent to (min,+)-convolution
Marek Cygan, Marcin Mucha, Karol Węgrzycki +1
In recent years, significant progress has been made in explaining the apparent hardness of improving upon the naive solutions for many fundamental polynomially solvable problems. T…
RecSys Challenge 2016: job recommendations based on preselection of offers and gradient boosting
Andrzej Pacuk, Piotr Sankowski, Karol Węgrzycki +2
We present the Mim-Solution's approach to the RecSys Challenge 2016, which ranked 2nd. The goal of the competition was to prepare job recommendations for the users of the website X…
There is Something Beyond the Twitter Network
Andrzej Pacuk, Piotr Sankowski, Karol Wegrzycki +1
How information spreads through a social network? Can we assume, that the information is spread only through a given social network graph? What is the correct way to compare the mo…
Locality-Sensitive Hashing without False Negatives for l_p
Andrzej Pacuk, Piotr Sankowski, Karol Wegrzycki +1
In this paper, we show a construction of locality-sensitive hash functions without false negatives, i.e., which ensure collision for every pair of points within a given radius …
Improved Distance Queries and Cycle Counting by Frobenius Normal Form
Piotr Sankowski, Karol Węgrzycki
Consider an unweighted, directed graph with the diameter . In this paper, we introduce the framework for counting cycles and walks of given length in matrix multiplication t…