Three efficient methods of finding near-optimal solution for np-hard discrete optimization problems. (Illustrated by their application to scheduling problems) Full article
| Conference |
International Conference Mathematical Optimization Theory and Operations Research Petrozavodsk, Karelia, Russia, July 2-6, 2022 02-08 Jul 2022 , Петрозаводск, Карелия, Россия |
||
|---|---|---|---|
| Journal |
Communications in Computer and Information Science
ISSN: 1865-0929 |
||
| Output data | Year: 2022, Volume: 1661, Pages: 3–33 Pages count : 31 DOI: 10.1007/978-3-031-16224-4_1 | ||
| Tags | Efficient methods · Approximation algorithms · Discrete optimization · Scheduling · Uniform distributions · Compact vector summation | ||
| Authors |
|
||
| Affiliations |
|
Funding (2)
| 1 | Russian Foundation for Basic Research | 20-07-00458 |
| 2 | Sobolev Institute of Mathematics | 0314-2019-0014 |
Abstract:
Three fairly universal and efficient methods of finding near-optimal solutions for NP-hard problems will be discussed in our talk and illustrated by examples of their application to scheduling problems (although, they are surely applicable to a much wider area of Discrete Optimization problems):
1. Methods of “compact” vector summation in a ball (of any norm) of minimum radius, and methods of non-strict summation of vectors in a given area of d-dimensional space. These methods are applicable to problems of finding uniform distributions of multicomponent objects.
2. Application of the maximum flow and the minimum cut algorithms to problems of finding uniform distributions of one-component objects with prescribed constraints on the distribution areas of objects.
3. The method of a gradual reduction of the feasible solutions domain.
Cite:
Sevastyanov S.
Three efficient methods of finding near-optimal solution for np-hard discrete optimization problems. (Illustrated by their application to scheduling problems)
Communications in Computer and Information Science. 2022. V.1661. P.3–33. DOI: 10.1007/978-3-031-16224-4_1 Scopus OpenAlex
Three efficient methods of finding near-optimal solution for np-hard discrete optimization problems. (Illustrated by their application to scheduling problems)
Communications in Computer and Information Science. 2022. V.1661. P.3–33. DOI: 10.1007/978-3-031-16224-4_1 Scopus OpenAlex
Dates:
| Published online: | Sep 30, 2022 |
Identifiers:
| Scopus: | 2-s2.0-85140481204 |
| OpenAlex: | W4313045632 |
Citing:
Пока нет цитирований