-1
$\begingroup$

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:

  1. may it be solved in polynomial time ?
  2. in practice, may it be solved optimally for a huge graph (1k vertices or more) or would the solution be a near-optimum ?

PS: 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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

I'm not exactly sure what algorithm you suggest, but in general it is known there are many NP-hard problems that are also NP-hard to approximate. So I don't think this line of attacking NP-hard problems is going to lead you to success in polynomial time.

I suggest looking through https://people.eecs.berkeley.edu/~luca/pcp/ if you are curious for more information in this direction.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.