New answers tagged optimization
2
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