# Linear order minimizing weighted distance from special element

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?