2023/09/22 by Dylan J. Altschuler, Altschuler, Dylan J.
Mathematics · Engineering · #Mathematical Approximation and Integration #Point processes and geometric inequalities #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.2309.13133
We introduce a general random model of a combinatorial optimization problem with geometric structure that encapsulates both linear programming and integer linear programming. Let Q be a bounded set called the feasible set, E be an arbitrary set called the constraint set, and A be a random linear transform. We define and study the ℓq-margin, Mq := dq(AQ, E). The margin quantifies the feasibility of finding y ∈ AQ satisfying the constraint y ∈ E. Our contribution is to establish strong concentration of the margin for any q ∈ (2,∞], assuming only that E has permutation symmetry. The case of q = ∞ is of particular interest in applications -- specifically to combinatorial ``balancing'' problems -- and is markedly out of the reach of the classical isoperimetric and concentration-of-measure tools that suffice for q ≤ 2. Generality is a key feature of this result: we assume permutation symmetry of the constraint set and nothing else. This allows us to encode many optimization problems in terms of the margin, including random versions of: the closest vector problem, integer linear feasibility, perceptron-type problems, ℓq-combinatorial discrepancy for 2 ≤ q ≤ ∞, and matrix balancing. Concentration of the margin implies a host of new sharp threshold results in these models, and also greatly simplifies and extends some key known results.