Nordic Journal of Computing Bibliography

M. Johnsson, G. Magyar, and O. Nevalainen. On the Euclidean 3-Matching Problem. Nordic Journal of Computing, 5(2):143-171, Summer 1998.

In the 3-matching problem (3MP) we want to partition a set of n=3l points into l disjoint subsets, each consisting of three points (called triplets), and to minimize the total cost of the triplets. The problem is related to the well-known weighted 2-matching, 3-dimensional assignment and p-median problems. We consider a Euclidean 3MP (E3MP) where the cost cijk of a triplet (i,j,k) is the sum of the lengths of the two shortest edges of the triangle (i,j,k). The problem has several related applications in the optimization of manufacturing operations. We show that the general 3MP is NP-complete and give several methods to calculate lower bounds for the E3MP. The exact solution by branch-and-bound technique is possible for small instances. For large problem instances we have to apply approximative solution algorithms. Local search-based heuristics augmented with ideas from tabu-search, simulated annealing and genetic algorithms worked well in our tests.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.1.6 [Numerical Analysis]: Optimization; G.2.1 [Discrete Mathematics]: Combinatorics; G.2.2 [Discrete Mathematics]: Graph Theory

Additional Key Words and Phrases: matching problems, lower bounds, Lagrangian relaxation, branch-and-bound, heuristic methods, simulated annealing, genetic algorithms

Selected references


  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database