Tuesday Afternoon Club/Session 4: Апроксимиращи алгоритми

Презентатор: доц. Минко Марков

Модератор: доц. Петър Армянов

Резюме: Сесията разглежда един начин за “заобикаляне” на алгоритмичната неподатливост (intractability): конструиране на апроксимиращи алгоритми.

В началото ще разгледаме оптимизационни изчислителни задачи по принцип и в частност NP-трудни оптимизационни задачи. След това ще разгледаме примери за ефикасни алгоритми за неподатливи оптимизационни задачи, които връщат не непременно оптимални решения, но дават гаранции за неоптималността. Ще разгледаме различни техники за конструиране на такива алгоритми.

После ще въведем формални определения и няколко изчислителни класове. Накрая ще разгледаме относителната спрямо недоказаната хипотеза, че P≠NP - невъзможност за апроксимиране на няколко задачи.