Posts Tagged ‘Approximation Factor’
A Greedy Approximation Algorithm for the Linear Assignment Problem
Starting today, I will be posting some of the related source code for articles on GitHub.
Introduction
The Linear Assignment Problem (LAP) is concerned with uniquely matching an equal number of workers to tasks, , such that the overall cost of the pairings is minimized. A polynomial time algorithm was developed in the late fifties by [6], and further refined by [9], called the Hungarian method. Named so after the work of Hungarian mathematicians König and Egerváry whose theorems in the 1930s form the basis for the method. While the Hungarian Method can solve LAP instances in time, we wish to find faster algorithms even if it means sacrificing optimality in the process. Here we examine a greedy approximation algorithm with runtime in terms of its approximation factor and compare it empirically to the Hungarian method.
Linear Assignment Problem
The above linear program has cost, , and assignment, , matrices that specify the terms of the LAP. This is equivalent to finding a perfect matching in a weighted bipartite graph. A minimal cost may have several possible assignments, but we are only interested in finding just one. It is assumed that no one worker can do all jobs more efficiently by themselves than the distributing work across all workers. Likewise, if the costs are thought of as durations, then the minimum cost is the minimum sequential rather than parallel time taken to complete the tasks.
From a practical point of view, we may relax the integral constraint on and allow all positive realvalued costs. For instances where there are more jobs than workers, and vice versa, dummy entries valued greater than the existing maximum may be added. Minimizing the cost is the default objective, but the maximum cost can be found by finding the optimal assignment for , then finding the cost relative to .
Algorithms
Brute Force Rather than using the mathematical programming or graph theoretic representation of the problem, we can instead view the problem as finding the assignment that minimizes the cost out of all possible assignments:
There are such assignments which can be produced using an iterative version of Heap’s algorithm [5] in time assuming one does differential scoring (opposed to calculating the score for each permutation which would result in an algorithm.)
Random The random algorithm selects a permutation uniformly from the set of all possible assignment permutations in time using the FisherYates shuffle [4]. This obviously does not produce an optimal or nearoptimal solution, but serves as a straw man to compare other results.
Greedy The greedy heuristic continues to cover the row and column of the smallest uncovered entry in the cost matrix until all entries are covered. The resulting set of entries then constitutes the assignment of workers to jobs. An inefficient algorithm can be used to find the smallest entry every iteration, or a more efficient result of can be obtained through the use of a sorted, array indexed hybrid mesh and queue. Let represent a tuple consisting of row, column, and value; the previous entry in the matrix this value, and the next entry in this matrix this value; and the (left, above, right, below) that are adjacent to this node.
Algorithm 1 A greedy algorithm for the LAP.

 // Adjacent node left, above, right, below properties
 // Sort in ascending order by node value
 // Adjacent node previous and next properties

 // Deletes row and col of
Allocating and linking for assignment is ; mesh ; queue . Therefore, initialization requires time. The body of the loop requires a constant time assignment of worker to job, and time to remove the row and column from a matrix using a modified depth first search. Thus, the loop itself accounts for time. The resulting time complexity is therefore .
Breaking ties for the minimum uncovered value can result in different costs. This drawback is shown in the above example were choosing at yields a minimum cost of , where as the one at gives a minimum cost of . The next progression in the design of the greedy algorithm would be to try all minimum positions and keep the top performing paths.
Hungarian The general idea behind the KuhnMunkres algorithm is that if we are given an initial assignment, we can make further assignments and potentially reassign workers until all workers have been tasked with a job. The highlevel sketch of the algorithm starts with an initial assignment. While we have jobs that are unassigned, we look for qualified workers, ie, the zero entries. If a worker is already assigned to a job, but is also qualified for another, then we prime the alternative and continue to the next qualified worker, but if that is the only job the worker is qualified for, then we’d like to reassign any other worker already tasked to that job. This leads to a natural ripple effect represented by an alternating path of starred and primed entries. In Munkres’ paper [9] “starred” zero’s represent assignments of workers to jobs, and “primed” zero’s are alternative assignments. By flipping the bits of the path, we reassign workers to their alternative tasks while ensuring the assignment continues to be minimal by construction. After assigning as many workers as we have to, we then deduct the lowest cost to create a new qualified worker. Thus, every iteration we are guaranteed to make positive progress towards our goal of finding an optimal assignment. This scheme results in the worst case time to complete.
Algorithm 2 The Hungarian method for the LAP.

 Star the first uncovered zero in row , cover the corresponding column for
 All columns not covered
 Uncovered zeros
 Prime the current uncovered zero
 There’s a starred zero in this row
 Uncover the starred zero’s column and cover the row

 Find an alternating augmented path from the primed zero
 Unstar the starred zeros on the path and star the primed zeros on the path
 Remove all the prime markings and cover all stared zeros
 Found path

 over all uncovered
 for all uncovered columns
 for all covered rows
 Uncovered zeros
 Starred zeros // These are all the assignments
To further illustrate the algorithm, consider the following example where starred entries are denoted by red, and primed entries by green:
Analysis
The prevailing convention in the literature is to look at the approximation factor, , to determine how close the results of an approximation algorithm are to optimal [10]. Here this ratio is the expected minimum cost assignment of the algorithm under test to the same quantity given by the expected minimum assignment cost. Let be an a standard exponential random cost matrix. We resort to the exponential distribution for its ease of analyis and prominence in related literature. Cf. the works of [7], [8] for analysis based on .
Exponential Distribution Properties Let have cumulative distribution function and expectation . The distribution demonstrates the memoryless property for expectations . Define the order statistic to be the minimum of draws from . [2] with expectation . If then with expectation .
Expected Minimum Cost The expected minimum assignment cost for is given by [1]:
Which is the generalized harmonic number of order two and converges to . For the generalized harmonic numbers, , for .
Greedy The minimum value of an matrix is given by the order statistic with expectation . The expected value of the minimum cost assignment is not just because the expectation doesn’t take into account the previous iteration’s minimum value. To accomplish this we make use of the memoryless property of the exponential distribution to observe that the expected difference in minimums between iterations is the expected minimum value given by . If we add up all these differences we get the expected minimum value of the k’th iteration; summing all these expectations then yields the expected minimum cost assignment:
This is the harmonic number of order one which does not converge. The resulting approximation factor is:
Random The random algorithm will simply select an assignment permutation, so we are just adding up distributed random variables leading to an expected cost of:
And approximation factor:
From this analysis one concludes that the greedy algorithm has an unbounded approximation factor that grows significantly slower than that of randomly selecting assignments.
Evaluation
To illustrate the preceding results, Figure 1 shows the approximation factor for the greedy algorithm implementations against the derived approximation factor. The simulated results are based on 120 standard exponentially distributed matrices for . Using the same conventions for the approximation factor, Figure 2 illustrates the runtime characteristics of the algorithms after rejecting outliers due to system fluctuations. Results obtained from source code compiled with O3 flags and ran on a Xeon E31245 v5 3.5 Ghz system with 32 GBs of 2133Mhz DDR4 RAM. The algorithms coincide with the theoretical time complexities as shown in Table 2.
Solver  MSE 

GREEDYEFFICIENT  0.002139 
GREEDYNAIVE  0.014161 
HUNGARIAN  0.232998 
Summary
Brute  Random  Greedy  Hungarian  

Complexity  
1  1 
Exact solutions can be delivered by the brute method when a handful of workers are being considered, and the Hungarian method should be considered for all other instances. Approximate solutions can be provided by the greedy algorithm with logarithmic degeneracy while providing a linear factor improvement over the Hungarian method. For inputs greater than those considered, the parallel Auction algorithm [3] is a suitable alternative and the subject of future work.
References
 Aldous, D. J. The limit in the random assignment problem. Random Structures & Algorithms 18, 4 (2001), 381418.
 Balakrishnan, N., and Rao, C. Handbook of statistics 16: Order statisticstheory and methods, 2000.
 Bertsekas, D. P. The auction algorithm: A distributed relaxation method for the assignment problem. Annals of operation research 4, 1 (1988), 105123.
 Durtenfeld, R. Algorithm 235: random permutation. Communications of the ACM 7, 7 (1964), 420.
 Heap, B. Permutations by interchanges. The Computer Journal 6, 3 (1963), 293298.
 Kuhn, H. W. The hungarian method for the assignment problem. Naval research logistics quarterly 2, 12 (1955), 83097.
 Kurtzberg, J. M. On approximation methods for the assignment problem. Journal of the ACM (JACM) 9, 4 (1962), 419439.
 Steele, M. J. Probability and statistics in the service of computer science: illustrations using the assignment problem. Communications in StatisticsTheory and Methods 19, 11 (1990), 43154329.
 Munkres, J. Algorithms for the assignment and transportation problems. Journal of the society for industrial and applied mathematics 5, 1 (1957), 3238.
 Williamson, D. P., and Shmoys, D. B. The design of approximation algorithms. Cambridge university press, 2011.