B_i + \|\bc_{q_i} - \hat{\bc}_{q_i} \|_p \\ LB_i(\bc) &amp; \leftarrow LB_i(\bc) - \|\bc -\hat \bc\|_p. \end{align*}
</p>
<p>Thus the K-means algorithm becomes:</p>
<ol type="1">
<li><b>Initialization.</b> Compute \(LB_i(\bc) = \|\bx_i -\hat \bc\|_p\) for all points and centers. Find the current assignments \(q_i\) and bounds \(UB_i\) by finding the closest centers to each point: \(UB_i = \min_{\bc} LB_i(\bc)\).</li>
<li><b>Center estimation.</b><ol type="a">
<li>Recompute all the centers based on the new m