Martingale Inequalities, Interpolation and NP-Complete Problems
Published Online:1 Feb 1989https://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.
