Questions related to design and analysis of algorithms
12
votes
0answers
154 views
How does the runtime of the Ukkonen's algorithm depend on the alphabet size?
I am concerned with the question of the asymptotic running time of the Ukkonen's algorithm, perhaps the most popular algorithm for constructing suffix trees in linear (?) time.
Here is a citation ...
10
votes
0answers
231 views
Towers of Hanoi but with arbitrary initial and final configuration
Recently, I came across this problem, a variation of towers of hanoi.
Problem statement:
Consider the folowing variation of the well know problem Towers of
Hanoi:
We are given $n$ towers ...
10
votes
0answers
180 views
Approximate minimum-weighted tree decomposition on complete graphs
Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By ...
9
votes
0answers
212 views
distributed alpha beta pruning
I am looking for an efficient algorithm that lets me process the minimax search tree for chess with alpha-beta pruning on a distributed architecture. The algorithms I have found (PVS, YBWC, DTS see ...
8
votes
0answers
113 views
Theoretical foundations of Divide and Conquer
When it comes to the design of algorithms, one often employs the following techniques:
Dynamic Programming
The Greedy-Strategy
Divide-and-Conquer
While for the first two methods, there are ...
7
votes
0answers
122 views
FFT-less $O(n\log n)$ algorithm for pairwise sums
Suppose we are given $n$ distinct integers $a_1, a_2, \dots, a_n$, such that $0 \le a_i \le kn$ for some constant $k \gt 0$, and for all $i$.
We are interested in finding the counts of all the ...
7
votes
0answers
134 views
Alternatives to SVD for rank factorization
I have rank-deficient matrix $M \in \mathbb{R}^{n\times m}$ with $\text{rank}(M) = k$ and I want to find a rank factorization $M = PQ$ with $P \in \mathbb{R}^{n \times k}$ and $Q \in \mathbb{R}^{k ...
7
votes
0answers
130 views
Problems for which algorithms based on partition refinement run faster than in loglinear time
Partition refinement is a technique in which you start with a finite set of objects and progressively split the set. Some problems, like DFA minimization, can be solved using partition refinement ...
6
votes
0answers
59 views
numerical integral vs counting roots
I have a problem that can be viewed in two different ways:
Compute an $n$-dimensional integral, numerical context. The domain of integration is an $n$-dimensional hyper-cube of side $L$.
Count (just ...
6
votes
0answers
85 views
How to distribute items of varying sizes into bins of varying sizes, such that percent utilization across all bins is minimized?
I have a bunch of databases, each having different access patterns, such that each puts a different amount of load on its database cluster. I would like to distribute them around my set of database ...
6
votes
0answers
58 views
Fixed-length decision-tree-like feature selection to minimize average search performance
I have a complex query $Q$ used to search a dataset $S$ to find $H_\text{exact} = \{s \in S \mid \text{where $Q(s)$ is True}\}$. Each query takes on average time $t$ so the overall time in the linear ...
6
votes
0answers
108 views
Fast algorithm for max-convolution with concave functions?
I'm interested in a discrete max-convolution problem, which is to compute
$$r(c) = \max_{x | x \ge 0, \sum_k x_k = c} \left[ \sum_{k=1} f_k(x_k) \right] $$
for all values $c=0, \ldots, C$, where ...
6
votes
0answers
63 views
What is the proof for the lemma “For every iteration of the Gomory-Hu algorithm, there is a representant pair for each edge”?
For a given undirected graph $G$, a Gomory-Hu tree is a graph which has the same nodes as $G$, but its edges represent the minimal cut between each pair of nodes in $G$. The Gomory-Hu algorithm finds ...
6
votes
0answers
406 views
Area of the union of rectangles anchored on the x-axis
I am trying to solve the following computational geometry problem.
Let $S$ be a set of $n$ axis-parallel rectangles in the plane, so that the bottom edge of each rectangle in $S$ lies on the ...
6
votes
0answers
210 views
Weighted Maximum 3-DIMENSIONAL-MATCHING with restricted weights (Approx Algo)
If the weights of the weighted 3-DIMENSIONAL-MATCHING problem are restricted to let's say, 1 and 2, is there a possibility to reduce this case to the unweighted 3-DIMENSIONAL-MATCHING problem?
...
