Aproksymacyjne pakowanie zbiorów

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