New answers tagged


We confirm @YonatanN's conjecture: Lemma 1. There is always an optimal solution $v'$ such that, for some $i'$, $|v_{i'}' - v_{i'}| = k$, while $v'_i = v_i$ for all $i\ne i'$. @YonatanN's suggested algorithm (try all possible such solutions and choose the best) will give the following corollary: Corollary 1. There is a polynomial-time algorithm for the ...

Top 50 recent answers are included