Наредни састанак Семинара биће одржан онлајн у петак, 5. децембар 2025. са почетком у 12:15.

Предавач: Марко Миленковић, ЕТХ Цирих

Наслов предавања: АПРОКСИМАЦИЈА МИНИМАЛНОГ РАЗАПИЊУЈУЋЕГ СТАБЛА – ПРЕДСТАВЉАЊЕ РЕЗУЛТАТА РАДА ALVAREZ & SEIDEL (2010)

Апстракт: На овом предавању видећемо неке занимљиве резултате из рада Alvareza и Seidela из 2010. Они проучавају колико је тешко апроксимирати минимално разапињајуће стабло (MST) неког скупа тачака користећи само мали подскуп тих тачака. Главни резултати:

• Ако желимо да приближно погодимо тежину MST-а за било који скуп тачака,
  понекад морамо да узмемо скоро цео скуп.
• Ако нам је битан само облик MST-а, онда је ситуација скроз другачија.
  Увек постоји мали подскуп Q величине O(1/ε^d) који врло добро апроксимира
  оригинални MST у смислу Хаусдорфове дистанце.
• Такав подскуп и одговарајуће стабло T могу се ефикасно израчунати у
  полиномијалном времену, уз зависност од димензије и ε.

Овај рад показује занимљиву разлику између апроксимације тежине и апроксимације облика МST структуре. Мала промена циља води до потпуно другачије комплексности.

Напомена: Предавања можете пратити на даљину. Све информације су доступне на страници:
https://miteam.mi.sanu.ac.rs/asset/M4zcEwxkzy5PqNS73