Sciact
  • EN
  • RU

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
Авторы Sevastyanov Sergey 1
Организации
1 Sobolev Institute of Mathematics

Информация о финансировании (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
Даты:
Опубликована online: 30 сент. 2022 г.
Идентификаторы БД:
Scopus: 2-s2.0-85140481204
OpenAlex: W4313045632
Цитирование в БД: Пока нет цитирований
Альметрики: