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?