  Concentration results and probabilistic analysis for combinatorial problems
like the TSP, MWST, graph coloring have received much attention, but generally,
for i.i.d. samples (i.i.d. points in the unit square for the TSP, for example).
Here, we prove two probability inequalities which generalize and strengthen
Martingale inequalities. The inequalities provide the tools to deal with more
general heavy-tailed and inhomogeneous distributions for combinatorial
problems. We prove a wide range of applications - in addition to the TSP, MWST,
graph coloring, we also prove more general results than known previously for
concentration in bin-packing, sub-graph counts, Johnson-Lindenstrauss random
projection theorem. It is hoped that the strength of the inequalities will
serve many more purposes.
