A concentration inequality for random combinatorial optimisation problems

Given a finite set S, i.i.d. random weights ᵢ∈ S, and a family of subsets F⊆ 2S, we consider the minimum weight of an F∈ F: \[ M(F):= minF∈ F ∑i∈ FX_i. \] In particular, we investigate under what conditions this random variable is sharply concentrated around its mean. We define the patchability of a family F: essentially, how expensive is it to finish an almost-complete F (that is, F is close to F in Hamming distance) if the edge weights are re-randomized? Combining the patchability of F, applying the Talagrand inequality to a dual problem, and a sprinkling-type argument, we prove a concentration inequality for the random variable M(F).