24.10.2017 Параметризованные сведения (Данил Сагунов)

Время: 24 октября, 16:30

Место: ПОМИ РАН, ауд. 402

Докладчик: Данил Сагунов

Описание:

Мы рассмотрим основные понятия параметризованной сложности: 

параметризованная задача - задача, экземпляры которой расширены дополнительным числом-параметром;

класс FPT - класс параметризованных задач, для которых для любого фиксированного значения параметра существует алгоритм, работающий полиномиальное время;

параметризованные сведения - сведения, позволяющие, подобно полиномиальным сведениям, сохранять наличие FPT-алгоритма.

Последнему понятию будет уделено основное внимание: мы сравним его с полиномиальными сведениями и приведем несколько содержательных примеров параметризованных сведений известных NP-трудных задач друг к другу. Также будет определена W-иерархия - иерархия классов параметризованных задач, замкнутых относительно параметризованных сведений, и сформулированы некоторые полные в этих классах задачи.

 

Доклад по Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, Chapter 13. Fixed-parameter intractability.

AttachmentSize
PDF icon chapter13.pdf1.36 MB