<p>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.</p>

<p>I suggest looking through <a href="https://people.eecs.berkeley.edu/~luca/pcp/" rel="nofollow noreferrer">https://people.eecs.berkeley.edu/~luca/pcp/</a> if you are curious for more information in this direction.</p>

CC BY-SA 4.0
2020-04-22T19:05:30.630Z
2020-04-22T19:05:30.630Z
lacker
<p>Suppose we have a <code>NP-Hard</code> problem such as the <code>k-col</code>, which is meant to determine if a graph may be colored using at most <code>k</code> different colors.</p>

<p>Considering we model the <code>k-col</code> problem as a <code>linear programming</code> problem, then apply slightly random perturbations (<a href="https://arxiv.org/abs/cs/0111050" rel="nofollow noreferrer">Spielman and Teng - 2001</a>) to the input tableau for the <code>simplex</code> algorithm as mentioned <a href="https://cstheory.stackexchange.com/questions/2373/complexity-of-the-simplex-algorithm">here</a>, obtaining a problem very close to the original one:</p>

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

<p>PS:
Please, note I have considered <a href="https://cstheory.stackexchange.com/questions/17601/smoothed-analysis-of-approximation-algorithms">this</a> 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 <code>smoothed analysis</code> is related to the questions I've asked.</p>

<np-hardness><approximation-algorithms><optimization><linear-programming><approximation-hardness>
Is it possible to approximate the solution of NP-Hard problems in polynomial time using linear programming?
G Oliveira
# Is it possible to approximate the solution of NP-Hard problems in polynomial time using linear programming?

(Asked by: username_0 on 2020-04-22)

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](https://arxiv.org/abs/cs/0111050)) to the input tableau for the `simplex` algorithm as mentioned [here](https://cstheory.stackexchange.com/questions/2373/complexity-of-the-simplex-algorithm), 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](https://cstheory.stackexchange.com/questions/17601/smoothed-analysis-of-approximation-algorithms) 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.

**Tags:** np-hardness, approximation-algorithms, optimization, linear-programming, approximation-hardness


---

## 1 answers

### Answer by username_1 on 2020-04-22. Score: 0 | Accepted answer

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.


---

