Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOnline Algorithms with Lookaround
91
0
0.0
(
0
)
Added by
Darya Melnyk
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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$.
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.
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.
The general adwords problem has remained largely unresolved. We define a subcase called {em $k$-TYPICAL}, $k in Zplus$, as follows: the total budget of all the bidders is sufficient to buy $k$ bids for each bidder. This seems a reasonable assumption for a typical instance, at least for moderate values of $k$. We give a randomized online algorithm, achieving a competitive ratio of $left(1 - {1 over e} - {1 over k} right)$, for this problem. We also give randomized online algorithms for other special cases of adwords. Another subcase, when bids are small compared to budgets, has been of considerable practical significance in ad auctions cite{MSVV}. For this case, we give an optimal randomized online algorithm achieving a competitive ratio of $left(1 - {1 over e} right)$. Previous algorithms for this case were based on LP-duality; the impact of our new approach remains to be seen. The key to these results is a simplification of the proof for RANKING, the optimal algorithm for online bipartite matching, given in cite{KVV}. Our algorithms for adwords can be seen as natural extensions of RANKING.
Payment channels allow transactions between participants of the blockchain to be executed securely off-chain, and thus provide a promising solution for the scalability problem of popular blockchains. We study the online network design problem for payment channels, assuming a central coordinator. We focus on a single channel, where the coordinator desires to maximize the number of accepted transactions under given capital constraints. Despite the simplicity of the problem, we present a flurry of impossibility results, both for deterministic and randomized algorithms against adaptive as well as oblivious adversaries.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
