Search

We initiate the study of tree structures in the context of scenario-based robust optimization. Specifically, we study Binary Search Trees (BSTs) and Huffman coding, two fundamental techniques for efficiently managing and encoding data based on a known set of frequencies of keys. Given $k$ different scenarios, each defined by a distinct frequency distribution over the keys, our objective is to compute a single tree of best-possible performance, relative to any scenario. We consider, as performance metrics, the competitive ratio, which compares multiplicatively the cost of the solution to the tree of least cost among all scenarios, as well as the regret, which induces a similar, but additive comparison. For BSTs, we show that the problem is NP-hard across both metrics. We also show how to obtain a tree of competitive ratio $\lceil \log_2(k+1) \rceil$, and we prove that this ratio is optimal. For Huffman Trees, we show that the problem is, likewise, NP-hard across both metrics; we also give an algorithm of regret $\lceil \log_2 k \rceil$, which we show is near-optimal, by proving a lower bound of $\lfloor \log_2 k \rfloor$. Last, we give a polynomial-time algorithm for computing Pareto-optimal BSTs with respect to their regret, assuming scenarios defined by uniform distributions over the keys. This setting captures, in particular, the first study of fairness in the context of data structures. We provide an experimental evaluation of all algorithms. To this end, we also provide mixed integer linear program formulation for computing optimal trees.

The study of online algorithms with machine-learned predictions has gained considerable prominence in recent years. One of the common objectives in the design and analysis of such algorithms is to attain (Pareto) optimal tradeoffs between the consistency of the algorithm, i.e., its performance assuming perfect predictions, and its robustness, i.e., the performance of the algorithm under adversarial predictions. In this work, we demonstrate that this optimization criterion can be extremely brittle, in that the performance of Pareto-optimal algorithms may degrade dramatically even in the presence of imperceptive prediction error. To remedy this drawback, we propose a new framework in which the smoothness in the performance of the algorithm is enforced by means of a user-specified profile. This allows us to regulate the performance of the algorithm as a function of the prediction error, while simultaneously maintaining the analytical notion of consistency/robustness tradeoffs, adapted to the profile setting. We apply this new approach to a well-studied online problem, namely the one-way trading problem. For this problem, we further address another limitation of the state-of-the-art Pareto-optimal algorithms, namely the fact that they are tailored to worst-case, and extremely pessimistic inputs. We propose a new Pareto-optimal algorithm that leverages any deviation from the worst-case input to its benefit, and introduce a new metric that allows us to compare any two Pareto-optimal algorithms via a dominance relation.

Contract scheduling is a widely studied framework for designing real-time systems with interruptible capabilities. Previous work has showed that a prediction on the interruption time can help improve the performance of contract-based systems, however it has relied on a single prediction that is provided by a deterministic oracle. In this work, we introduce and study more general and realistic learning-augmented settings in which the prediction is in the form of a probability distribution, or it is given as a set of multiple possible interruption times. For both prediction settings, we design and analyze schedules which perform optimally if the prediction is accurate, while simultaneously guaranteeing the best worst-case performance if the prediction is adversarial. We also provide evidence that the resulting system is robust to prediction errors in the distributional setting. Last, we present an experimental evaluation that confirms the theoretical findings, and illustrates the performance improvements that can be attained in practice., Comment: To appear in Proceedings of IJCAI 2024

We introduce the study of search games between a mobile Searcher and an immobile Hider in a new setting in which the Searcher has some potentially erroneous information, i.e., a prediction on the Hider's position. The objective is to establish tight tradeoffs between the consistency of a search strategy (i.e., its worst case expected payoff assuming the prediction is correct) and its robustness (i.e., the worst case expected payoff with no assumptions on the quality of the prediction). Our study is the first to address the full power of mixed (randomized) strategies; previous work focused only on deterministic strategies, or relied on stochastic assumptions that do not guarantee worst-case robustness in adversarial situations. We give Pareto-optimal strategies for three fundamental problems, namely searching in discrete locations, searching with stochastic overlook, and searching in the infinite line. As part of our contribution, we provide a novel framework for proving optimal tradeoffs in search games which is applicable, more broadly, to any two-person zero-sum games in learning-augmented settings.

We study the classic problem of searching for a hidden target in the line and the $m$-ray star, in a setting in which the searcher has some prediction on the hider's position. We first focus on the main metric for comparing search strategies under predictions; namely, we give positive and negative results on the consistency-robustness tradeoff, where the performance of the strategy is evaluated at extreme situations in which the prediction is either error-free, or adversarially generated, respectively. For the line, we show tight bounds concerning this tradeoff, under the untrusted advice model, in which the prediction is in the form of a $k$-bit string which encodes the responses to $k$ binary queries. For the star, we give tight, and near-tight tradeoffs in the positional and the directional models, in which the prediction is related to the position of the target within the star, and to the ray on which the target hides, respectively. Last, for all three prediction models, we show how to generalize our study to a setting in which the performance of the strategy is evaluated as a function of the searcher's desired tolerance to prediction errors, both in terms of positive and inapproximability results., Comment: Conference version in MFCS 2023

We study the nascent setting of online computation with imperfect advice, in which the online algorithm is enhanced by some prediction encoded in the form of a possibly erroneous binary string. The algorithm is oblivious to the advice error, but defines a desired tolerance, namely an upper bound on the number of erroneous advice bits it can tolerate. This is a model that generalizes the untrusted advice model [Angelopoulos et al. ITCS 2020], in which the performance of the algorithm is only evaluated at the extreme values of error (namely, if the advice has either no errors, or if it is generated adversarially). In this work, we establish connections between games with a lying responder, also known as R\'enyi-Ulam games, and the design and analysis of online algorithms with imperfect advice. Specifically, we demonstrate how to obtain upper and lower bounds on the competitive ratio for well-studied online problems such as time-series search, online bidding, and fractional knapsack. Our techniques provide the first lower bounds for online problems in this model. We also highlight and exploit connections between competitive analysis with imperfect advice and fault-tolerance in multiprocessor systems. Last, we show how to waive the dependence on the tolerance parameter, by means of resource augmentation and robustification.

In the online (time-series) search problem, a player is presented with a sequence of prices which are revealed in an online manner. In the standard definition of the problem, for each revealed price, the player must decide irrevocably whether to accept or reject it, without knowledge of future prices (other than an upper and a lower bound on their extreme values), and the objective is to minimize the competitive ratio, namely the worst-case ratio between the maximum price in the sequence and the one selected by the player. The problem formulates several applications of decision-making in the face of uncertainty on the revealed samples. Previous work on this problem has largely assumed extreme scenarios in which either the player has almost no information about the input, or the player is provided with some powerful, and error-free advice. In this work, we study learning-augmented algorithms, in which there is a potentially erroneous prediction concerning the input. Specifically, we consider two different settings: the setting in which the prediction is related to the maximum price in the sequence, as well as the setting in which the prediction is obtained as a response to a number of binary queries. For both settings, we provide tight, or near-tight upper and lower bounds on the worst-case performance of search algorithms as a function of the prediction error. We also provide experimental results on data obtained from stock exchange markets that confirm the theoretical analysis, and explain how our techniques can be applicable to other learning-augmented applications., Comment: 22 pages, 5 figures

Several well-studied online resource allocation problems can be formulated in terms of infinite, increasing sequences of positive values, in which each element is associated with a corresponding allocation value. Examples include problems such as online bidding, searching for a hidden target on an unbounded line, and designing interruptible algorithms based on repeated executions. The performance of the online algorithm, in each of these problems, is measured by the competitive ratio, which describes the multiplicative performance loss due to the absence of full information on the instance. We study such competitive sequencing problems in a setting in which the online algorithm has some (potentially) erroneous information, expressed as a $k$-bit advice string, for some given $k$. We first consider the untrusted advice setting of [Angelopoulos et al, ITCS 2020], in which the objective is to quantify performance considering two extremes: either the advice is either error-free, or it is generated by a (malicious) adversary. Here, we show a Pareto-optimal solution, using a new approach for applying the functional-based lower-bound technique due to [Gal, Israel J. Math. 1972]. Next, we study a nascent noisy advice setting, in which a number of the advice bits may be erroneous; the exact error is unknown to the online algorithm, which only has access to a pessimistic estimate (i.e., an upper bound on this error). We give improved upper bounds, but also the first lower bound on the competitive ratio of an online problem in this setting. To this end, we combine ideas from robust query-based search in arrays, and fault-tolerant contract scheduling. Last, we demonstrate how to apply the above techniques in robust optimization without predictions, and discuss how they can be applicable in the context of more general online problems.

Bin packing is a classic optimization problem with a wide range of applications, from load balancing to supply chain management. In this work, we study the online variant of the problem, in which a sequence of items of various sizes must be placed into a minimum number of bins of uniform capacity. The online algorithm is enhanced with a (potentially erroneous) prediction concerning the frequency of item sizes in the sequence. We design and analyze online algorithms with efficient tradeoffs between the consistency (i.e., the competitive ratio assuming no prediction error) and the robustness (i.e., the competitive ratio under adversarial error), and whose performance degrades near-optimally as a function of the prediction error. This is the first theoretical and experimental study of online bin packing under competitive analysis, in the realistic setting of learnable predictions. Previous work addressed only extreme cases with respect to the prediction error, and relied on overly powerful and error-free oracles., Comment: 30 pages, 6 figures

We study the setting in which a mobile agent must locate a hidden target in a bounded or unbounded environment, with no information about the hider's position. In particular, we consider online search, in which the performance of the search strategy is evaluated by its worst case competitive ratio. We introduce a multi-criteria search problem in which the searcher has a budget on its allotted search time, and the objective is to design strategies that are competitively efficient, respect the budget, and maximize the total searched ground. We give analytically optimal strategies for the line and the star environments, and efficient heuristics for general networks.

Contract scheduling is a general technique that allows to design a system with interruptible capabilities, given an algorithm that is not necessarily interruptible. Previous work on this topic has largely assumed that the interruption is a worst-case deadline that is unknown to the scheduler. In this work, we study the setting in which there is a potentially erroneous prediction concerning the interruption. Specifically, we consider the setting in which the prediction describes the time that the interruption occurs, as well as the setting in which the prediction is obtained as a response to a single or multiple binary queries. For both settings, we investigate tradeoffs between the robustness (i.e., the worst-case performance assuming adversarial prediction) and the consistency (i.e, the performance assuming that the prediction is error-free), both from the side of positive and negative results.

The linear search problem, informally known as the cow path problem, is one of the fundamental problems in search theory. In this problem, 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. In this work we study this problem in a setting in which the searcher has a hint concerning the target. 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. 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 study the classic problem in which a Searcher must locate a hidden point, also called the Hider in a network, starting from a root point. The network may be either bounded or unbounded, thus generalizing well-known settings such as linear and star search. We distinguish between pathwise search, in which the Searcher follows a continuous unit-speed path until the Hider is reached, and expanding search, in which, at any point in time, the Searcher may restart from any previously reached point. The former has been the usual paradigm for studying search games, whereas the latter is a more recent paradigm that can model real-life settings such as hunting for a fugitive, demining a field, or search-and-rescue operations. We seek both deterministic and randomized search strategies that minimize the competitive ratio, namely the worst-case ratio of the Hider's discovery time, divided by the shortest path to it from the root. Concerning expanding search, we show that a simple search strategy that applies a "waterfilling" principle has optimal deterministic competitive ratio; in contrast, we show that the optimal randomized competitive ratio is attained by fairly complex strategies even in a very simple network of three arcs. Motivated by this observation, we present and analyze an expanding search strategy that is a 5/4 approximation of the randomized competitive ratio. Our approach is also applicable to pathwise search, for which we give a strategy that is a 5 approximation of the randomized competitive ratio, and which improves upon strategies derived from previous work.

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.

In this paper we address the problem of designing an interruptible system in a setting in which $n$ problem instances, all equally important, must be solved concurrently. The system involves scheduling executions of contract algorithms (which offer a trade-off between allowable computation time and quality of the solution) in m identical parallel processors. When an interruption occurs, the system must report a solution to each of the $n$ problem instances. The quality of this output is then compared to the best-possible algorithm that has foreknowledge of the interruption time and must, likewise, produce solutions to all $n$ problem instances. This extends the well-studied setting in which only one problem instance is queried at interruption time. In this work we first introduce new measures for evaluating the performance of interruptible systems in this setting. In particular, we propose the deficiency of a schedule as a performance measure that meets the requirements of the problem at hand. We then present a schedule whose performance we prove that is within a small factor from optimal in the general, multiprocessor setting. We also show several lower bounds on the deficiency of schedules on a single processor. More precisely, we prove a general lower bound of (n+1)/n, an improved lower bound for the two-problem setting (n=2), and a tight lower bound for the class of round-robin schedules. Our techniques can also yield a simpler, alternative proof of the main result of [Bernstein et al, IJCAI 2003] concerning the performance of cyclic schedules in multiprocessor environments., Comment: Extended version of IJCAI 2009 paper

In search problems, a mobile searcher seeks to locate a target that hides in some unknown position of the environment. Such problems are typically considered to be of an on-line nature, in that the input is unknown to the searcher, and the performance of a search strategy is usually analyzed by means of the standard framework of the competitive ratio, which compares the cost incurred by the searcher to an optimal strategy that knows the location of the target. However, one can argue that even for simple search problems, competitive analysis fails to distinguish between strategies which, intuitively, should have different performance in practice. Motivated by the above, in this work we introduce and study measures supplementary to competitive analysis in the context of search problems. In particular, we focus on the well-known problem of linear search, informally known as the cow-path problem, for which there is an infinite number of strategies that achieve an optimal competitive ratio equal to 9. We propose a measure that reflects the rate at which the line is being explored by the searcher, and which can be seen as an extension of the bijective ratio over an uncountable set of requests. Using this measure we show that a natural strategy that explores the line aggressively is optimal among all 9-competitive strategies. This provides, in particular, a strict separation from the competitively optimal doubling strategy, which is much more conservative in terms of exploration. We also provide evidence that this aggressiveness is requisite for optimality, by showing that any optimal strategy must mimic the aggressive strategy in its first few explorations.

We study the online maximum matching problem in a model in which the edges are associated with a known recourse parameter $k$. An online algorithm for this problem has to maintain a valid matching while edges of the underlying graph are presented one after the other. At any moment the algorithm can decide to include an edge into the matching or to exclude it, under the restriction that at most $k$ such actions per edge take place, where $k$ is typically a small constant. This problem was introduced and studied in the context of general online packing problems with recourse by Avitabile et al. [Information Processing Letters, 2013], whereas the special case $k=2$ was studied by Boyar et al. [WADS 2017]. In the first part of this paper we consider the edge arrival model, in which an arriving edge never disappears from the graph. Here, we first show an improved analysis on the performance of the algorithm AMP of Avitabile et al., by exploiting the structure of the matching problem. In addition, we show that the greedy algorithm has competitive ratio $3/2$ for every even $k$ and ratio $2$ for every odd $k$. Moreover, we present and analyze an improvement of the greedy algorithm which we call $L$-Greedy, and we show that for small values of $k$ it outperforms the algorithm AMP. In terms of lower bounds, we show that no deterministic algorithm better than $1+1/(k-1)$ exists, improving upon the known lower bound of $1+1/k$. The second part of the paper is devoted to the edge arrival/departure model, which is the fully dynamic variant of online matching with recourse. The analysis of $L$-Greedy and AMP carry through in this model; moreover we show a lower bound of $(k^2-3k+6) / (k^2-4k+7)$ for all even $k \ge 4$. For $k\in\{2,3\}$, the competitive ratio is $3/2$.

We introduce and study the general setting of weighted search in which a number of targets, each with a certain weight, are hidden in a star-like environment that consists of $m$ infinite, concurrent rays, with a common origin. A mobile searcher, initially located at the origin, explores this environment so as to locate a set of targets whose aggregate weight is at least a given value $W$. The cost of the search strategy is defined as the total 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 with complete access to the instance. This is the first study of a setting that generalizes several problems in search theory: the problem in which only a single target is sought, as well as the problem in which all targets have unit weights. We present and analyze a search strategy of near-optimal performance for the problem at hand. We observe that the classical approaches that rely on geometrically increasing search depths perform rather poorly in the context of weighted search. We bypass this problem by using a strategy that modifies the search depths adaptively, depending on the number of targets located up to the current point in time.

Stochastic dominance is a technique for evaluating the performance of online algorithms that provides an intuitive, yet powerful stochastic order between the compared algorithms. Accordingly this holds for bijective analysis, which can be interpreted as stochastic dominance assuming the uniform distribution over requests. These techniques have been applied to some online problems, and have provided a clear separation between algorithms whose performance varies significantly in practice. However, there are situations in which they are not readily applicable due to the fact that they stipulate a stringent relation between the compared algorithms. In this paper, we propose remedies for these shortcomings. First, we establish sufficient conditions that allow us to prove the bijective optimality of a certain class of algorithms for a wide range of problems; we demonstrate this approach in the context of some well-studied online problems. Second, to account for situations in which two algorithms are incomparable or there is no clear optimum, we introduce the bijective ratio as a natural extension of (exact) bijective analysis. Our definition readily generalizes to stochastic dominance. This renders the concept of bijective analysis (and that of stochastic dominance) applicable to all online problems, and allows for the incorporation of other useful techniques such as amortized analysis. We demonstrate the applicability of the bijective ratio to one of the fundamental online problems, namely the continuous $k$-server problem on metrics such as the line, the circle, and the star. Among other results, we show that the greedy algorithm attains bijective ratios of $O(k)$ consistently across these metrics. These results confirm extensive previous studies that gave evidence of the efficiency of this algorithm on said metrics in practice, which, however, is not reflected in competitive analysis., Comment: Abridged abstract; full abstract in manuscript

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 Apern 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.

This paper addresses two classes of different, yet interrelated optimization problems. The first class of problems involves a robot that must locate a hidden target in an environment that consists of a set of concurrent rays. The second class pertains to the design of interruptible algorithms by means of a schedule of contract algorithms. We study several variants of these families of problems, such as searching and scheduling with probabilistic considerations, redundancy and fault-tolerance issues, randomized strategies, and trade-offs between performance and preemptions. For many of these problems we present the first known results that apply to multi-ray and multi-problem domains. Our objective is to demonstrate that several well-motivated settings can be addressed using the same underlying approach., Comment: Full version of conference paper, to appear in Proceedings of IJCAI 2015

We study online scheduling problems on a single processor that can be viewed as extensions of the well-studied problem of minimizing total weighted flow time. In particular, we provide a framework of analysis that is derived by duality properties, does not rely on potential functions and is applicable to a variety of scheduling problems. A key ingredient in our approach is bypassing the need for "black-box" rounding of fractional solutions, which yields improved competitive ratios. We begin with an interpretation of Highest-Density-First (HDF) as a primal-dual algorithm, and a corresponding proof that HDF is optimal for total fractional weighted flow time (and thus scalable for the integral objective). Building upon the salient ideas of the proof, we show how to apply and extend this analysis to the more general problem of minimizing $\sum_j w_j g(F_j)$, where $w_j$ is the job weight, $F_j$ is the flow time and $g$ is a non-decreasing cost function. Among other results, we present improved competitive ratios for the setting in which $g$ is a concave function, and the setting of same-density jobs but general cost functions. We further apply our framework of analysis to online weighted completion time with general cost functions as well as scheduling under polyhedral constraints., Comment: 30 pages