We present two new probability inequalities which generalize the usual Hoeffding-Azuma inequality. The first simpler one replaces the absolute bound on the Martingale Differences by bounds on their moments. We use this to study traditional problems such as the TSP, but with more general Distributions. For example, for the TSP, we allow heavier tails and inhomogenity in the distribution. The second more complicated inequality allows the bounds on the moments to be violated occasionally. Using that we settle the long -studied concentration for bin-packing by proving the best possible bounds. We also derive the first sub-Gaussian tail bounds for the number of triangles in a sparse random graph.