Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Comparison of Performance Measures via Online Search
126
0
0.0
(
0
)
Added by
Joan Boyar F
Publication date
2011
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Though competitive analysis has been a very useful performance measure for the quality of online algorithms, it is recognized that it sometimes fails to distinguish between algorithms of different quality in practice. A number of alternative measures have been proposed, but, with a few exceptions, these have generally been applied only to the online problem they were developed in connection with. Recently, a systematic study of performance measures for online algorithms was initiated [Boyar, Irani, Larsen: Eleventh International Algorithms and Data Structures Symposium 2009], first focusing on a simple server problem. We continue this work by studying a fundamentally different online problem, online search, and the Reservation Price Policies in particular. The purpose of this line of work is to learn more about the applicability of various performance measures in different situations and the properties that the different measures emphasize. We investigate the following analysis techniques: Competitive, Relative Worst Order, Bijective, Average, Relative Interval, Random Order, and Max/Max. In addition to drawing conclusions on this work, we also investigate the measures sensitivity to integral vs. real-valued domains, and as a part of this work, generalize some of the known performance measures. Finally, we have established the first optimality proof for Relative Interval Analysis.
rate research
Read More
In this paper, we strengthen the competitive analysis results obtained for a fundamental online streaming problem, the Frequent Items Problem. Additionally, we contribute with a more detailed analysis of this problem, using alternative performance measures, supplementing the insight gained from competitive analysis. The results also contribute to the general study of performance measures for online algorithms. It has long been known that competitive analysis suffers from drawbacks in certain situations, and many alternative measures have been proposed. However, more systematic comparative studies of performance measures have been initiated recently, and we continue this work, using competitive analysis, relative interval analysis, and relative worst order analysis on the Frequent Items Problem.
Over three decades ago, Karp, Vazirani and Vazirani (STOC90) introduced the online bipartite matching problem. They observed that deterministic algorithms competitive ratio for this problem is no greater than $1/2$, and proved that randomized algorithms can do better. A natural question thus arises: emph{how random is random}? i.e., how much randomness is needed to outperform deterministic algorithms? The textsc{ranking} algorithm of Karp et al.~requires $tilde{O}(n)$ random bits, which, ignoring polylog terms, remained unimproved. On the other hand, Pena and Borodin (TCS19) established a lower bound of $(1-o(1))loglog n$ random bits for any $1/2+Omega(1)$ competitive ratio. We close this doubly-exponential gap, proving that, surprisingly, the lower bound is tight. In fact, we prove a emph{sharp threshold} of $(1pm o(1))loglog n$ random bits for the randomness necessary and sufficient to outperform deterministic algorithms for this problem, as well as its vertex-weighted generalization. This implies the same threshold for the advice complexity (nondeterminism) of these problems. Similar to recent breakthroughs in the online matching literature, for edge-weighted matching (Fahrbach et al.~FOCS20) and adwords (Huang et al.~FOCS20), our algorithms break the barrier of $1/2$ by randomizing matching choices over two neighbors. Unlike these works, our approach does not rely on the recently-introduced OCS machinery, nor the more established randomized primal-dual method. Instead, our work revisits a highly-successful online design technique, which was nonetheless under-utilized in the area of online matching, namely (lossless) online rounding of fractional algorithms. While this technique is known to be hopeless for online matching in general, we show that it is nonetheless applicable to carefully designed fractional algorithms with additional (non-convex) constraints.
We consider the design of adaptive data structures for searching elements of a tree-structured space. We use a natural generalization of the rotation-based online binary search tree model in which the underlying search space is the set of vertices of a tree. This model is based on a simple structure for decomposing graphs, previously known under several names including elimination trees, vertex rankings, and tubings. The model is equivalent to the classical binary search tree model exactly when the underlying tree is a path. We describe an online $O(log log n)$-competitive search tree data structure in this model, matching the best known competitive ratio of binary search trees. Our method is inspired by Tango trees, an online binary search tree algorithm, but critically needs several new notions including one which we call Steiner-closed search trees, which may be of independent interest. Moreover our technique is based on a novel use of two levels of decomposition, first from search space to a set of Steiner-closed trees, and secondly from these trees into paths.
Nearly thirty years ago, Bar-Noy, Motwani and Naor [IPL92] conjectured that an online $(1+o(1))Delta$-edge-coloring algorithm exists for $n$-node graphs of maximum degree $Delta=omega(log n)$. This conjecture remains open in general, though it was recently proven for bipartite graphs under emph{one-sided vertex arrivals} by Cohen et al.~[FOCS19]. In a similar vein, we study edge coloring under widely-studied relaxations of the online model. Our main result is in the emph{random-order} online model. For this model, known results fall short of the Bar-Noy et al.~conjecture, either in the degree bound [Aggarwal et al.~FOCS03], or number of colors used [Bahmani et al.~SODA10]. We achieve the best of both worlds, thus resolving the Bar-Noy et al.~conjecture in the affirmative for this model. Our second result is in the adversarial online (and dynamic) model with emph{recourse}. A recent algorithm of Duan et al.~[SODA19] yields a $(1+epsilon)Delta$-edge-coloring with poly$(log n/epsilon)$ recourse. We achieve the same with poly$(1/epsilon)$ recourse, thus removing all dependence on $n$. Underlying our results is one common offline algorithm, which we show how to implement in these two online models. Our algorithm, based on the Rodl Nibble Method, is an adaptation of the distributed algorithm of Dubhashi et al.~[TCS98]. The Nibble Method has proven successful for distributed edge coloring. We display its usefulness in the context of online algorithms.
We study the online discrepancy minimization problem for vectors in $mathbb{R}^d$ in the oblivious setting where an adversary is allowed fix the vectors $x_1, x_2, ldots, x_n$ in arbitrary order ahead of time. We give an algorithm that maintains $O(sqrt{log(nd/delta)})$ discrepancy with probability $1-delta$, matching the lower bound given in [Bansal et al. 2020] up to an $O(sqrt{log log n})$ factor in the high-probability regime. We also provide results for the weighted and multi-col
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
