High probable polynomial time algorithm for NP-hard problems? 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?
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.