We present a combinatorial optimization problem with useful applications in the fields of task assignment, memory allocation, and image document analysis. Our motivation is to find a mapping that optimizes an objective function defined as a sum of averaged elementary gains. The problem is conjectured to be NP-hard, and solution we propose is heuristic-based. It utilizes a greedy heuristic function which combines optimal solutions of small-sized sub-problems to yield a potential solution to the original problem. The solutions of the sub-problem are, in turn, related to what we call saddle points of the underlying sub-problem. The proposed algorithm has been extensively tested. In the case of problems with a small number of elements, the reported solution has been compared to the optimal solution determined by exhaustively searching the solution space, and in these cases, the heuristic solution obtained is remarkably close to the optimal one. For problems of larger magnitude, the computed heuristic solution is compared to the value obtained by a greedy solution, and our algorithm is markedly superior in almost every case. Copyright 2006 ACM.

Additional Metadata
Keywords Approximation algorithms for optimization, Averaged mappings, Heuristic solutions
Persistent URL dx.doi.org/10.1145/1185448.1185455
Conference 44th Annual ACM Southeast Conference, ACMSE 2006
Hilaire, X. (Xavier), & Oommen, J. (2006). The averaged mappings problem: Statement, applications, and approximate solution. In Proceedings of the Annual Southeast Conference (pp. 24–29). doi:10.1145/1185448.1185455