Aproksymacyjne pakowanie zbiorów

Speaker(s)

Marek Cygan

Affiliation

Uniwersytet Warszawski

Date

Oct. 20, 2016, 2:15 p.m.

Room

room 5440

Seminar

Colloquium Of MIM

---

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