Abstract
We introduce a subclass of NP optimization problems which contains, e.g., Bin Covering and Bin Packing. For each problem in this subclass we prove that with probability tending to 1 as the number of input items tends to infinity, the problem is approximable up to any given constant factor ε > 0 by a finite-state machine. More precisely, let II be a problem in our subclass of NP optimization problems, and let I be an input represented by a sequence of n independent identically distributed random variables with a fixed distribution. Then for any ε > 0 there exists a finite-state machine which does the following: On a random input I the finite-state machine produces a feasible solution whose objective value M(I) satisfies\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}
$$P\left( {\frac{{|Opt(I) - M(I)|}}{{\max \{ Opt(I),M(I)\} }} \geqslant \varepsilon } \right) \leqslant K\exp ( - hn)$$
\end{document}when n is large enough. Here K and h are positive constants.