Martingale Inequalities, Interpolation and NP-Complete Problems
- 1 February 1989
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 14 (1) , 91-96
- https://doi.org/10.1287/moor.14.1.91
Abstract
In a previous work (Rhee, W., Talagrand, M. 1987. Martingale inequalities and NP-complete problems. Math. Oper. Res. 12(1) 177–181.), we showed how to use martingale inequalities in the probabilistic analysis of stochastic models of NP-complete problems to obtain sharp bounds on P(|Un − E(Un)| ≥ t), where Un is the objective function value of the problem with n random data. Here, we show how to interpolate between martingale inequalities to obtain even sharper bounds.Keywords
This publication has 0 references indexed in Scilit: