Страница публикации

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

Авторы: Семёнов А.А.

Журнал: Прикладная дискретная математика. Приложение

Том:

Номер: 15

Год: 2022

Отчётный год: 2022

Издательство:

Местоположение издательства:

URL:

Проекты:

Теоретические основы, методы и высокопроизводительные алгоритмы непрерывной и дискретной оптимизации для поддержки междисциплинарных научных исследований

DOI: 10.17223/2226308X/15/23

Аннотация: Дан обзор некоторых недавних результатов, связанных со структурами, за которыми в англоязычной литературе закрепился термин “Backdoor”. Наиболее близким аналогом в русском, по-видимому, является термин «лазейка». Лазейка - это такое множество переменных в произвольной задаче удовлетворения ограничений, знание которого существенно упрощает рассматриваемую задачу либо даёт верхнюю оценку трудности её решения, которая лучше трудности тривиальной переборной стратегии. Лазейки в последние годы являются популярным объектом исследований как в прикладных областях, так и в теоретических (главным образом, в параметризованной сложности). Обсуждается применение лазеек для повышения эффективности решения конкретных комбинаторных задач из семейств SAT (проблема булевой выполнимости) и 0-1-ILP (0-1-целочисленное линейное программирование).

Индексируется WOS: Нет

Индексируется Scopus: Нет

Индексируется УБС: Нет

Индексируется РИНЦ: Да

Индексируется ВАК: Нет

Индексируется CORE: Нет

Публикация в печати: 0