<p>Fernandez de la Vega and Karpinski in their paper <em>9/8-approximation algorithm for 
random max-3sat</em> give, as the title suggests, such an algorithm under the uniform distribution over 3sat clauses. Håstad showed that no deterministic 7/8 approximation algorithms exists for max-3sat (unless ...)</p>

<p>I don't know of any clear-cut decision problems, i.e. ones where the algorithm beats an inapproximability result for an optimization problem.</p>

CC BY-SA 2.5
2010-08-30T16:52:27.033Z
2010-08-30T16:52:27.033Z
Pall Melsted
<p>Many NP-complete or NP-hard problems are addressed under the assumption that the problem instances are uniformly distributed. However, it is not true for real world applications. One example is the SAT problem. Randomly generated SAT problems are greatly different from industry collected SAT problems. The solvers behave quite different.</p>

<p>I am thinking about an approximation scheme that given an unknown distribution $D$ over the problem instances, there exists a polynomial time algorithm $A$ that solves the problems drawn from $D$ successfully with a probability $1-\eta$. $\eta$ somehow relates to the divergence between the $D$ and the random distribution.</p>

<p>Furthermore, if we have samples from $D$, we can estimate $A$, and address the sample complexity and the consistency issue. </p>

<p>I wonder whether such a scheme already exists or not. If so, what is the name and what are the milestones?</p>

CC BY-SA 3.0
2012-08-02T15:12:31.003Z
Are you looking for [Smoothed Analysis](http://www.cs.yale.edu/homes/spielman/SmoothedAnalysis/framework.html)?
Radu Curticapean
CC BY-SA 2.5
2010-08-30T21:31:38.303Z
“Many NP-complete or NP-hard problems are addressed under the assumption that the problem instances are uniformly distributed.”  I have difficulty understanding the meaning of this sentence.  Are you saying that some (many?) NP-complete problems are known to be _easy_ on average, or that some (many?) problems are known to be _hard_ on average, or something else?
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-07T18:05:48.710Z
Taking the kSAT as an example, you randomly generate 10,000 kSAT problems (literals and clauses), then apply several solvers to determine if they are Satisfiable. The literals and clauses form a problem space. The conventional algorithm theory concerns about the worst case running time for the entire problem space no matter if it is exact or approximate.
miao
CC BY-SA 2.5
2010-09-07T18:14:37.033Z
However, we never look at the distribution of problem instances on the problem space. In real world, the distribution of problem instances are quite different than randomly generated ones. Therefore, prioritizing the algorithm operations according to the real distribution might produce a Poly time performance.
miao
<cc.complexity-theory><approximation-algorithms>
High probable polynomial time algorithm for NP-hard problems?
miao
# High probable polynomial time algorithm for NP-hard problems?

(Asked by: username_0 on 2010-08-24)

Many NP-complete or NP-hard problems are addressed under the assumption that the problem instances are uniformly distributed. However, it is not true for real world applications. One example is the SAT problem. Randomly generated SAT problems are greatly different from industry collected SAT problems. The solvers behave quite different.

I am thinking about an approximation scheme that given an unknown distribution $D$ over the problem instances, there exists a polynomial time algorithm $A$ that solves the problems drawn from $D$ successfully with a probability $1-\eta$. $\eta$ somehow relates to the divergence between the $D$ and the random distribution.

Furthermore, if we have samples from $D$, we can estimate $A$, and address the sample complexity and the consistency issue.

I wonder whether such a scheme already exists or not. If so, what is the name and what are the milestones?

**Tags:** cc.complexity-theory, approximation-algorithms

> **Comments:**
> **username_2**: “Many NP-complete or NP-hard problems are addressed under the assumption that the problem instances are uniformly distributed.”  I have difficulty understanding the meaning of this sentence.  Are you saying that some (many?) NP-complete problems are known to be _easy_ on average, or that some (many?) problems are known to be _hard_ on average, or something else?  
> **username_0**: Taking the kSAT as an example, you randomly generate 10,000 kSAT problems (literals and clauses), then apply several solvers to determine if they are Satisfiable. The literals and clauses form a problem space. The conventional algorithm theory concerns about the worst case running time for the entire problem space no matter if it is exact or approximate.  
> **username_0**: However, we never look at the distribution of problem instances on the problem space. In real world, the distribution of problem instances are quite different than randomly generated ones. Therefore, prioritizing the algorithm operations according to the real distribution might produce a Poly time performance.  
> **username_1**: Are you looking for [Smoothed Analysis](http://www.cs.yale.edu/homes/spielman/SmoothedAnalysis/framework.html)?  

---

## 1 answers

### Answer by username_3 on 2010-08-30. Score: 5

Fernandez de la Vega and Karpinski in their paper *9/8-approximation algorithm for
random max-3sat* give, as the title suggests, such an algorithm under the uniform distribution over 3sat clauses. Håstad showed that no deterministic 7/8 approximation algorithms exists for max-3sat (unless ...)

I don't know of any clear-cut decision problems, i.e. ones where the algorithm beats an inapproximability result for an optimization problem.


---

