New answers tagged ds.algorithms
2
In computer algebra, this computation is usually referred as computing the subproduct tree and is a subroutine of multipoint evaluation and interpolation. See for instance: von zur Gathen, Gerhard. Modern Computer Algebra, 3rd edition, 2013 [chapter 10]. As far as I know, the best known complexity is $O(\mathsf{M}(n)\log n)$ where $\mathsf M(n)$ denotes the ...
5
Yes, there are many such algorithms. Two of the easiest are
(1) Use Borůvka's algorithm, where each vertex finds its minimum-weight outgoing edge, you form trees from selected edges, collapse each tree to a supervertex, and repeat. But modify it so that after the collapse you return to a simple graph rather than a multigraph. To do so, use radix sort to sort ...
2
Let $opt^{*}(P_{1})$, $opt^{*}(P_{2})$, and $opt^{*}(P)$ denote the optimal $1$-median costs of $P_{1}$, $P_{2}$, and $P$, repsectively.
We show that $\hat{opt} \leq 3 \cdot opt^{*}(P)$ using the following sequence of inequalities:
\begin{align}
\hat{opt} &\leq opt^{*}(P_{1}) + opt^{*}(P_{2}) + n \cdot d(c_{1}^{*},\hat{c}) + n \cdot d(c_{2}^{*},\hat{c}) ,...
Top 50 recent answers are included