Motivated by applications for robust guarding, we consider a variant of the multiple-watchmen problem that ensures that every point within a polygon P is seen from more than one direction: we search for two routes W₁,W₂, such that every point p ∈ P is contained in a segment w₁w₂ ⊆ P such that w₁ ∈ W₁ and w₂ ∈ W₂. We call such routes segment watchman routes. We show that finding the two routes that are optimal with respect to the min-max criterion is weakly NP-hard even in simple polygons, and that finding the routes that are optimal with respect to the min-sum criterion is NP-hard in polygons with holes. Moreover, we present sufficient conditions for routes to be segment watchman routes, and provide a polynomial-time 2-approximation under both the min-max criterion and the min-sum criterion, both in simple polygons. Finally, we show how to generalize our results for k watchmen.

Abstract 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 has length at most k. In this paper, we show that the VC dimension of this problem is 3 in simple polyominoes, and 4 in polyominoes with holes. Furthermore, we provide a reduction from Planar Monotone 3Sat, thereby showing that the problem is -complete even in thin polyominoes (i.e., polyominoes that do not a contain a $$2\times 2$$ 2 × 2 block of cells). Complementarily, we present a linear-time 4-approximation algorithm for simple 2-thin polyominoes (which do not contain a $$3\times 3$$ 3 × 3 block of cells) for all $$k\in {\mathbb {N}}$$ k ∈ N .

Abstract 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, where we want the tours where the longest of them has smallest length, and the minsum measure, where we want the tours for which the sum of their lengths is the smallest. It is known that computing a minmax two-watchman route is NP-hard for simple rectilinear polygons and thus also for simple polygons. Also, any c-approximation algorithm for the minmax two-watchman route is automatically a 2c-approximation algorithm for the minsum two-watchman route. We exhibit two constant factor approximation algorithms for computing minmax two-watchman routes in simple polygons with approximation factors 5.969 and 11.939, having running times $$O(n^8)$$ O ( n 8 ) and $$O(n^4)$$ O ( n 4 ) respectively, where n is the number of vertices of the polygon. We also use the same techniques to obtain a 6.922-approximation for the fixed two-watchman route problem running in $$O(n^2)$$ O ( n 2 ) time, i.e., when two starting points of the two tours are given as input.

Abstract 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 triangulation for which Bose and Morin (SIAM J Comput 33(4):937–951, 2004) showed that there exists an online routing algorithm that is O(1)-competitive. However, a Delaunay triangulation can have $$\varOmega (n)$$ Ω ( n ) vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree. We show a simple construction, given a set V of n points in the Euclidean plane, of a planar geometric graph on V that has small weight (within a constant factor of the weight of a minimum spanning tree on V), constant degree, and that admits a local routing strategy that is O(1)-competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an O(1)-competitive routing strategy.

Given a set S of regions with piece-wise linear boundary and a positive angle α < 90°, we consider the problem of computing the locations and orientations of the minimum number of α-floodlights positioned at points in S which suffice to illuminate the entire x-axis. We show that the problem can be solved in O(n log n) time and O(n) space, where n is the number of vertices of the set S.

Abstract 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 function. In online clustering, the input graph is given one vertex at a time, and any vertices that have previously been clustered together are not allowed to be separated. The goal is to maintain a clustering with an objective value close to the optimal solution. For the variant where we want to maximize the number of edges in the clusters, we propose an online algorithm based on the doubling technique. It has an asymptotic competitive ratio at most 15.646 and a strict competitive ratio at most 22.641. We also show that no deterministic algorithm can have an asymptotic competitive ratio better than 6. For the variant where we want to minimize the number of edges between clusters, we show that the deterministic competitive ratio of the problem is $$n-\omega (1)$$ n-ω(1) , where n is the number of vertices in the graph.

This work presents an extension of Thompson Sampling bandit policy for orchestrating the collection of base recommendation algorithms for e-commerce. We focus on the problem of item-to-item recommendations, for which multiple behavioral and attribute-based predictors are provided to an ensemble learner. In addition, we detail the construction of a personalized predictor based on k -Nearest Neighbors ( k NN), with temporal decay capabilities and event weighting. We show how to adapt Thompson Sampling to realistic situations when neither action availability nor reward stationarity is guaranteed. Furthermore, we investigate the effects of priming the sampler with pre-set parameters of reward probability distributions by utilizing the product catalog and/or event history, when such information is available. We report our experimental results based on the analysis of three real-world e-commerce datasets.

This work presents an extension of Thompson Sampling bandit policy for orchestrating the collection of base recommendation algorithms for e-commerce. We focus on the problem of item-to-item recommendations, for which multiple behavioral and attribute-based predictors are provided to an ensemble learner. We show how to adapt Thompson Sampling to realistic situations when neither action availability nor reward stationarity is guaranteed. Furthermore, we investigate the effects of priming the sampler with pre-set parameters of reward probability distributions by utilizing the product catalog and/or event history, when such information is available. We report our experimental results based on the analysis of three real-world e-commerce datasets.

We study bandit algorithms for e-commerce recommender systems. The question we pose is whether it is necessary to consider reinforcement learning effects in recommender systems. A key reason to introduce a recommender system for a product page on an e-commerce site is to increase the order value by improving the chance of making an upsale. If the recommender system merely predicts the next purchase, there might be no positive effect at all on the order value, since the recommender system predicts sales that would have happened independent of the recommender system. What we really are looking for are the false negatives, i.e., purchases that happen as a consequence of the recommender system. These purchases entail the entire uplift and should be present as reinforcement learning effects. This effect cannot be displayed in a simulation of the site, since there are no reinforcement learning effects present in a simulation. The attribution model must capture the uplift to guarantee an increased order value. However, such an attribution model is not practical, due to data sparsity. Given this starting point, we study some standard attribution models for e-commerce recommender systems, and describe how these fare when applied in a reinforcement learning algorithm, both in a simulation and on live sites.

We experiment on two real e-commerce datasets and survey more than 30 popular e-commerce platforms to reveal what methods work best for product recommendations in industrial settings. Despite recent academic advances in the field, we observe that simple methods such as best-seller lists dominate deployed recommendation engines in e-commerce. We find our empirical findings to be well-aligned with those of the survey, where in both cases simple personalized recommenders achieve higher ranking than more advanced techniques. We also compare the traditional random evaluation protocol to our proposed chronological sampling method, which can be used for determining the optimal time-span of the training history for optimizing the performance of algorithms. This performance is also affected by a proper hyperparameter tuning, for which we propose golden section search as a fast alternative to other optimization techniques.

We study the problem of optimizing recommendation systems for e-commerce sites. We consider in particular a combinatorial solution to this optimization based on the well known Maximum Coverage problem that asks for the k sets (products) that cover the most elements from a ground set (consumers). This formulation provides an abstract model for what k products should be recommended to maximize the probability of consumer purchase. Unfortunately, Maximum Coverage is NP-complete but an efficient approximation algorithm exists based on the Greedy methodology.

In this paper, a data structure is given for higher dimensional shortest path queries.For a set of n axisparallel boxes in d-space and a fixed target, it is possible with this sttucturc to find a shortest rectilinear path from any point in d-space to this target, where the path does not cross any box.Alternatively, it is possible to find the length of the path.The metric considered is a generalization of the L1 -metric and the link metric, where the length of a path is its L1-length plus some (fixed) constant times the number of turns on the path.The data structure uses O ((n log n)d-l ) space to store, and a query takes O (logd-1 n) time (plus the output size if the path must be reported).As a byproduct a solution to the single shot problem is obtained; the shortest path between two given points can be computed in time O (nd log n).