Questions tagged [randomized-algorithms]

Questions about algorithms whose behaviour is determined not only by its input but also by a source of random numbers.

Filter by
Sorted by
Tagged with
2
votes
1answer
47 views

Question on an Algorithm for Longest Increasing Subsequence

I have been reading this paper: https://arxiv.org/abs/2011.10874 This paper presented an exact randomized algorithm with update time $\tilde{O}(n^{0.8})$. I will quickly talk about the overall idea of ...
0
votes
0answers
21 views

Proving an algorithm satisfies $\epsilon$-DP

I am trying to prove/disprove that an algorithm satisfies $\epsilon$-DP. I proved some of them but there are 3 more which I could not decide on. Here they are: Algorithm A takes as input a dataset D ...
0
votes
1answer
109 views

Algorithmic challenge: generate a list of random non overlapping squares

For an undisclosed reason, I need a list of $n$ squares in a two dimensions space where each square does not overlap. So the challenge is simply: given a two dimensional area $a$ (...
2
votes
1answer
38 views

2-Approximation algorithm for for messages across a cyclic network

Question There are $n$ computers arranged in a cycle ($1,2,3..,n,1$), with undirected edges between adjacent computers. There are $m$ messages that need to be delivered. Message $i$ ($1 \le i \le m$) ...
2
votes
1answer
28 views

Question in coreset construction fro K-median clustering

I was reading Ke chen's paper about coreset construction for K-median clustering. In this paper, he assumed that $A$ is an $[α, β]$-bicriteria approximation for K-median clustering for some $α, β=O(1)$...
1
vote
1answer
25 views

Definition of BPP

We know that BPP is described as $\{L\mid \exists \text{ TM }M, \text{ s.t. }\Pr[M(x)=L(x)]\geq2/3\}$. I saw a proof which uses Chernoff bound to prove that any probability larger than $1/2$ can be ...
2
votes
1answer
43 views

Algorithm for cyclic $n$-string Hamming distance with constant sized language $\Sigma$

Suppose we are given a language $\Sigma$ where, suppose, $|\Sigma| = O(1)$. Consider two fixed strings $A, B \in \Sigma^n$. Define the Hamming metric between these strings as $$d_{H}(A,B) = \sum_{i=1}^...
0
votes
0answers
30 views

Let M be a k × n random matrix with iid entries such that

$M$ is a $k × n$ random matrix with iid entries such that $P(m_{i,j} = +1) = P(m_{i,j} = −1) = 0.5.$ Let $k = O({1\over \epsilon^l})$ for some constant $l$. $v ∈ R_n$ is a fixed vector. Does a ...
0
votes
0answers
21 views

The observation of the coreset in K-median clustering problems [duplicate]

I have seen two observations from the paper by Har-Peled but I do not know how to prove them (i) If $C1$ and $C2$ are the $(k, ε)$-coresets for disjoint sets P1 and P2 respectively, then $C1 ∪ C2$ is ...
0
votes
2answers
61 views

About the properties of the coresets in k-median clustering

I have seen two observations from the paper by Har-Peled but I do not know how to prove them (i) If $C1$ and $C2$ are the $(k, ε)$-coresets for disjoint sets P1 and P2 respectively, then $C1 ∪ C2$ is ...
0
votes
1answer
41 views

Existence of Pseudorandom Generator

How to show that for $\epsilon>0$, there exists a function $G:\{0,1\}^n->\{0,1\}^{2^{\epsilon n}}$ that is a $2^{\epsilon n}$-prg, without the condition that is is computable in $2^{O(n)}$ time. ...
1
vote
1answer
57 views

derandomize a BPP algorithm

Suppose we have a BPP algorithm $A$ s.t. its running time is random and is $O(n^2)$ in expectation. How do we create a new BPP algorithm $B$ to solve the same problem s.t. it has deterministic running ...
2
votes
1answer
36 views

Generate a uniform random numbers in $O(1)$

Suppose you have access to a random number generator $G()$ that generates uniform random numbers in $\{0,\cdots,n-1\}$. (Here, $n$ is given and cannot be changed.) How do we generate a uniform random ...
2
votes
0answers
42 views

Randomized Assignment Problem

Given $x_1,...,x_n,y_1,...,y_n\in \mathbb{R}^d$ find a permutation matrix $P\in\mathbb{S}_d$ that minimizes $\sum_{ij}P_{ij}|x_i-y_j|$. This is an assignment problem and can be solved in $O(n^3+n^2d)$ ...
0
votes
2answers
37 views

Maximization problem

I work at a company and i got to a seminar we're they told us to solve this problem below in the picture Is there an algorithm that can help me solve this question. I thought about a randomized ...
0
votes
1answer
20 views

Randomly generating graph based off number of connections on each node

I'm trying to generate a graph based off some data I have. This graph should have N nodes where the number of edges each node has is equal to a random number ...
1
vote
1answer
46 views

Efficiently selecting a random subset of size $m$ from a set of size $n$

This is a cross post of my question here on math.se. I have a list of $n$ items and would like to randomly select an $m$ set from it efficiently (in terms of time complexity). Also, I want all ...
1
vote
0answers
23 views

Distributional error probability of deterministic algorithm implies error probability of randomized algorithm?

Consider some problem $P$ and let's assume we sample the problem instance u.a.r. from some set $I$. Let $p$ be a lower bound on the distributional error of a deterministic algorithm on $I$, i.e., ...
1
vote
1answer
30 views

Median of distribution with memory constraint

Task I want to approximate the median of a given distribution $D$ that I can sample from. A simple algorithm for this, using $n$ samples, is: ...
3
votes
3answers
195 views

Book recommendations on the analysis of randomized algorithms

I would like to read some books (or any other material) that cover the design of randomized algorithms with a particular focus on the analysis. My main goal is to develop the rigour needed to ...
3
votes
1answer
185 views

Weighted Online Matching - randomized algorithms

Let's consider the edge weighted online matching problem. The Vertices arrive online and reveal all their current edges and edge-weights $w_e>0$. The goal is to maximize the matchings weight. An ...
0
votes
0answers
22 views

Analyzing a counting triangles streaming algorithm which uses $\ell_0$ sampling

I'm trying to analyze the following streaming algorithm for counting triangles (see below). It supposedly works also for dynamic graphs (i.e. "turnstile model", where edge deletions are ...
2
votes
1answer
113 views

Is any randomized Algorithm a probability distribution over the set of deterministic Algorithms?

If there is a finite set of Instances of size n and the set of (reasonable) deterministic algorithms is finit. Can any randomized Algorithm be seen as a probability distribution over the set of ...
2
votes
1answer
121 views

Randomized Algorithms: High-Probability vs. Expectation

Hopefully this question isn't too general, but I was wondering what the relationship is between randomized algorithms that perform well with high-probability and those that perform well in expectation....
1
vote
0answers
23 views

Space complexity of using a pairwise independent hash family

I'm trying to analyze the space complexity of using the coloring function $f$ which appears in "Colorful Triangle Counting and a MapReduce Implementation", Pagh and Tsourakakis, 2011, https:...
2
votes
1answer
78 views

Returning random integer from interval based on last result and a seed

Suppose we have an interval of integers [a, b]. I would like to have a function that returns random members from within the interval, without repetitions. Once that all members within the interval are ...
2
votes
1answer
40 views

Streaming algorithm for counting triangles in a graph

As described in the reference, the algorithm (see at the bottom) supposes to output an estimator $\hat T$ for the # of triangles in a given graph $G = (V, E)$, denoted $T$. It is written that "it ...
0
votes
1answer
46 views

1-sparse recovery algorithm

In the reference below, a 1-sparse recovery algorithm over a vector $a \in R^n$ is defined as follows. My question is why do we need the modulus (i.e. $x \mod p$)? Algorithm: Keep track of $$ \...
1
vote
1answer
27 views

Purpose of randomization/derandomization in basic randomized algorithm for MAX SAT

In Sections 5.1 of The Design of Approximation Algorithms by Williamson and Shmoys, they describe a basic randomized algorithm for MAX SAT and how to derandomize it. The algorithm is just to assign ...
2
votes
1answer
37 views

Confusion about the Hiring Problem

I'm confused about where the probability from the hiring problem comes from. For background: We interview one person everyday who has a quality characteristic, x, from 0 to 1(distributed uniformly). ...
1
vote
1answer
33 views

When does a Monte Carlo algorithm solve a problem?

When can we say that a Monte Carlo algorithm solves a problem? To quote from Wikipedia on Monte Carlo algorithms For instance, the Solovay–Strassen primality test is used to determine whether a ...
0
votes
0answers
22 views

Lectures and books for beginner to approach learning simulations

I'm an incoming undergrad with a math background up to single-variable calculus, but reasonably strong programming background through algorithms, data structures, web and mobile app development. ...
4
votes
1answer
50 views

Marginal Probability of Generating a Tree

Fix some finite graph $G = (V, E)$, and some vertex $x$. Suppose I generate a random sub-tree of $G$ of size $N$, containing $x$, as follows: Let $T_0 = \{ x \}$. For $0 < n \leqslant N$ i. Let ...
1
vote
0answers
51 views

How to estimate the number of elements inserted to a Bloom filter

A Bloom filter is a probabilistic data structure that allows encoding sets with false positives. Parameterized by the number of bits $m$ in the array $A$ (initialized to zeros), and number of hash ...
1
vote
1answer
33 views

Is there an efficient algorithm for determining the probability a large randomly chosen integer is not divisible by any integer of some set?

Given a set of 10 integers $A = a_1, a_2, \cdots a_{10}$, is there an efficient algorithm which can tell me what's the probability a randomly chosen integer between $1$ and $10^{10}$ is NOT divisible ...
2
votes
1answer
69 views

Flip-based algorithm for Delaunay triangulation in expected or average-case O(nlogn)

Focusing on the 2D plane: Lawson's Flip Algorithm works in worst-case $O(n^2)$ flips. I have seen it mentioned that (other?) flip-based algorithms work in expected $O(nlogn)$ time for two dimensions. ...
1
vote
0answers
34 views

Heuristic algorithm for the minimum weighted s-t cut with linear running time

To the best of my knowledge, the best algorithm for the minimum s-t cut in a weighted digraph is the Goldberg push-relabel algorithm with $O(n^{2}\sqrt{m})$ time complexity. I'm interested in solving ...
1
vote
1answer
137 views

Analyzing a randomized algorithm for finding an approximate median of an array

I'm given an array $A$ = ($a_1, a_2, \cdots a_n$), where n is uneven. For an element $a_i$ we denote its position in the array with $p(a_i)$. This element would be an $ε$-approximate median of the ...
1
vote
2answers
499 views

Probability that two elements are compared in randomized quicksort

I am having an issue in a specific part of the randomized quick-sort analysis. As per the randomized quick-sort algorithm the pivot is chosen from the given subset on which it is called from a random ...
1
vote
1answer
77 views

Amount of expected loop iterations when searching an array by random index

Lets say we have an array A of size n. It has 1 as its first index and n as its last index. It contains a value x, with x occurring k times in A where 1<=k<=n If we have a search algorithm like ...
4
votes
2answers
978 views

Generating random words by grammar

A bit of context I was writing a parser for a grammar, and for testing purposes I come up with idea to generate some random inputs. The grammar I was dealing with was much more complicated, in this ...
1
vote
0answers
23 views

An algorithm which efficiently generates random samples without replacement, from a large range [0-N], N ~ 10^12?

I want an algorithm which generates random integers, without replacement, from a large range [0-N], N~10^12. However, the whole range should not be stored in memory. The memory footprint should be O(...
1
vote
1answer
40 views

Color coding to get an FPT algoirthm for $k$ disjoint triangles

Consider the following problem: Input: A graph $G=(V,E)$ and an integer $k \in \mathbb{N}$ Output: Are there $k$ vertex-disjoint triangles in $G$? Assume we want to use color coding to develop an FPT ...
2
votes
1answer
50 views

Set which is easy to sample, but difficult to sample from its complement

Given a set $S \subseteq \{0,1\}^*$, the algorithm $A$ is a generator for $S$ if given $n$ random bits $x \in \{0,1\}^n$, $A$ generates an element of $S$ of size $n$, and $A$ can generate at least $\...
2
votes
1answer
38 views

If I walk through list and delete every out-of-order element I come across, on average how many elements will be left?

I have a uniformly randomly permuted list of length $n$. I walk through the list element-by-element, and delete an element if it's out-of-order (compared to the previous in-order elements of the list)....
3
votes
1answer
594 views

Expected length of a random walk on a line

I am given the following randomized algorithm for SAT, Input: A satisfiable CNF-formula $\varphi$. Output: An assignment $\rho$, such that $\rho \models \varphi$. The algorithm works as follow: ...
8
votes
0answers
125 views

Compute the expected size of an approximation of vertex cover

Consider the following randomized approximation algorithm of vertex cover: Input: A graph G = (V, E). Output: A set $C_G \subseteq V$ a vertex cover of $G$. The algorithm: Set $C_G := \emptyset$. ...
1
vote
1answer
181 views

Error lower-bound for an algorithm for vertex cover

I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set: Fix some order $e_1, e_2, . . . , e_m$ over all edges in the edge set E of G, and set $B_0 = \...
3
votes
1answer
44 views

Given an unsorted list of $n$ items, how many random comparisons are needed on average to be able to sort the list?

There is an unsorted list of $n$ items $x_1, \ldots, x_n$. Until you can sort the list, you are given one of the ${n \choose 2}$ possible binary comparisons uniformly at random (with replacement). On ...
1
vote
0answers
37 views

Finding a node in a binary tree by looking at the path between it and the root

There is a directed binary tree as shown in the picture (all edges are diercted from higher- to lower-level nodes). In that tree there is some specific unknown node $s$. All nodes in the $(s, root)$ ...

1
2 3 4 5
7