Aproksymacyjne pakowanie zbiorów

Prelegent(ci)

Marek Cygan

Afiliacja

Uniwersytet Warszawski

Termin

20 października 2016 14:15

Pokój

p. 5440

Seminarium

Kolokwium Wydziału MIM UW

---

W problemie pakowania k-zbiorów mamy dane uniwersum oraz rodzinę jego podzbiorów, przy czym każdy zbiór jest mocy co najwyżej k. Celem jest wybranie możliwie najliczniejszej podrodziny parami rozłącznych zbiorów. Problem ten jest NP-trudny a badania jego aproksymowalności sięgają lat 80-tych. Podczas referatu omówię historię algorytmów aproksymacyjnych dla tego problemu, ze szczególnym uwzględnieniem metod opartych o przeszukiwanie lokalne

---

• slajdy