Suppose we have a
NP-Hard problem such as the
k-col, which is meant to determine if a graph may be colored using at most
k different colors.
Considering we model the
k-col problem as a
linear programming problem, then apply slightly random perturbations (Spielman and Teng - 2001) to the input tableau for the
simplex algorithm as mentioned here, obtaining a problem very close to the original one:
- may it be solved in polynomial time ?
- in practice, may it be solved optimally for a huge graph (1k vertices or more) or would the solution be a near-optimum ?
Please, note I have considered this before posting this question, however, I still didn't understand, therefore, I would like to see an answer in simpler words. In addition, I'm not sure if
smoothed analysis is related to the questions I've asked.