New answers tagged

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