Linear assignment problems in combinatorial optimization

Boris Goldengorin, Dmitry Krushinsky*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

Abstract

In this chapter we introduce the notion of a “pattern” in the Linear Assignment Problem and show that patterns may be useful to create new insights and approaches for many combinatorial optimization problems defined on a rectangular input matrix. We define a pattern as a specific collection of cells in the rectangular matrix reflecting the structure of an optimal solution to the original combinatorial optimization problem (COP). We illustrate the notion of pattern by means of some well-known problems in combinatorial optimization, including the variations of the Linear Ordering Problem, the Cell Formation Problem, and some others. Then, we give a detailed consideration to pattern-based solution approaches for the two mentioned problems.

Original languageEnglish
Title of host publicationOptimization Methods and Applications
Subtitle of host publicationIn Honor of Ivan V. Sergienko's 80th Birthday
EditorsS. Butenko, P.M. Pardalos, V. Shylo
PublisherSpringer International Publishing
Pages183-216
ISBN (Electronic)9783319686400
ISBN (Print)9783319686394
DOIs
Publication statusPublished - 7 Dec 2017

Publication series

NameSpringer Optimization and Its Applications
Volume130
ISSN (Print)1931-6828
ISSN (Electronic)1931-6836

Fingerprint Dive into the research topics of 'Linear assignment problems in combinatorial optimization'. Together they form a unique fingerprint.

Cite this