Probabilistic approximation of some NP optimization problems by finite-state machines TeX Export

@incollection{citeulike:1916019, 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 \$\$P\left( {\frac{{|Opt(I) - M(I)|}}{{\max \{ Opt(I),M(I)\} }} \geqslant \varepsilon } \right) \leqslant K\exp ( - hn)\$\$}, author = {Hong, Dawei and Birget, Jean-Camille}, citeulike-article-id = {1916019}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/3-540-63248-4_13}, doi = {10.1007/3-540-63248-4_13}, journal = {Randomization and Approximation Techniques in Computer Science}, keywords = {computational\_complexity, finite\_automata, np\_completeness, optimization}, pages = {151--164}, posted-at = {2007-11-14 21:12:24}, priority = {2}, title = {Probabilistic approximation of some NP optimization problems by finite-state machines}, url = {http://dx.doi.org/10.1007/3-540-63248-4_13}, year = {1997} }

TY - CHAP ID - citeulike:1916019 L3 - citeulike-article-id:1916019 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 $$P\left( {\frac{{|Opt(I) - M(I)|}}{{\max \{ Opt(I),M(I)\} }} \geqslant \varepsilon } \right) \leqslant K\exp ( - hn)$$ JF - Randomization and Approximation Techniques in Computer Science EP - 164 TI - Probabilistic approximation of some NP optimization problems by finite-state machines SP - 151 KW - computational_complexity KW - finite_automata KW - np_completeness KW - optimization AU - Hong, Dawei AU - Birget, Jean-Camille PY - 1997/// UR - http://dx.doi.org/10.1007/3-540-63248-4_13 ER -