• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

A Reduction Technique for Weighted Grouping Problems

Timo Knuutila, Olli Nevalainen, A Reduction Technique for Weighted Grouping Problems. European Journal of Operations Research (140), 590-605, 2002.

Abstract:

Weighted grouping problems are shown to have an equivalent reduced form, which is often considerably smaller than the original problem. Although the reduction may be small for randomly generated problems, real-life problems often contain non-random properties that greatly increase the effect of reduction. We give an efficient algorithm to build the reduced problem instance, and analyse the expected amount of reduction for certain statistical distributions and real-life data. In addition, we briefly discuss the effect of reduction on traditional solving methods of the grouping problem. The results show clearly the usefulness of problem reduction: it is computationally cheap to apply and may make the reduced problem solvable in a practical time whilst the original one is not. The method is readily applicable to the job grouping problem of printed circuit board (PCB) printing industry.

BibTeX entry:

@ARTICLE{jKnNea,
  title = {A Reduction Technique for Weighted Grouping Problems},
  author = {Knuutila, Timo and Nevalainen, Olli},
  journal = {European Journal of Operations Research},
  number = {140},
  pages = {590-605},
  year = {2002},
}

Belongs to TUCS Research Unit(s): Algorithmics and Computational Intelligence Group (ACI)

Edit publication