Combinatorial Optimization Problems

Ivan V. Sergienko
Additional contact information
Ivan V. Sergienko: National Academy of Sciences of Ukraine

Chapter Chapter 7 in Topical Directions of Informatics, 2014, pp 233-249 from Springer

Abstract: Abstract We consider combinatorial optimization problems (COP), i.e., finding extrema of an objective function on a combinatorial space. Many various important applied and theoretical problems of different degree of complexity can be presented as problems in graph theory. These, for example, are the problem of designing communication networks, engineering devices, electronic and digital equipment, traffic control, planning and management of industrial and commercial activities, layout of equipment. To solve them, the number graph theory is proposed. To solve other COP, the theories of mathematical safes, construction of discrete images, combinatorial recognition, and solution of extremum problems on combinatorial configurations are proposed. The theory of mathematical safes analyzes a number of problems on special graphs, which are called safes. One should use certain operations to decode the states of vertices called locks. It is used in coding theory, information security, and cryptology. The theory of constructing discrete images involves problems where it is necessary to use a given set of colored patterns to construct a prescribed image on a rectangular field of view. It is also used in coding theory and information security. The combinatorial recognition theory addresses problems of recognition of the properties of individual objects from some set by so-called tests or trials, which allow a wide interpretation. Such problems occur in various lotteries, banking sector, and insurance companies. The graph-theoretical approach is proposed to solve these problems. Many problems in economic and mathematical modeling reduce to optimization problems on combinatorial configurations such as permutations, partitions, combinations, arrangements, multisets, etc. To solve them, the direct structuring method based on the graph theory is proposed.

Keywords: Combinatorial Optimization Problem; Combinatorial Problem; Complex Image; Elementary Image; Oriented Graph (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-1-4939-0476-1_7

Ordering information: This item can be ordered from
http://www.springer.com/9781493904761

DOI: 10.1007/978-1-4939-0476-1_7

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().