Search

We study a generalization of the advice complexity model of online computation in which the advice is provided by an untrusted source. Our objective is to quantify the impact of untrusted advice so as to design and analyze online algorithms that are robust if the advice is adversarial, and efficient is the advice is foolproof. We focus on four well-studied online problems, namely ski rental, online bidding, bin packing and list update. For ski rental and online bidding, we show how to obtain algorithms that are Pareto-optimal with respect to the competitive ratios achieved, whereas for bin packing and list update, we give online algorithms with worst-case tradeoffs in their competitiveness, depending on whether the advice is trusted or adversarial. More importantly, we demonstrate how to prove lower bounds, within this model, on the tradeoff between the number of advice bits and the competitiveness of any online algorithm. [ABSTRACT FROM AUTHOR]

We study the problem of searching for a hidden target in an environment that is modeled by an edge-weighted graph. A sequence of edges is chosen starting from a given root vertex such that each edge is adjacent to a previously chosen edge. This search paradigm, known as expanding search was recently introduced by Alpern and Lidbetter (2013) for modeling problems such as searching for coal or minesweeping in which the cost of re-exploration is negligible. It can also be used to model a team of searchers successively splitting up in the search for a hidden adversary or explosive device, for example. We define the search ratio of an expanding search as the maximum over all vertices of the ratio of the time taken to reach the vertex and the shortest-path cost to it from the root. This can be interpreted as a measure of the multiplicative regret incurred in searching, and similar objectives have previously been studied in the context of conventional (pathwise) search. In this paper we address algorithmic and computational issues of minimizing the search ratio over all expanding searches, for a variety of search environments, including general graphs, trees and star-like graphs. Our main results focus on the problem of finding the randomized expanding search with minimum expected search ratio , which is equivalent to solving a zero-sum game between a Searcher and a Hider. We solve these problems for certain classes of graphs, and obtain constant-factor approximations for others. [ABSTRACT FROM AUTHOR]

We introduce the study of search problems, in a setting in which the searcher has some information, or hint concerning the hiding target. In particular, we focus on one of the fundamental problems in search theory, namely the linear search problem. Here, an immobile target is hidden at some unknown position on an unbounded line, and a mobile searcher, initially positioned at some specific point of the line called the root , must traverse the line so as to locate the target. The objective is to minimize the worst-case ratio of the distance traversed by the searcher to the distance of the target from the root, which is known as the competitive ratio of the search. We consider three settings in regards to the nature of the hint: i) the hint suggests the exact position of the target on the line; ii) the hint suggests the direction of the optimal search (i.e., to the left or the right of the root); and iii) the hint is a general k -bit string that encodes some information concerning the target. Our objective is to study the Pareto -efficiency of strategies in this model, with respect to the tradeoff between consistency and robustness. Namely, we seek optimal, or near-optimal tradeoffs between the searcher's performance if the hint is correct (i.e., provided by a trusted source) and if the hint is incorrect (i.e., provided by an adversary). We prove several results in each of these three settings. For positional hints, we show that the optimal consistency of r -robust strategies is (b r + 1) / (b r − 1) , where b r is defined to be equal to ρ r + ρ r 2 − 4 ρ r 2 , and ρ r = (r − 1) / 2 , for all r ≥ 9. For directional hints, we show that for every b ≥ 1 and δ ∈ (0 , 1 ] , there exists a strategy with consistency equal to c = 1 + 2 ( b 2 b 2 − 1 + δ b 3 b 2 − 1) and robustness equal to 1 + 2 ( b 2 b 2 − 1 + 1 δ b 3 b 2 − 1) ; furthermore, we show again that this upper bound is tight. Last, for general k -bit hints, we show upper bounds for general k -bit hints, as well as lower bounds: specifically, we show that the consistency of any 9-robust strategy must be at least 5, and that the consistency of r -robust strategies is at least 1 + 2 b r / (b r − 1) , in the case of a natural class of asymptotic strategies. [ABSTRACT FROM AUTHOR]

We study the general setting of weighted search in which a number of weighted targets are hidden in a star-like environment, and a mobile searcher must locate a subset of targets with aggregate weight at least a given value W. The cost of the strategy is the distance traversed by the searcher, and its performance is measured by the worst-case ratio of the cost incurred by the searcher over the cost of an on optimal, offline strategy. This is the first study of a setting that generalizes several problems in search theory such as searching for a single target and searching for unit-weighted targets. We present and analyze a near-optimal strategy using an approach based on parameterized analysis. This problem formulates settings of resource allocation among parallel tasks under uncertainty; specifically, we demonstrate further applications in the design of interruptible systems based on adaptive scheduling of contract algorithms. [ABSTRACT FROM AUTHOR]