15 citations · 45 across the 12 of their papers we have counts for
6 papers · 1 filter
Hardness of approximation for strip packing
Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk +1
Strip packing is a classical packing problem, where the goal is to pack a set of rectangular objects into a strip of a given width, while minimizing the total height of the packing…
Algorithmic and Hardness Results for the Colorful Components Problems
Anna Adamaszek, Alexandru Popa
In this paper we investigate the colorful components framework, motivated by applications emerging from comparative genomics. The general goal is to remove a collection of edges fr…
A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices
Anna Adamaszek, Andreas Wiese
The Maximum Weight Independent Set of Polygons problem is a fundamental problem in computational geometry. Given a set of weighted polygons in the 2-dimensional plane, the goal is…
Approximation Schemes for Maximum Weight Independent Set of Rectangles
Anna Adamaszek, Andreas Wiese
In the Maximum Weight Independent Set of Rectangles (MWISR) problem we are given a set of n axis-parallel rectangles in the 2D-plane, and the goal is to select a maximum weight sub…
Large-girth roots of graphs
Anna Adamaszek, Michal Adamaszek
We study the problem of recognizing graph powers and computing roots of graphs. We provide a polynomial time recognition algorithm for r-th powers of graphs of girth at least 2r+3,…
PTAS for k-tour cover problem on the plane for moderately large values of k
Anna Adamaszek, Artur Czumaj, Andrzej Lingas
Let P be a set of n points in the Euclidean plane and let O be the origin point in the plane. In the k-tour cover problem (called frequently the capacitated vehicle routing problem…