Locating objects in physical environments can be an exhausting and frustrating task, particularly when these objects are out of the user's view or occluded by other objects. With recent advances in Augmented Reality (AR), these environments can be augmented to visualize objects for which the user searches. However, it is currently unclear which visualization strategy can best support users in locating these objects. In this paper, we compare a printed map to three different AR visualization strategies: (1) in-view visualization, (2) out-of-view visualization, and (3) the combination of in-view and out-of-view visualizations. Our results show that in-view visualization reduces error rates for object selection accuracy, while additional out-of-view object visualization improves users' search time performance. However, combining in-view and out-of-view visualizations leads to visual clutter, which distracts users.

We study the two-dimensional bin packing problem: Given a list of n rectangles the objective is to find a feasible, i.e. axis-parallel and non-overlapping, packing of all rectangles into the minimum number of unit sized squares, also called bins. Our problem consists of two versions; in the first version it is not allowed to rotate the rectangles while in the other it is allowed to rotate the rectangles by 90°, i.e. to exchange the widths and the heights. Two-dimensional bin packing is a generalization of its one-dimensional counterpart and is therefore strongly -hard. Furthermore Bansal et al. [2] showed that even an is ruled out for this problem, unless . This lower bound of asymptotic approximability was improved by Chlebík & Chlebíková [4] to values 1 + 1/3792 and 1 + 1/2196 for the version with and without rotations, respectively. On the positive side there is an asymptotic 1.69‥ approximation by Caprara [3] without rotations and an asymptotic 1.52… approximation by Bansal et al. [1] for both versions. We give a new asymptotic upper bound for both versions of our problem: For any fixed ε and any instance that fits optimally into OPT bins, our algorithm computes a packing into (1.5 + ε) · OPT+ 69 bins with polynomial running time in the input length. In our new technique we consider an optimal packing of the rectangles into the bins. We cut a small vertical or horizontal strip out of each bin and move the intersecting rectangles into additional bins. This enables us to either round the widths of all wide rectangles, or the heights of all long rectangles in this bin. After this step we round the other, unrounded side of these rectangles and we achieve a solution with a simple structure and only few types of rectangles. Our algorithm initially rounds the instance and computes a solution that nearly matches the modified optimal solution.

We study two closely related problems in nonpreemptive scheduling of jobs on identical parallel machines. In these two settings there are either fixed jobs or nonavailability intervals during which the machines are not available; in both cases, the objective is to minimize the makespan. Both formulations have different applications, for example, in turnaround scheduling or overlay computing. For both problems we contribute approximation algorithms with an improved ratio of 3/2. For scheduling with fixed jobs, a lower bound of 3/2 on the approximation ratio has been obtained by Scharbrodt et al. [1999]; for scheduling with nonavailability we provide the same lower bound. We use dual approximation, creation of a gap structure, and a PTAS for the multiple subset sum problem, combined with a postprocessing step to assign large jobs.