Given a budget and an undirected graph with a cost and a profit function on the edges, the Edge Orienteering Problem asks for a closed walk in the graph that collects the most profit while the sum of costs does not exceed the budget. While the profit is collected only once per edge, the cost is incurred each time the edge is traversed by the walk. In this paper, we present a ( 4 + ε ) -approximation algorithm for the Edge Orienteering Problem.

Given a convex region P and a set of irregular polygons with associated profits, the Maximum Polygon Packing Problem seeks a non-overlapping packing of a subset of the polygons (without rotations) into P maximizing the profit of the packed polygons. Depending on the size of an instance, we use different algorithmic solutions: integer linear programs for small instances, genetic algorithms for medium-sized instances and a best-fit approach for large instances. For packing rectilinear polygons we provide a dedicated best-fit algorithm.

Datasets containing human or animal movement are often sparse, for instance, due to poor GPS reception during recording or because of considerations concerning the battery life of the tracking device. Still, it may be desirable to estimate which walk the observed subject could have taken. A practical solution to this problem is to interpolate between measurements using random walk models. It is however intrinsically difficult to generate walks according to such models that also match the measurements, which in turn makes it difficult to compute metrics like visit probabilities.

The touring problem aims to find an "interesting" (round) trip of a given length. Here, what is considered interesting depends on the type of the desired route, e.g., a user may be looking for an off-road cycling trip or fast running route.

Exactly 20 years ago at MFCS, Demaine posed the open problem whether the game of Dots & Boxes is PSPACE-complete. Dots & Boxes has been studied extensively, with for instance a chapter in Berlekamp et al. Winning Ways for Your Mathematical Plays, a whole book on the game The Dots and Boxes Game: Sophisticated Child’s Play by Berlekamp, and numerous articles in the Games of No Chance series. While known to be NP-hard, the question of its complexity remained open. We resolve this question, proving that the game is PSPACE-complete by a reduction from a game played on propositional formulas.

We present a new game, Dots & Polygons, played on a planar point set. We prove that its NP-hard and discuss strategies for the case when the point set is in convex position.