Martingale Inequalities and NP-Complete Problems

1 February 1987

journal article
Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research

Vol. 12 (1) , 177-181
https://doi.org/10.1287/moor.12.1.177

Abstract

We use martingale inequalities in the probabilistic analysis of stochastic models of NP-complete problems. We give examples of applications to the Bin Packing and Traveling-Salesman Problems. In both cases, we obtain sharp bounds on Pr(|U_n − EU_n| > t), where U_n is the objective function value of the problem with n random data.

Keywords

INEQUALITIES
MARTINGALE
NP COMPLETE
COMPLETE PROBLEMS
FUNCTION
MODELS
PROBABILISTIC
BIN

This publication has 0 references indexed in Scilit: