Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > On the 3-Matching Problem

On the 3-Matching Problem

Mika Johnsson, Gábor Magyar, Olli Nevalainen, On the 3-Matching Problem. TUCS Technical Reports 112, Turku Centre for Computer Science, 1997.

Abstract:

<p>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 2-matching and 3-dimensional assignment problems. We consider an 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 an application in the optimization of manufacturing operations. We show that the general 3MP is NP-complete and give several methods to calculate the lower bound for the E3MP. The exact solution by branch-and-bound technique is possible for small instances (n < 54). For larger 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.

<p>Contact Mika Johnsson (johnsson@cs.utu.fi) for the complete report.

BibTeX entry:

@TECHREPORT{tJoMaNe97,
  title = {On the 3-Matching Problem},
  author = {Johnsson, Mika and Magyar, Gábor and Nevalainen, Olli},
  number = {112},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {1997},
  ISBN = {952-12-0011-1},
}

Edit publication