Approximation of some NP-hard optimization problems by finite machines, in probability

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)323-339
Number of pages17
JournalTheoretical Computer Science
Volume259
Issue number1-2
DOIs
StatePublished - Aug 4 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

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

Fingerprint Dive into the research topics of 'Approximation of some NP-hard optimization problems by finite machines, in probability'. Together they form a unique fingerprint.

  • Cite this