A Simple Approximation Algorithm for the Modified Bottleneck Assignment Problem in Vector Case

Yuusaku Kamura^* and Mario Nakamori

We deal with the modified bottleneck assignment problem in vector case. The problem is to find the matching between two vector sets that minimizes the maximum sum of vectors' elements. In scalar case, there is a simple polynomial time algorithm that uses the order of elements' value. We extend this problem to the vector case and propose a simple approximation algorithm for it. Though the problem is expressed by the integer programming problem, we don't deal with it directly. Outline of the algorithm is as follows: (1) make the ordered sequence for each vector's set based on vector's position in the coordinate space, (2) combine each component from the two sequences that is similar to the scalar case. In this research, we discuss the problem in the $2$-dimensional vector's case. We propose the algorithm and show the effectiveness of it by numerical experiments. Our problem arises from making the optimal combination of lenses' system used in semiconductor manufacturing systems. In the industrial producing site, it is often required that the running time of algorithm has priority over the preciseness of it. Therefore it is valuable to propose the algorithm not only guarantees the weak preciseness but also executes quickly in practical use.

Mathematics Subject Classification: 90C27 90C59

Keywords: assignment problem; discrete algorithm; approximation

Contributed Talks