TY - GEN
T1 - Probabilistic approximation of some NP optimization problems by finite-state machines
AU - Hong, Dawei
AU - Birget, Jean Camille
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1997.
PY - 1997
Y1 - 1997
N2 - 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 (Formula Presented)when n is large enough. Here K and h are positive constants.
AB - 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 (Formula Presented)when n is large enough. Here K and h are positive constants.
KW - Approximation
KW - Finite-state machines
KW - NP- optimization problems
KW - Probabilistic algorithms
UR - http://www.scopus.com/inward/record.url?scp=84957626112&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84957626112&partnerID=8YFLogxK
U2 - 10.1007/3-540-63248-4_13
DO - 10.1007/3-540-63248-4_13
M3 - Conference contribution
AN - SCOPUS:84957626112
SN - 3540632484
SN - 9783540632481
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 151
EP - 164
BT - Randomization and Approximation Techniques in Computer Science - International Workshop, RANDOM 1997, Proceedings
A2 - Rolim, José
PB - Springer Verlag
T2 - International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 1997
Y2 - 11 July 1997 through 12 July 1997
ER -