All Questions
Tagged with randomized-algorithms reference-request
25 questions
2
votes
0
answers
59
views
Approximately sampling from a discrete unimodal distribution with large support
I have an algorithmic problem and I am curious if a solution is known in the literature, because I cannot find it. I came up with an algorithm of my own, but would be curious if something is known.
I ...
- 630
0
votes
0
answers
97
views
Examples of Gaussian randomized algorithms
I've been thinking about algorithms of the form where a quantity $c$ can be viewed as the expectation of some estimator (random variable) $X$ and the expectation is taken over some multivariate ...
- 111
2
votes
1
answer
115
views
Property testable in sublinear time in bounded degree graphs but not in general graphs
Is there some natural property that is testable in strongly sublinear time (i.e. $O(n^{1-\epsilon})$ for some $\epsilon > 0$) in bounded-degree graphs but not in general graphs? If not such ...
- 630
0
votes
0
answers
81
views
A variant of randomized co-ordinate descent
Let us consider the following optimization problem.
$\mathcal{P} =\{P_1,\cdots,P_n\}$, where $P_i\subset\mathbb{R}^d$. Let $m = max_i\lvert P_i\rvert$. The goal is to find a point $c$ such that ...
- 265
5
votes
0
answers
177
views
Classification of randomized approximation algorithms
Is there a known classification of randomized approximation algorithms, in the same vein as the distinction between Monte Carlo and Las Vegas algorithms for decision problems? (Or equivalently ...
- 4,563
6
votes
2
answers
639
views
Max cut problem between two connected subgraphs
Let $G$ be a connected graph.
Consider the problem of finding a partition $G = A \cup B$ into connected subgraphs, so that the cut between $A$ and $B$ is maximized. Is there anything which is known ...
- 1,479
3
votes
1
answer
217
views
Tighter Probability Bounds
Let $\mathcal{F}$ be a class of binary functions on a probability space $\Omega$. For $f \in \mathcal{F}$, let $P(f) =\mathbb{E}(f(Z))$ and $P_n(f) = \frac{1}{n} \sum_{i=1}^n f(Z_i)$ where $Z_i$'s are ...
- 33
3
votes
1
answer
321
views
Literature reference for search-BPP
I'm trying to find the first article/paper that the complexity class search-BPP appeared in. Search-BPP, as defined as follows (in [1]):
A binary relation $R$ is in search-BPP if there is a ...
- 525
4
votes
2
answers
255
views
Extended version of the paper "Consistent Hashing and Random Trees" with proofs
I've been reading the following paper:
David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Mathew Levine, Daniel Lewin, "Consistent Hashing and Random Trees: Distributed Caching Protocols for ...
- 161
1
vote
0
answers
83
views
"conservative approximate Set Cover"?
We are given a lattice graph $L$, embedded on the plane, and a certain "shape" (a connected, acyclic subgraph $S$ of $L$).
The task is to approximately cover $L$ with translated, rotated and flipped ...
- 131
11
votes
2
answers
632
views
Lower bound on estimating $\sum_{k=1}^n a_k$ for non-increasing $(a_k)_k$
I'd like to know (related to this other question) if lower bounds were known for the following testing problem: one is given query access to a sequence of non-negative numbers $a_n \geq \dots\geq a_1$ ...
- 4,491
10
votes
2
answers
319
views
What is the minimum over all distributions of unit vectors of the variance of the dot product of the vectors?
I am trying to find a distribution over $n$ random vectors, say $x_1,\ldots, x_n$, on the $k$-dimensional unit sphere (where $n > k$) that minimizes $\max_{i\neq j} \mathrm{Var}(x_i^T x_j)$ subject ...
- 101
21
votes
1
answer
731
views
A flowchart for concentration bounds
When I teach tail bounds, I use the usual progression:
If your r.v is positive, you can apply Markov's inequality
If you have independence and also bounded variance, you can apply Chebyshev's ...
- 32.2k
2
votes
1
answer
159
views
Complexity of determining unique elements of each cycle in a permutation
It is a well known fact that a permutation is a set of cycles, and that one can find all cycles of a permutation in $O(n)$ time, where $n$ is the length of the permutation.
But suppose that we know ...
- 187
4
votes
0
answers
191
views
Randomized Parallel Algorithm for Maximal Independent Set
There are a couple of randomized parallel algorithms for the maximal independent set problem, e.g. A Simple Parallel Algorithm for the Maximal Independent Set Problem, A fast and simple randomized ...
- 1,338
7
votes
1
answer
678
views
Shortest paths perturbation
I have a graph $G=(V,E)$, with positive weights $w_e, e\in E$ on the edges, and I would like to randomly perturb the weights of the edges so that for each pair of distinct vertices $(u,v)$ such that ...
- 569
1
vote
2
answers
2k
views
Chernoff Bounds for settings with limited dependence
Could someone point me to a way of bounding the tail probability of sums of bernoulli variables each generated by the same distribution but the condition of independence is only partially satisfied. ...
- 666
5
votes
0
answers
229
views
Distributed algorithms on sets
Given a connected arbitrary network $G = (V,E)$, where $V$ is a set of nodes (processors) and $E$ is the set of edges between the nodes. Each node $v _i$ is assigned a non-empty set $S(v _i)$, where $\...
- 644
2
votes
1
answer
188
views
Independent iterations in Las Vegas algorithms
In [Randomized Algorithms, Motwani and Raghavan] book, it is stated that the method of independent iterations to reduce the error probability in Monte Carlo algorithms (amplification according to ...
- 644
28
votes
10
answers
3k
views
Probabilistic (randomized) algorithms before "modern" computer science appeared
Edit: I choice the answer with highest score by December 06, 2012.
This is a soft question.
The concept of (deterministic) algorithms dates back to BC. What about the probabilistic algorithms?
In ...
26
votes
1
answer
2k
views
Who first proposed using $x^2+y^2 < 1$ Monte Carlo algorithm to calculate Pi?
I'm sure everybody knows of Buffon's needle experiment in the 18th century, that is one of the first probabilistic algorithms to calculate $\pi$.
The implementation of the algorithm in computers ...
- 638
0
votes
1
answer
334
views
Maximum Independent Set using Maximal MIS
I want to use multiple runs of maximal independent set (Luby's algorithm) to find a lower bound on the size of maximum independent set.
Are there any bounds on the number of times the maximal ...
- 153
10
votes
1
answer
557
views
Determine the minimum number of coin-weighings
In the paper On two problems of information theory, Erdõs and Rényi give lower bounds on the minimum number of weighings one must do to determine the number of false coins in a set of $n$ coins.
...
- 746
2
votes
0
answers
483
views
Texts on application of randomized algorithms
as far as I know, Motwani & Raghavan, ”Randomized Algorithms”, Cambridge University Press, 1995 is the standard book for randomized algorithms. This is an excellent theoretical intro.
Which is ...
- 121
27
votes
1
answer
927
views
Other applications of Karger-Stein branching amplification?
I just taught the Karger-Stein randomized mincut algorithm in my graduate algorithms class. This is a real algorithmic gem, so I can't not teach it, but it always leaves me frustrated, because I don'...