Average-case analysis for combinatorial problems featuring subset sums and stochastic spanning trees

This talk will be a survey of some recent developments in average-case analysis of algorithms for combinatorial problems. I will focus on random distributions which seem to yield computationally challenging problems and where to find the “easiest hard problems” and the “hardest easy problems”.

As a detailed example, I will describe the modular subset sum problem, where you are given n numbers, a modulus M, and a target number T, and the goal is to find a subset of the numbers which sum to T (mod M). Though this is a classic NP-hard problem, many particular instances are not too challenging computationally. When the n numbers are selected uniformly at random from {0, 1, … , M-1}, the difficulty depends critically on the size of M (as a function of n). I will describe what is known about this complicated relationship, including results from [Flaxman and Przydatek, STACS 2005] which describe an algorithm that succeeds in expected polynomial time when M = n^{O(log n)}.

I will also talk about another combinatorial problem, which related to the minimum spanning tree. When the cost of the edges between n nodes are selected independently and uniformly from [0,1], the cost of the minimum spanning tree converges to a constant, and the constant is ζ(3) = 1/1³ + 1/2³ + 1/3³ + … [Frieze, Discrete Appl. Math.1985]. In the two-stage stochastic programming version of this problem [Flaxman, Frieze, and Krivelevich, SODA 2005/Random Structures Algorithms 2006], you know the costs of each edge on Monday and the distribution of the costs of each edge on Tuesday. The goal is to select a set of edges to buy on Monday so that when the tree is completed on Tuesday, the expected total cost is minimized. When the Monday and Tuesday costs are all selected independently and uniformly from [0,1], a simple threshold heuristic produces a solution with expected cost ζ(3) – 1/2. This is not the optimal two-stage solution, however.