Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRelaxing the Irrevocability Requirement for Online Graph Algorithms
53
0
0.0
(
0
)
Added by
Lene M. Favrholdt
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Online graph problems are considered in models where the irrevocability requirement is relaxed. Motivated by practical examples where, for example, there is a cost associated with building a facility and no extra cost associated with doing it later, we consider the Late Accept model, where a request can be accepted at a later point, but any acceptance is irrevocable. Similarly, we also consider a Late Reject model, where an accepted request can later be rejected, but any rejection is irrevocable (this is sometimes called preemption). Finally, we consider the Late Accept/Reject model, where late accepts and rejects are both allowed, but any late reject is irrevocable. For Independent Set, the Late Accept/Reject model is necessary to obtain a constant competitive ratio, but for Vertex Cover the Late Accept model is sufficient and for Minimum Spanning Forest the Late Reject model is sufficient. The Matching problem has a competitive ratio of 2, but in the Late Accept/Reject model, its competitive ratio is 3/2.
rate research
Read More
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.
We study emph{parallel} online algorithms: For some fixed integer $k$, a collective of $k$ parallel processes that perform online decisions on the same sequence of events forms a $k$-emph{copy algorithm}. For any given time and input sequence, the overall performance is determined by the best of the $k$ individual total results. Problems of this type have been considered for online makespan minimization; they are also related to optimization with emph{advice} on future events, i.e., a number of bits available in advance. We develop textsc{Predictive Harmonic}$_3$ (PH3), a relatively simple family of $k$-copy algorithms for the online Bin Packing Problem, whose joint competitive factor converges to 1.5 for increasing $k$. In particular, we show that $k=6$ suffices to guarantee a factor of $1.5714$ for PH3, which is better than $1.57829$, the performance of the best known 1-copy algorithm textsc{Advanced Harmonic}, while $k=11$ suffices to achieve a factor of $1.5406$, beating the known lower bound of $1.54278$ for a single online algorithm. In the context of online optimization with advice, our approach implies that 4 bits suffice to achieve a factor better than this bound of $1.54278$, which is considerably less than the previous bound of 15 bits.
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$.
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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
