Naredni sastanak Seminara biće održan onlajn u petak, 5. decembar 2025. sa početkom u 12:15.

Predavač: Marko Milenković, ETH Cirih

Naslov predavanja: APROKSIMACIJA MINIMALNOG RAZAPINjUJUĆEG STABLA – PREDSTAVLjANjE REZULTATA RADA ALVAREZ & SEIDEL (2010)

Apstrakt: Na ovom predavanju videćemo neke zanimljive rezultate iz rada Alvareza i Seidela iz 2010. Oni proučavaju koliko je teško aproksimirati minimalno razapinjajuće stablo (MST) nekog skupa tačaka koristeći samo mali podskup tih tačaka. Glavni rezultati:

• Ako želimo da približno pogodimo težinu MST-a za bilo koji skup tačaka,
  ponekad moramo da uzmemo skoro ceo skup.
• Ako nam je bitan samo oblik MST-a, onda je situacija skroz drugačija.
  Uvek postoji mali podskup Q veličine O(1/ε^d) koji vrlo dobro aproksimira
  originalni MST u smislu Hausdorfove distance.
• Takav podskup i odgovarajuće stablo T mogu se efikasno izračunati u
  polinomijalnom vremenu, uz zavisnost od dimenzije i ε.

Ovaj rad pokazuje zanimljivu razliku između aproksimacije težine i aproksimacije oblika MST strukture. Mala promena cilja vodi do potpuno drugačije kompleksnosti.

Napomena: Predavanja možete pratiti na daljinu. Sve informacije su dostupne na stranici:
https://miteam.mi.sanu.ac.rs/asset/M4zcEwxkzy5PqNS73