The averaged mappings problem: statement, applications, and approximate solution

ABSTRACT

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.

REFERENCES

• 1: APPROX. In APPROX, Proceedings of the various International Workshops on Approximation Algorithms for Combinatorial Optimization Problems.
• 2: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 3: Xavier Hilaire, A Matching Scheme to Enhance Performance Evaluation of Raster-to-Vector Conversion Algorithms, Proceedings of the Seventh International Conference on Document Analysis and Recognition, p.629, August 03-06, 2003
• 4: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 5: B. John Oommen , Luis G. Rueda, A formal analysis of why heuristic functions work, Artificial Intelligence, v.164 n.1-2, p.1-22, May 2005 [doi>10.1016/j.artint.2002.02.001]
• 6: Takeshi Tokuyama , Jun Nakano, Efficient Algorithms for the Hitchcock Transportation Problem, SIAM Journal on Computing, v.24 n.3, p.563-578, June 1995 [doi>10.1137/S0097539792236729]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Performance

Keywords:
approximation algorithms for optimization, averaged mappings, heuristic solutions, optimization