Заседание научного семинара лаборатории ЛАТАС
Мероприятие завершено
Докладчик: Dmitry Gribanov (lab LATNA HSE NN)
Тема: The knapsack problem with a non-separable polynomial objective function.
Язык семинара: English
We consider the nonlinear knapsack problem with a general non-separable polynomial objective function. It is known that this problem is strongly NP-hard already with at most two variables, thus the existence of even quasi-polynomial algorithms is highly unlikely. However, it is known that for a fixed dimension this problem admits an FPTAS.
In our work we construct a FPTAS that is polynomial on dimension and maximal element of the knapsack.
Приглашаются все желающие.
Явка аспирантов школы компьютерных наук обязательна.
Чтобы получить ссылку на конференцию Zoom, необходимо зарегистрироваться.
Дата
8 февраля
16:00