# Jin Hao Wan: Probabilistic LSAP and 2-out graph

I read Walkup’s approximation algorithm for the probabilistic linear sum assignment problem (LSAP) in Michael Steele’s book, *Probability Theory and Combinatorial Optimization*, this past IAP. The algorithm became one of my favorites instantly.

In LSAP, we have a set of n machines, indexed by i, and a set of n jobs, indexed by j. The cost to do job j on machine i is c_{ij}. Our goal is to find an assignment, or a permutation \pi: [n] \mapsto [n], that solves: A_n = \min_{\pi} \sum_{i=1}^{n} c_{i \pi(i)}. The problem becomes interesting once we add “probabilistic” to it. Now c_{ij}’s are independent random variables with the uniform distribution on [0,1]; and we aim to compute the expected value of A_n.

To approximate E[A_n], we can upper-bound it by the expected cost of any assignment algorithm. If we start out with the greedy algorithm, looking at either one job at a time (locally greedy) or all unassigned jobs at once (globally greedy), we will find out that the expected cost in this case is \Omega(\log{n}). In 1979, however, Walkup came up with an algorithm whose expected cost is 3 + o(1). Thus, E[A_n] is bounded above by a constant, irrespective of n!

Before we go on, it is convenient to view the machines and the jobs as the two partitions of a bipartite graph, and the costs as edges. The algorithm selects a subset of edges, E, based on a probability space defined in terms of c_{ij}’s. It turns out that edges in E have two desirable properties. First, E forms a random *2-out graph*. A 2-out graph is a *directed* bipartite graph where the out-degree of every vertex is 2. Walkup proves that with high probability a random 2-out graph has a perfect matching. This allows the algorithm to reduce the original problem to finding a minimum assignment in a much sparser 2-out graph. Now the second property of E comes into play: edges in E have small costs on average. This implies that the total cost, C, of the assignment returned by the algorithm will be small. Taking the expectation, we find out that E[C] = 3 + o(1).

Note: The proof in Walkup’s paper is non-constructive; so the word “Walkup’s approximation algorithm” in the first sentence of this writeup is misleading. It was Karp, Ronnooy Kan and Vohra who came up with the algorithm in 1995. Since my favorite part of this algorithm (introducing the idea of a 2-out graph) is due to Walkup, I feel justified in using “Walkup’s approximation algorithm.”