Search

The article of record as published may be found at https://doi.org/10.1016/j.tcs.2020.03.011 A set of n boxes, located on the vertices of a hypergraph G, contain known but different rewards. A Searcher opens all the boxes in some hyperedge of G with the objective of collecting the maximum possible total reward. Some of the boxes, however, are booby trapped. If the Searcher opens a booby trapped box, the search ends and she loses all her collected rewards. We assume the number k of booby traps is known, and we model the problem as a zero-sum game between the maximizing Searcher and a minimizing Hider, where the Hider chooses k boxes to booby trap and the Searcher opens all the boxes in some hyperedge. The payoff is the total reward collected by the Searcher. This model could reflect a military operation in which a drone gathers intelligence from guarded locations, and a booby trapped box being opened corresponds to the drone being destroyed or incapacitated. It could also model a machine scheduling problem, in which rewards are obtained from successfully processing jobs but the machine may crash. We solve the game when G is a 1-uniform hypergraph (the hyperedges are all singletons), so the Searcher can open just 1 box. When G is the complete hypergraph (containing all possible hyperedges), we solve the game in a few cases: (1) same reward in each box, (2) k=1, and (3) n=4 and k = 2. The solutions to these few cases indicate that a general simple, closed form solution to the game appears unlikely. This material is based upon work supported by the National Science Foundation under Grant No. IIS-1909446. This material is based upon work supported by the National Science Foundation under Grant No. IIS-1909446.

The article of record as published may be found at http://dx.doi.org/10.1016/j.cor.2006.09.020 We develop and analyze a “manhunting” game involving a mobile hider, who wishes to maximize his time to capture, and a mobile searcher, who wishes to minimize this same time. The game takes place within a variegated environment that offers better and worse locations to evade capture. The hider is able to move from one hide site to another at will. In choosing a hide site, he must consider the risk of discovery, the risk that he will be betrayed, and the risk that he will be captured while moving from one site to another. The searcher can select any cell to search within the fugitive’s feasible hiding set. We examine the strategic behavior of both players and provide examples. Published by Elsevier Ltd.

We consider the problem of searching for an object on a line at an unknown distance OPT from the original position of the searcher, in the presence of a cost of d for each time the searcher changes direction. This is a generalization of the well-studied linear-search problem. We describe a strategy that is guaranteed to find the object at a cost of at most 9*OPT + 2d, which has the optimal competitive ratio 9 with respect to OPT plus the minimum corresponding additive term. Our argument for upper and lower bound uses an infinite linear program, which we solve by experimental solution of an infinite series of approximating finite linear programs, estimating the limits, and solving the resulting recurrences. We feel that this technique is interesting in its own right and should help solve other searching problems. In particular, we consider the star search or cow-path problem with turn cost, where the hidden object is placed on one of m rays emanating from the original position of the searcher. For this problem we give a tight bound of (1+(2(m^m)/((m-1)^(m-1))) OPT + m ((m/(m-1))^(m-1) - 1) d. We also discuss tradeoff between the corresponding coefficients, and briefly consider randomized strategies on the line., 15 pages, 2 figures, 1 table; to appear in Theoretical Computer Science. Did some minor editorial changes, fixed some typos, etc