Let's say I have a set of beads, $b_0,\dots,b_n$, and let $b_0$ be the 'special bead'. I want to lay out the beads on a string to minimize the total cost, defined as $\sum_{i=1}^n w_i \cdot d(b_0, b_i)$, where the weights $w_i$ are given, and the distance is computed as the number of beads between the two corresponding beads.

The minimum cost for every position of $b_0$ can be calculated in linear total time (plus $n \log n$ pre-processing time to sort the weights), by noting that the optimal solution is to pair up the beads on either side by increasing weight, with a residual 'tail' on the longer side, and working out how the cost changes as you shift $b_0$ along.

What if some of $b_1,\dots,b_n$ are fixed in given positions?

Obviously quadratic time is possible by solving each sub-problem independently, but is there an incremental algorithm akin to the case without any fixed beads?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.