Accession Number:

ADA171552

Title:

Tight Bounds for Minimax Grid Matching, with Applications to the Average Case Analysis of Algorithms.

Descriptive Note:

Interim research rept.,

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

• Leighton,Tom
• Shor,Peter

Report Date:

1986-05-01

Pagination or Media Count:

31.0

Abstract:

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, two-dimensional 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 2-dimensional 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. This paper solves 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.

Descriptors:

• *GRIDS
• *MINIMAX TECHNIQUE
• ALGORITHMS
• STATISTICAL ANALYSIS
• COMBINATORIAL ANALYSIS
• MATCHING
• PSEUDO RANDOM SYSTEMS
• RANDOM NUMBER GENERATORS

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE