Three efficient methods of finding near-optimal solution for np-hard discrete optimization problems. (Illustrated by their application to scheduling problems) Научная публикация
| Конференция |
International Conference Mathematical Optimization Theory and Operations Research Petrozavodsk, Karelia, Russia, July 2-6, 2022 02-08 июл. 2022 , Петрозаводск, Карелия, Россия |
||
|---|---|---|---|
| Журнал |
Communications in Computer and Information Science
ISSN: 1865-0929 |
||
| Вых. Данные | Год: 2022, Том: 1661, Страницы: 3–33 Страниц : 31 DOI: 10.1007/978-3-031-16224-4_1 | ||
| Ключевые слова | Efficient methods · Approximation algorithms · Discrete optimization · Scheduling · Uniform distributions · Compact vector summation | ||
| Авторы |
|
||
| Организации |
|
Информация о финансировании (2)
| 1 | Российский фонд фундаментальных исследований | 20-07-00458 |
| 2 | Институт математики им. С.Л. Соболева СО РАН | 0314-2019-0014 |
Реферат:
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.
Библиографическая ссылка:
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
Даты:
| Опубликована online: | 30 сент. 2022 г. |
Идентификаторы БД:
| Scopus: | 2-s2.0-85140481204 |
| OpenAlex: | W4313045632 |
Цитирование в БД:
Пока нет цитирований