A concentration inequality for random combinatorial optimisation problems

2024/07/17 by Joel Larsson Danielsson, Danielsson, Joel Larsson
Computer Science · Engineering · #60C05 #Combinatorics (math.CO) #Data Management and Algorithms #FOS: Mathematics #Optimization and Packing Problems #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2407.12672

openalex publication_date 2024/07/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a finite set S, i.i.d. random weights \X_i\_{i∈ S}, and a family of subsets F⊆ 2^S, we consider the minimum weight of an F∈ F: M(F):= min_{F∈ F} ∑_{i∈ F}X_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).

Related

• Concentration inequalities for smooth random fields
• The concentration inequality for a discrete height function model perturbed by random potential
• The convex distance inequality for dependent random variables, with applications to the stochastic travelling salesman and other problems
• A Bound on the Expected Optimality of Random Feasible Solutions to Combinatorial Optimization Problems
• Computational Concentration of Measure: Optimal Bounds, Reductions, and More