Martingale inequalities and NP-complete problems. (English) Zbl 0718.60040
Azéma’s exponential martingale inequality [see e.g., W. F. Stout, Almost sure convergence (1974; Zbl 0321.60022)] is shown to have many applications in the analysis of problems in operations research and computer science. These include the bin-packing problem and the traveling salesman problem. Typically, upper bounds are obtained for \(P(| U_ n-EU_ n| >t)\) where \(U_ n\) is an objective function value. In particular, probability inequalities are given that complement results of J. M. Steele [Math. Oper. Res. 6, No.3, 374-378 (1981; Zbl 0496.90078)] regarding the tour length of the traveling salesman tour defined on n i.i.d. points uniformly distributed on the unit square.
MSC:
60G42 | Martingales with discrete parameter |
68Q25 | Analysis of algorithms and problem complexity |
90B15 | Stochastic network models in operations research |
90C10 | Integer programming |