Before revision:  They are in fact extremely challenging combinatorial optimization problems, since we cannot impose any restriction on the  outliers.
After revision:  They are in fact extremely challenging combinatorial optimization problems, since we cannot impose any restriction on the adversarial outliers.