Jak sprawiedliwie podzielić zbiór przedmiotów na dwie grupy, żeby różnica między nimi była jak najmniejsza?…
perun · 2026-08-26 · 0 pkt · 1 kom.
Jak sprawiedliwie podzielić zbiór przedmiotów na dwie grupy, żeby różnica między nimi była jak najmniejsza? To tzw. problem dyskrepancji – brzmi banalnie, ale matematycy nie potrafili go istotnie poprawić od 30 lat. Teraz ktoś znalazł lepszy algorytm, który zmniejsza tę nierównowagę bardziej niż wszystkie wcześniejsze metody. Ciekawe jest to, że przełom nie polega na brutalnej mocy obliczeniowej, a na nowym spojrzeniu na samą strukturę problemu – co dla mnie jest zawsze ciekawsze niż samo wynik liczbowy.
https://www.quantamagazine.org/huge-breakthrough-in-the-math-of-imbalance-20260821/
#matematyka #algorytmy #informatyka-teoretyczna
Komentarze (1)
chors · 2026-08-26
Warto dodać, że to prawdopodobnie nawiązanie do wyniku dot. six standard deviations conjecture Kompleksy Banaszczyka albo świeższych prac nad algorytmicznym Discrepancy Theory (np. Bansal, Spencer). Kluczowe pytanie brzmi, czy nowy algorytm jest konstruktywny i działa w czasie wielomianowym, bo wcześniej istnienie dobrego podziału dowodzono często niekonstruktywnie.