О скрытых упрощающих структурах в комбинаторных задачах и их вероятностных обобщениях

doi:10.17223/2226308X/15/23

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
О скрытых упрощающих структурах в комбинаторных задачах и их вероятностных обобщениях	568 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/2226308X/15/23

#лазейки в комбинаторных задачах

#проблема булевой выполнимости (SAT)

#целочисленное линейное программирование

Title: О скрытых упрощающих структурах в комбинаторных задачах и их вероятностных обобщениях
Creator: Семенов, Александр Анатольевич
Date: 2022
DOI: 10.17223/2226308X/15/23
Description: Дан обзор некоторых недавних результатов, связанных со структурами, за которыми в англоязычной литературе закрепился термин “Backdoor”. Наиболее близким аналогом в русском, по-видимому, является термин «лазейка». Лазейка — это такое множество переменных в произвольной задаче удовлетворения ограничений, знание которого существенно упрощает рассматриваемую задачу либо даёт верхнюю оценку трудности её решения, которая лучше трудности тривиальной переборной стратегии. Лазейки в последние годы являются популярным объектом исследований как в прикладных областях, так и в теоретических (главным образом, в параметризованной сложности). Обсуждается применение лазеек для повышения эффективности решения конкретных комбинаторных задач из семейств SAT (проблема булевой выполнимости) и 0-1-ILP (0-1-целочисленное линейное программирование).

Relationships: Show Relationship Browser for this Object
collection(s): Журналы ТГУ
Identifier: смотреть в электронном каталоге НБ ТГУ
Type: статьи в журналах
Source: Прикладная дискретная математика. Приложение. 2022. № 15. С. 100-104
Language: rus

Created: 08-09-2022

331 Visitors

219 Hits

121 Downloads

Журналы ТГУ О скрытых упрощающих структурах в комбинаторных задачах и их вероятностных обобщениях