Source author record

Spyros Angelopoulos

Spyros Angelopoulos appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Artificial Intelligence math.OC

Catalog footprint

What is connected

7works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2023arXiv

Competitive Search in the Line and the Star with Predictions

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.

preprint2023arXiv

Rényi-Ulam Games and Online Computation with Imperfect Advice

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ényi-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.

preprint2021arXiv

Online Maximum Matching with Recourse

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

preprint2021arXiv

Primal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow-time problems

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.

preprint2020arXiv

Online Search With a Hint

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

preprint2016arXiv

Stochastic dominance and the bijective ratio of online algorithms

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.

preprint2015arXiv

Further Connections Between Contract-Scheduling and Ray-Searching Problems

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.