5
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ “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? $\endgroup$
    – Tsuyoshi Ito
    Aug 30, 2010 at 21:31
  • $\begingroup$ 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. $\endgroup$
    – miao
    Sep 7, 2010 at 18:05
  • $\begingroup$ 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. $\endgroup$
    – miao
    Sep 7, 2010 at 18:14
  • $\begingroup$ Are you looking for Smoothed Analysis? $\endgroup$
    – Radu Curticapean
    Aug 2, 2012 at 15:12

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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