Tight bounds for minimax grid matching, with applications to the average case analysis of algorithms
Frank Thomson Leighton, Peter W. Shor · 1986
The minimax grid matching problem is a fundamental combinatorial problem associated with the average case analysis of algorithms.The problem has arisen in a number of interesting and seemingly unrelated areas, including wafer-scale integration of systolic arrays, twodimensional discrepancy problems, and testing pseudorandom number generators.However, the minimax grid matching problem is best known for its application to the maximum up-right matching problem.The maximum up-right matching problem was originally defined by Karp, Luby and Marchetti-Spaccamela in association with algorithms for 2dimensional bin packing.More recently, the up-right matching problem has arisen in the average case analysis of on-line algorithms for 1-dimensional bin packing and dynamic allocation.In this paper, we solve both the minimax grid matching problem and the maximum up-right matching problem.As a direct result, we obtain tight upper bounds on the average case behavior of the best algorithms known for 2-dimensional bin packing, 1-dimensional on-line packing and on-line dynamic allocation.The results also solve a long-open question in mathematical statistics.