4 papers
Online Bin Covering with Exact Parameter Advice
Andrej Brodnik, Bengt J. Nilsson, Gordana Vujovic
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…
Approximation Algorithms for the Two-Watchman Route in a Simple Polygon
Bengt J. Nilsson, Eli Packer
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…
APX-Hardness of the Minimum Vision Points Problem
Mayank Chaturvedi, Bengt J. Nilsson
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 vi…
Opposing Half Guards
Erik Krohn, Bengt J. Nilsson, Christiane Schmidt
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…