Minimizing the sum of absolute deviations and applications