О некоторых обобщениях задачи о рюкзаке

Задача о рюкзаке является одной из самых известных дискретной оптимизации - её формулировка очень проста, притом что сама задача является NP-полной. Сочетание этих двух особенностей, а также широкий спектр возможных применений в логистике, экономике и других областях приводит к высокому уровню исследовательского интереса к данной задаче. При этом задача имеет множество разных вариаций и формулировок, большая часть из которых хорошо изучены. В данной работе рассматривается ещё один способ обобщить задачу о рюкзаке, продиктованный желанием связать её с теорией сложности вычислений. В частности, рассматриваются обобщения, для которых нетривиально определить конкретный класс сложности задачи, а также ставится цель разработать приближенные алгоритмы для данных обобщений, имеющие приемлемое время работы. Для выполнения данных целей используются стандартные подходы для подобных ситуаций - построение релаксаций исходных задач, поиск оптимума для них и доказательство того, оптимумы прямых задач и соответствуюзих им релаксаций отличаются не более чем в константу раз. В главе №2 рассматриваются общие формулировки теоретико-сложностных задач, частными случаями которых являются классическая задача о рюкзаке и некоторые её обобщения, которые будут изучены в последующих главах. Также доказываются некоторые утверждения, уточняющие нижние оценки сложности задач. В главе №3 рассматривается конкретно задача ADVERSARY KNAPSACK, являющаяся нестандартным, но при этом естественным обобщением задачи в классической формулировке. Для данной задачи предъявляется алгоритм, гарантирующий константное приближение для нахождения оптимума. Аналогично в главе №4 изучается задача TWIN KNAPSACK, стоящая выше ранее упомянутых задач о рюкзаке в сложностной иерархии. Для этой задачи также предъявляется алгоритм, гарантирующий константное приближение к искомому значению. Полученные приближённые алгоритмы, в свою очередь, и являются основным результатом данной работы. В данной работе были успешно достигнуты цели, заявленные во введении. Для задач ADVERSARY KNAPSACK и TWIN KNAPSACK были предъявлены полиномиальные от длины входа, данного в унарной записи, алгоритмы, гарантирующие константное приближение к оценке искомых значений. Также автор считает важным отметить, что данное исследование оставляет широкий зазор на будущее для дальнейшего изучения. Остаются открытыми вопросы о сложности задачи GAME в бинарной записи, а также о более глубоком понимании структуры игры MULTI-GAME в общем и в отдельных случаях.