Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOnline metric algorithms with untrusted predictions
238
0
0.0
(
0
)
Added by
Adam Polak
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Machine-learned predictors, although achieving very good results for inputs resembling training data, cannot possibly provide perfect predictions in all situations. Still, decision-making systems that are based on such predictors need not only to benefit from good predictions but also to achieve a decent performance when the predictions are inadequate. In this paper, we propose a prediction setup for arbitrary metrical task systems (MTS) (e.g., caching, k-server and convex body chasing) and online matching on the line. We utilize results from the theory of online algorithms to show how to make the setup robust. Specifically for caching, we present an algorithm whose performance, as a function of the prediction error, is exponentially better than what is achievable for general MTS. Finally, we present an empirical evaluation of our methods on real world datasets, which suggests practicality.
rate research
Read More
In this paper, we initiate the study of the weighted paging problem with predictions. This continues the recent line of work in online algorithms with predictions, particularly that of Lykouris and Vassilvitski (ICML 2018) and Rohatgi (SODA 2020) on unweighted paging with predictions. We show that unlike unweighted paging, neither a fixed lookahead nor knowledge of the next request for every page is sufficient information for an algorithm to overcome existing lower bounds in weighted paging. However, a combination of the two, which we call the strong per request prediction (SPRP) model, suffices to give a 2-competitive algorithm. We also explore the question of gracefully degrading algorithms with increasing prediction error, and give both upper and lower bounds for a set of natural measures of prediction error.
We introduce a new model of computation: the online LOCAL model (OLOCAL). In this model, the adversary reveals the nodes of the input graph one by one, in the same way as in classical online algorithms, but for each new node the algorithm can also inspect its radius-$T$ neighborhood before choosing the output; instead of looking ahead in time, we have the power of looking around in space. It is natural to compare OLOCAL with the LOCAL model of distributed computing, in which all nodes make decisions simultaneously in parallel based on their radius-$T$ neighborhoods.
We study the minimum-cost metric perfect matching problem under online i.i.d arrivals. We are given a fixed metric with a server at each of the points, and then requests arrive online, each drawn independently from a known probability distribution over the points. Each request has to be matched to a free server, with cost equal to the distance. The goal is to minimize the expected total cost of the matching. Such stochastic arrival models have been widely studied for the maximization variants of the online matching problem; however, the only known result for the minimization problem is a tight $O(log n)$-competitiveness for the random-order arrival model. This is in contrast with the adversarial model, where an optimal competitive ratio of $O(log n)$ has long been conjectured and remains a tantalizing open question. In this paper, we show improved results in the i.i.d arrival model. We show how the i.i.d model can be used to give substantially better algorithms: our main result is an $O((log log log n)^2)$-competitive algorithm in this model. Along the way we give a $9$-competitive algorithm for the line and tree metrics. Both results imply a strict separation between the i.i.d model and the adversarial and random order models, both for general metrics and these much-studied metrics.
Online algorithms make decisions based on past inputs. In general, the decision may depend on the entire history of inputs. If many computers run the same online algorithm with the same input stream but are started at different times, they do not necessarily make consistent decisions. In this work we introduce time-local online algorithms. These are online algorithms where the output at a given time only depends on $T = O(1)$ latest inputs. The use of (deterministic) time-local algorithms in a distributed setting automatically leads to globally consistent decisions. Our key observation is that time-local online algorithms (in which the output at a given time only depends on local inputs in the temporal dimension) are closely connected to local distributed graph algorithms (in which the output of a given node only depends on local inputs in the spatial dimension). This makes it possible to interpret prior work on distributed graph algorithms from the perspective of online algorithms. We describe an algorithm synthesis method that one can use to design optimal time-local online algorithms for small values of $T$. We demonstrate the power of the technique in the context of a variant of the online file migration problem, and show that e.g. for two nodes and unit migration costs there exists a $3$-competitive time-local algorithm with horizon $T=4$, while no deterministic online algorithm (in the classic sense) can do better. We also derive upper and lower bounds for a more general version of the problem; we show that there is a $6$-competitive deterministic time-local algorithm and a $2.62$-competitive randomized time-local algorithm for any migration cost $alpha ge 1$.
In this paper, we study $k$-Way Min-cost Perfect Matching with Delays - the $k$-MPMD problem. This problem considers a metric space with $n$ nodes. Requests arrive at these nodes in an online fashion. The task is to match these requests into sets of exactly $k$, such that the space and time cost of all matched requests are minimized. The notion of the space cost requires a definition of an underlying metric space that gives distances of subsets of $k$ elements. For $k>2$, the task of finding a suitable metric space is at the core of our problem: We show that for some known generalizations to $k=3$ points, such as the $2$-metric and the $D$-metric, there exists no competitive randomized algorithm for the $3$-MPMD problem. The $G$-metrics are defined for 3 points and allows for a competitive algorithm for the $3$-MPMD problem. For $k>3$ points, there exist two generalizations of the $G$-metrics known as $n$- and $K$-metrics. We show that neither the $n$-metrics nor the $K$-metrics can be used for the $k$-MPMD problem. On the positive side, we introduce the $H$-metrics, the first metrics to allow for a solution of the $k$-MPMD problem for all $k$. In order to devise an online algorithm for the $k$-MPMD problem on the $H$-metrics, we embed the $H$-metric into trees with an $O(log n)$ distortion. Based on this embedding result, we extend the algorithm proposed by Azar et al. (2017) and achieve a competitive ratio of $O(log n)$ for the $k$-MPMD problem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
