Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRandomized algorithms for finding a majority element
139
0
0.0
(
0
)
Added by
Przemys{\\l}aw Uzna\\'nski
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Given $n$ colored balls, we want to detect if more than $lfloor n/2rfloor$ of them have the same color, and if so find one ball with such majority color. We are only allowed to choose two balls and compare their colors, and the goal is to minimize the total number of such operations. A well-known exercise is to show how to find such a ball with only $2n$ comparisons while using only a logarithmic number of bits for bookkeeping. The resulting algorithm is called the Boyer--Moore majority vote algorithm. It is known that any deterministic method needs $lceil 3n/2rceil-2$ comparisons in the worst case, and this is tight. However, it is not clear what is the required number of comparisons if we allow randomization. We construct a randomized algorithm which always correctly finds a ball of the majority color (or detects that there is none) using, with high probability, only $7n/6+o(n)$ comparisons. We also prove that the expected number of comparisons used by any such randomized method is at least $1.019n$.
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.
Finding the common subsequences of $L$ multiple strings has many applications in the area of bioinformatics, computational linguistics, and information retrieval. A well-known result states that finding a Longest Common Subsequence (LCS) for $L$ strings is NP-hard, e.g., the computational complexity is exponential in $L$. In this paper, we develop a randomized algorithm, referred to as {em Random-MCS}, for finding a random instance of Maximal Common Subsequence ($MCS$) of multiple strings. A common subsequence is {em maximal} if inserting any character into the subsequence no longer yields a common subsequence. A special case of MCS is LCS where the length is the longest. We show the complexity of our algorithm is linear in $L$, and therefore is suitable for large $L$. Furthermore, we study the occurrence probability for a single instance of MCS and demonstrate via both theoretical and experimental studies that the longest subsequence from multiple runs of {em Random-MCS} often yields a solution to $LCS$.
We consider the randomized decision tree complexity of the recursive 3-majority function. We prove a lower bound of $(1/2-delta) cdot 2.57143^h$ for the two-sided-error randomized decision tree complexity of evaluating height $h$ formulae with error $delta in [0,1/2)$. This improves the lower bound of $(1-2delta)(7/3)^h$ given by Jayram, Kumar, and Sivakumar (STOC03), and the one of $(1-2delta) cdot 2.55^h$ given by Leonardos (ICALP13). Second, we improve the upper bound by giving a new zero-error randomized decision tree algorithm that has complexity at most $(1.007) cdot 2.64944^h$. The previous best known algorithm achieved complexity $(1.004) cdot 2.65622^h$. The new lower bound follows from a better analysis of the base case of the recursion of Jayram et al. The new algorithm uses a novel interleaving of two recursive algorithms.
In this paper we show that many sequential randomized incremental algorithms are in fact parallel. We consider algorithms for several problems including Delaunay triangulation, linear programming, closest pair, smallest enclosing disk, least-element lists, and strongly connected components. We analyze the dependences between iterations in an algorithm, and show that the dependence structure is shallow with high probability, or that by violating some dependences the structure is shallow and the work is not increased significantly. We identify three types of algorithms based on their dependences and present a framework for analyzing each type. Using the framework gives work-efficient polylogarithmic-depth parallel algorithms for most of the problems that we study. This paper shows the first incremental Delaunay triangulation algorithm with optimal work and polylogarithmic depth, which is an open problem for over 30 years. This result is important since most implementations of parallel Delaunay triangulation use the incremental approach. Our results also improve bounds on strongly connected components and least-elements lists, and significantly simplify parallel algorithms for several problems.
In this paper we develop optimal algorithms in the binary-forking model for a variety of fundamental problems, including sorting, semisorting, list ranking, tree contraction, range minima, and ordered set union, intersection and difference. In the binary-forking model, tasks can only fork into two child tasks, but can do so recursively and asynchronously. The tasks share memory, supporting reads, writes and test-and-sets. Costs are measured in terms of work (total number of instructions), and span (longest dependence chain). The binary-forking model is meant to capture both algorithm performance and algorithm-design considerations on many existing multithreaded languages, which are also asynchronous and rely on binary forks either explicitly or under the covers. In contrast to the widely studied PRAM model, it does not assume arbitrary-way forks nor synchronous operations, both of which are hard to implement in modern hardware. While optimal PRAM algorithms are known for the problems studied herein, it turns out that arbitrary-way forking and strict synchronization are powerful, if unrealistic, capabilities. Natural simulations of these PRAM algorithms in the binary-forking model (i.e., implementations in existing parallel languages) incur an $Omega(log n)$ overhead in span. This paper explores techniques for designing optimal algorithms when limited to binary forking and assuming asynchrony. All algorithms described in this paper are the first algorithms with optimal work and span in the binary-forking model. Most of the algorithms are simple. Many are randomized.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
