Incremental Randomization in Combinatorial Optimization

Aravind Srinivasan
University of Maryland
College Park, Maryland

Randomized algorithms are now well-recognized to be powerful tools in combinatorial optimization. A common way in which they are employed is as "one-shot" approaches: a (carefully-constructed) randomized algorithm is shown to work with high probability. In the last two decades, a slowed-down version of this general approach has emerged as a very useful tool: here, the algorithm consists of several (small) randomized steps, the analysis of each of which makes use of some properties of previous steps. We will illustrate applications of such "nibble methods" in packing/covering problems for hypergraphs, packet routing in networks, graph partitioning, and graph coloring. The talk will only assume a basic familiarity with probability and discrete optimization.