49 citations · 107 across the 12 of their papers we have counts for
12 papers · 1 filter
An Improved Algorithm For Online Min-Sum Set Cover
Marcin Bienkowski, Marcin Mucha
We study a fundamental model of online preference aggregation, where an algorithm maintains an ordered list of elements. An input is a stream of preferred sets $R_1, R_2, \dots…
Matroid-Based TSP Rounding for Half-Integral Solutions
Anupam Gupta, Euiwoong Lee, Jason Li +3
We show how to round any half-integral solution to the subtour-elimination relaxation for the TSP, while losing a less-than-1.5 factor. Such a rounding algorithm was recently given…
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…
Online Facility Location with Deletions
Marek Cygan, Artur Czumaj, Marcin Mucha +1
In this paper we study three previously unstudied variants of the online Facility Location problem, considering an intrinsic scenario when the clients and facilities are not only a…
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…
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…