Algorithm to solve a discrete minimax problem of the arrangement of physical field sources (Q844370)

The authors propose an approximation algorithm for a special minimax assignment problem which arises when you have to place a certain number of elements (heat sources) on a wire-circuit board aiming to minimize the maximum temperature at a finite set of test points. The problem is formulated as a finite set of assignment problems with identical set of feasible solutions where the maximum value of the different objective functions has to be minimized. Using well-known facts of transportation problems an iterative improvement algorithm is developed by use of potentials related to base solutions. Approximation guarantees are only given with respect to the relaxed integer programming problem.