Jakie heurystyki polecacie?
Oczywiście na ten temat napisano setki jak nie tysiące publikacji, bo to klasyka, ale potrzebuję na szybko:

  1. Czegoś lepszego niż alg. zachłanny wybierający za każdym razem zbiór zawierający najwięcej elementów do tej pory niepokrytych. Ten alg. mam zaimplementowany, a teraz myślę, żeby troszkę poprawić wyniki, bo jest dosyć szybki (O (n log n)). Jeżeli w większości przypadków będzie dawać wyniki nie gorsze niż o 25% od optymalnego, to będzie super. Wiem, że się nie da takiej gwarancji zapewnić stricte matematycznie, ale chodzi o takie mniej więcej zdatne do zastosowania w przemyśle, nie w nauce.

  2. Czegoś działającego w sensownym czasie tj. O(n^2) maks., a najlepiej jakby można było odpalać w trybie "znajdź możliwie najlepsze rozwiązanie w zadanym czasie np. 10 ms"

  3. Czegoś w miarę prostego w implementacji lub posiadającego gotową bibliotekę (ale jeśli biblioteka to rozwijana, z kodem źródłowym i dostępna w maven). Jako proste w implementacji rozumiem coś co da się zrobić powiedzmy w 100-200 dodatkowych liniach kodu ponad heurystykę zachłanną, i nie trzeba tydzień rozgryzać co autor papieru miał na myśli.

Charakterystyka danych wejściowych:
Liczba zbiorów wejściowych raczej mała < 1000. Typowa wielkość każdego zbioru < 6. Wielkość zbioru do pokrycia < 1000.

Może robiliście coś na studiach i okazało się fajnie działać? Może być link do artykułu lub krótki opis, lub nawet nazwa algorytmu + info że działało dobrze lub źle.