49 citations · 107 across the 12 of their papers we have counts for
14 papers
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…
Improving Ads-Profitability Using Traffic-Fingerprints
Adam Gabriel Dobrakowski, Andrzej Pacuk, Piotr Sankowski +2
This paper introduces the concept of traffic-fingerprints, i.e., normalized 24-dimensional vectors representing a distribution of daily traffic on a web page. Using k-means cluster…
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…