Zobrazeno 1 - 10
of 624
pro vyhledávání: '"Nilsson P. J."'
We show an asymptotic 2/3-competitive strategy for the bin covering problem using O(b+log n) bits of advice, where b is the number of bits used to encode a rational value and n is the length of the input sequence.
Comment: 10 pages, 2 figure, su
Comment: 10 pages, 2 figure, su
Externí odkaz:
http://arxiv.org/abs/2309.13647
Autor:
Nilsson, Bengt J., Packer, Eli
The two-watchman route problem is that of computing a pair of closed tours in an environment so that the two tours together see the whole environment and some length measure on the two tours is minimized. Two standard measures are: the minmax measure
Externí odkaz:
http://arxiv.org/abs/2309.13428
We study the Art Gallery Problem under $k$-hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest path between the respective vertices in the dual graph of the polyomino
Externí odkaz:
http://arxiv.org/abs/2308.00334
Autor:
Chaturvedi, Mayank, Nilsson, Bengt J.
Placing a minimum number of guards on a given watchman route in a polygonal domain is called the {\em minimum vision points problem}. We prove that finding the minimum number of vision points on a shortest watchman route in a simple polygon is APX-Ha
Externí odkaz:
http://arxiv.org/abs/2207.04488
We study the art gallery problem for opposing half guards: guards that can either see to their left or to their right only. We present art gallery theorems, show that the location of half guards in 2-guardable polygons is not restricted to extensions
Externí odkaz:
http://arxiv.org/abs/2207.04474
Autor:
Nilsson, Bengt J., Vujovic, Gordana
We consider the online two-dimensional vector packing problem, showing a lower bound of $11/5$ on the competitive ratio of any {\sc AnyFit} strategy for the problem. We provide strategies with competitive ratio $\max\!\left\{2,6\big/\big(1+3\tan(\pi/
Externí odkaz:
http://arxiv.org/abs/2204.10322
Autor:
Nilsson, Bengt J., Schmidt, Christiane
We consider the watchman route problem for a $k$-transmitter watchman: standing at point $p$ in a polygon $P$, the watchman can see $q\in P$ if $\overline{pq}$ intersects $P$'s boundary at most $k$ times -- $q$ is $k$-visible to $p$. Traveling along
Externí odkaz:
http://arxiv.org/abs/2202.01757
We present an $O(nrG)$ time algorithm for computing and maintaining a minimum length shortest watchman tour that sees a simple polygon under monotone visibility in direction $\theta$, while $\theta$ varies in $[0,180^{\circ})$, obtaining the directio
Externí odkaz:
http://arxiv.org/abs/2007.08368
Autor:
Ashvinkumar, Vikrant, Gudmundsson, Joachim, Levcopoulos, Christos, Nilsson, Bengt J., van Renssen, André
Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no $O(1)$-competitive online routing algorithm exists. A notable exception is the Delaunay triangula
Externí odkaz:
http://arxiv.org/abs/1909.10215
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.