Optymalizacja kombinatoryczna w warunkach niepewności

Rozważmy portal randkowy (nie tinder), w którym są 44 tysiące kobiet i 44 tysięce mężczyzn. Portal zarabia na miesięcznej subskrypcji, a jego zadaniem jest proponowanie użytkownikom randek. Portal używając danych użytkowników (np. z ankiet na temat cech charakteru, ulubionych filmów i muzyki itd) jest w stanie całkiem nieźle wyestymować dla każdej pary użytkowników prawdopodobieństwo, że dana para się sobie wzajemnie spodoba, o ile tylko pójdzie na randkę. Pytanie jednak jest następujące: w jaki sposób portal powinien proponować randki, aby zmaksymalizować średnią (lub też totalną w ciągu roku) liczbę szczęśliwie skojarzonych par? Nie możemy przecież wysłać żadnego użytkownika na 100 nieudanych randek, bo do tego czasu zrezygnuje z subskrypcji. Musimy więc robić to ostrożnie. Co więcej dana para, jeśli tylko się sobie spodoba, to natychmiast opuszcza portal (a przynajmniej takie jest sensowne założenie). Gdyby nie było tutaj żadnej niepewności i a priori byśmy wiedzieli, które pary się sobie spodobają, a które nie, to naszym zadaniem byłoby obliczenie po prostu maksymalnego skojarzenia w grafie, które możemy zrobić całkiem sprawnie w czasie wielomianowym. Ale gdy uwzględnimy stochastyczną naturę, czyli że randki mogą się udać albo się nie udać, to problem — mimo, że cały czas dotyczy skojarzeń w grafach — staje się nagle zgoła inny. Co więcej, teraz nawet nie tyle, co nie znamy wielomianowego algorytmu, ale nawet nie wiemy, czy ten problem należy do klasy NP. Mimo wszystko na wykładzie zobaczymy 2-aproksymacyjny algorytm dla tego problemu.

Istotą tego przydługiego wstępu była ilustracja faktu, że bardzo często prawdziwie praktyczne problemy mają pewien aspekt niepewności w sobie, a ten z kolei wymusza zupełnie inne podejście do problemu niż w przypadku jego deterministycznego odpowiednika. Na wykładzie przedstawię kilka klasycznych modeli niepewności: stochastyczne próbkowanie (przykład portalu randkowego), problem sekretarki (https://en.wikipedia.org/wiki/Secretary_problem), nierówność Proroka (https://en.wikipedia.org/wiki/Prophet_inequality) i algorytmy online oraz jak w tych modelach rozważać struktury kombinatoryczne takie jak skojarzenia lub matroidy (na wykładzie wytłumaczę co to).

Przedmiot będzie mocno matematyczny, a nawet mocno probabilistyczny, jednak nie będziemy potrzebować żadnego zaawansowanego aparatu — znajomość warunkowej wartości oczekiwanej w zupełności wystarczy.

28 II Problem Sekretarki

Mateusz Orda

link

7 III Crash course programowania liniowego

MAX-SAT, vertex cover, max-matching

Mateusz Leonowicz

link

14 III Contention resolution scheme dla matchingów

8-approx union boundem, całka po iloczynie, iteratywne randomizowane zaokrąglanie z argumentem martyngałowym

Adrian Urbański, Maciej Malicki

link

21 III Stochastyczny matching part I

8-approx union boundem, 4-approx greedy'ego

Franciszek Malinka

link

28 III Stochastyczny matching part II; Prorok

LP-based 4-approx greedy'ego; prosty prorok

Adrianna Wilińska, Maria Wyrzykowska

link

4 IV Stochastyczny matching part III

iteratywne randomizowane zaokrąglanie, matroid partycji

Krzysztof Wasielewski, Jacek Kowalski

link