Linear assignment problems in combinatorial optimization

Boris Goldengorin, Dmitry Krushinsky*

*Corresponding author for this work

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

3 Citations (Scopus)


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
ISBN (Electronic)9783319686400
ISBN (Print)9783319686394
Publication statusPublished - 7 Dec 2017

Publication series

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


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

Cite this