### Abstract

We introduce a subclass of NP optimization problems which contains some NP-hard problems, e.g., bin covering and bin packing. For each problem in this subclass we prove that with probability tending to 1 (exponentially fast as the number of input items tends to infinity), the problem is approximable up to any chosen relative error bound ε > 0 by a deterministic finite-state machine. More precisely, let Π be a problem in our subclass of NP optimization problems, let ε > 0 be any chosen bound, and assume there is a fixed (but arbitrary) probability distribution for the inputs. Then there exists a finite-state machine which does the following: On an input I (random according to this probability distribution), the finite-state machine produces a feasible solution whose objective value M(I) satisfies P(|Opt(I)-M(I)|/max{Opt(I),M(I)}≥ε)≤Ke^{-hn}, when n is large enough. Here K and h are positive constants.

Original language | English (US) |
---|---|

Pages (from-to) | 323-339 |

Number of pages | 17 |

Journal | Theoretical Computer Science |

Volume | 259 |

Issue number | 1-2 |

DOIs | |

State | Published - Aug 4 2001 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

### Keywords

- Approximation
- Finite-state machines
- NP-optimization problems
- Probabilistic analysis of algorithms