Nordic Journal of Computing Bibliography

Abstract

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 c_ijk 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

• Sanjeev Arora. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In 37th Annual Symposium on Foundations of Computer Science, pages 2-11, Burlington, Vermont, 14-16 October 1996. IEEE.

• M. E. Dyer and A. M. Frieze. Planar 3DM is NP-complete. Journal of Algorithms, 7(2):174-184, June 1986.

• M. R. Garey, R. L. Graham, and D. S. Johnson. Some NP-complete geometric problems. In Conference Record of the Eighth Annual ACM Symposium on Theory of Computing, pages 10-22, Hershey, Pennsylvania, 3-5 May 1976.

• R. Z. Hwang, R. C. Chang, and Richard C. T. Lee. The searching over separators strategy to solve some NP-hard problems in subexponential time. Algorithmica, 9:398-423, 1993.

• Christos H. Papadimitriou. The Euclidean Traveling Salesman Problem is NP-complete. Theoretical Computer Science, 4(3):237-244, June 1977.

Shortcuts: