Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Goaoc, Xavier ; Kerber, Michael (Ed.)We consider the following surveillance problem: Given a set P of n sites in a metric space and a set R of k robots with the same maximum speed, compute a patrol schedule of minimum latency for the robots. Here a patrol schedule specifies for each robot an infinite sequence of sites to visit (in the given order) and the latency L of a schedule is the maximum latency of any site, where the latency of a site s is the supremum of the lengths of the time intervals between consecutive visits to s. When k = 1 the problem is equivalent to the travelling salesman problem (TSP) and thus it is NPhard. For k ≥ 2 (which is the version we are interested in) the problem becomes even more challenging; for example, it is not even clear if the decision version of the problem is decidable, in particular in the Euclidean case. We have two main results. We consider cyclic solutions in which the set of sites must be partitioned into 𝓁 groups, for some 𝓁 ≤ k, and each group is assigned a subset of the robots that move along the travelling salesman tour of the group at equal distance from each other. Our first main result is that approximating the optimal latency of the class of cyclic solutions can be reduced to approximating the optimal travelling salesman tour on some input, with only a 1+ε factor loss in the approximation factor and an O((k/ε) ^k) factor loss in the runtime, for any ε > 0. Our second main result shows that an optimal cyclic solution is a 2(11/k)approximation of the overall optimal solution. Note that for k = 2 this implies that an optimal cyclic solution is optimal overall. We conjecture that this is true for k ≥ 3 as well. The results have a number of consequences. For the Euclidean version of the problem, for instance, combining our results with known results on Euclidean TSP, yields a PTAS for approximating an optimal cyclic solution, and it yields a (2(11/k)+ε)approximation of the optimal unrestricted (not necessarily cyclic) solution. If the conjecture mentioned above is true, then our algorithm is actually a PTAS for the general problem in the Euclidean setting. Similar results can be obtained by combining our results with other known TSP algorithms in nonEuclidean metrics.more » « less

Dictionaries remain the most well studied class of data structures. A dictionary supports insertions, deletions, membership queries, and usually successor, predecessor, and extractmin. In a RAM, all such operations take O(log n) time on n elements. Dictionaries are often crossreferenced as follows. Consider a set of tuples {〈ai,bi,ci…〉}. A database might include more than one dictionary on such a set, for example, one indexed on the a ‘s, another on the b‘s, and so on. Once again, in a RAM, inserting into a set of L crossreferenced dictionaries takes O(L log n) time, as does deleting. The situation is more interesting in external memory. On a Disk Access Machine (DAM), Btrees achieve O(logB N) I/Os for insertions and deletions on a single dictionary and Kelement range queries take optimal O(logB N + K/B) I/Os. These bounds are also achievable by a Btree on crossreferenced dictionaries, with a slowdown of an L factor on insertion and deletions. In recent years, both the theory and practice of external memory dictionaries has been revolutionized by write optimization techniques. A dictionary is write optimized if it is close to a Btree for query time while beating Btrees on insertions. The best (and optimal) dictionaries achieve a substantially improved insertion and deletion cost of amortized I/Os on a single dictionary while maintaining optimal O(log1+B∊ N + K/B) I/O range queries. Although write optimization still helps for insertions into crossreferenced dictionaries, its value for deletions would seem to be greatly reduced. A deletion into a cross referenced dictionary only specifies a key a. It seems to be necessary to look up the associated values b, c … in order to delete them from the other dictionaries. This takes Ω(logB N) I/Os, well above the perdictionary writeoptimization budget of So the total deletion cost is In short, for deletions, write optimization offers an advantage over Btrees in that L multiplies a lower order term, but when L = 2, write optimization seems to offer no asymptotic advantage over Btrees. That is, no known query optimal solution for pairs of crossreferenced dictionaries seem to beat Btrees for deletions. In this paper, we show a lower bound establishing that a pair of crossreferenced dictionaries that are optimal for range queries and that supports deletions cannot match the write optimization bound available to insertonly dictionaries. This result thus establishes a limit to the applicability of writeoptimization techniques on which many new databases and file systems are based. Read More: http://epubs.siam.org/doi/10.1137/1.9781611974782.99more » « less