2 citations · 3 across the 9 of their papers we have counts for
11 papers
Improving Online Bin Covering with Little Advice
Andrej Brodnik, Bengt J. Nilsson, Gordana Vujović
The online bin covering problem is: given an input sequence of items find a placement of the items in the maximum number of bins such that the sum of the items' sizes in each bin i…
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…
Guarding Polyominoes Under -Hop Visibility
Omrit Filtser, Erik Krohn, Bengt J. Nilsson +2
We study the Art Gallery Problem under -hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest p…
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…
Online Two-Dimensional Vector Packing with Advice
Bengt J. Nilsson, Gordana Vujovic
We consider the online two-dimensional vector packing problem, showing a lower bound of on the competitive ratio of any {\sc AnyFit} strategy for the problem. We provide str…
-Transmitter Watchman Routes
Bengt J. Nilsson, Christiane Schmidt
We consider the watchman route problem for a -transmitter watchman: standing at point in a polygon , the watchman can see if intersects 's bou…
Shortest Watchman Tours in Simple Polygons under Rotated Monotone Visibility
Bengt J. Nilsson, David Orden, Leonidas Palios +2
We present an time algorithm for computing and maintaining a minimum length shortest watchman tour that sees a simple polygon under monotone visibility in direction , w…
Local Routing in Sparse and Lightweight Geometric Graphs
Vikrant Ashvinkumar, Joachim Gudmundsson, Christos Levcopoulos +2
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 -competitive online r…
Online Clique Clustering
Marek Chrobak, Christoph Durr, Aleksander Fabijan +1
Clique clustering is the problem of partitioning the vertices of a graph into disjoint clusters, where each cluster forms a clique in the graph, while optimizing some objective fun…