Zobrazeno 1 - 10
of 69
pro vyhledávání: '"ADAMASZEK, ANNA"'
Publikováno v:
Journal of the ACM. Jan2022, Vol. 69 Issue 1, p1-70. 70p.
Autor:
Abrahamsen, Mikkel, Adamaszek, Anna, Bringmann, Karl, Cohen-Addad, Vincent, Mehr, Mehran, Rotenberg, Eva, Roytman, Alan, Thorup, Mikkel
We consider very natural "fence enclosure" problems studied by Capoyleas, Rote, and Woeginger and Arkin, Khuller, and Mitchell in the early 90s. Given a set $S$ of $n$ points in the plane, we aim at finding a set of closed curves such that (1) each p
Externí odkaz:
http://arxiv.org/abs/1804.00101
We prove that the art gallery problem is equivalent under polynomial time reductions to deciding whether a system of polynomial equations over the real numbers has a solution. The art gallery problem is a classical problem in computational geometry.
Externí odkaz:
http://arxiv.org/abs/1704.06969
We present an $(1+\varepsilon)$-approximation algorithm with quasi-polynomial running time for computing the maximum weight independent set of polygons out of a given set of polygons in the plane (specifically, the running time is $n^{O( \mathrm{poly
Externí odkaz:
http://arxiv.org/abs/1703.04758
In this paper we study the art gallery problem, which is one of the fundamental problems in computational geometry. The objective is to place a minimum number of guards inside a simple polygon such that the guards together can see the whole polygon.
Externí odkaz:
http://arxiv.org/abs/1701.05475
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. The problem has multiple applications, e.g. in scheduling and stock-
Externí odkaz:
http://arxiv.org/abs/1610.07766
Publikováno v:
Random Structures and Algorithms Volume 56 (4), 2020, pages 948-987
The Graceful Tree Conjecture of Rosa from 1967 asserts that the vertices of each tree T of order n can be injectively labelled by using the numbers {1,2,...,n} in such a way that the absolute differences induced on the edges are pairwise distinct. We
Externí odkaz:
http://arxiv.org/abs/1608.01577
Autor:
Adamaszek, Anna
In this thesis we study approximation algorithms for optimization problems, which is one of the core areas of modern theoretical computer science. We focus on two areas of approximation. First we consider geometric problems, and we present approximat
Externí odkaz:
http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.560419
Autor:
ADAMASZEK, ANNA1 (AUTHOR) anna@mpi-inf.mpg.de, HAR-PELED, SARIEL2 (AUTHOR) sariel@illinois.edu, WIESE, ANDREAS3 (AUTHOR) awiese@dii.uchile.cl
Publikováno v:
Journal of the ACM. Aug2019, Vol. 66 Issue 4, p1-40. 40p.
Autor:
Adamaszek, Anna, Popa, Alexandru
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 from an undirected vertex-colored graph $G$ such that in the resulting g
Externí odkaz:
http://arxiv.org/abs/1311.1298