Optymalizacja submodularna 2022
Harmonogram
1 1-03-2022
algorytm zachłanny dla Max Cover
definicja submodularności
Algorytm dla max cover omawiany na pierwszym wykładzie jest zgrabnie opisany w tych oto notatkach http://viswa.engin.umich.edu/wp-content/uploads/sites/169/2021/02/greedy.pdf
Definicje funkcji submodularnych i ich przykłady są podane tutaj (sekcja 1) https://theory.stanford.edu/~jvondrak/CS369P/lec16.pdf
Dowód twierdzenia o równoważnościach definicji jest podany w Lemacie 11 z tych notatek https://theory.stanford.edu/~jvondrak/CS369P/lec8.pdf
2 8-03-2022
Algorytm zachłanny dla maksymalizacji funkcji submodularnej z ograniczeniem na ilość
algorytm randomizowany dla max cuta
Algorytm zachłanny opisany jest tutaj (sekcja 3.1) https://theory.stanford.edu/~jvondrak/CS369P/lec16.pdf
randomizowany Max Cut tutaj (sekcja 2.3.4) https://people.seas.harvard.edu/~salil/pseudorandomness/power.pdf
3 15-03-2022
algorytm ślepy i deterministyczny dla max cuta
argument niekonstruktywny dla max-cuta o logarytmicznej liczbie zbiorow, ktore daja stałą aproksymację
deterministyczny adaptywny max cut tutaj (sekcja 3.4.2) https://people.seas.harvard.edu/~salil/pseudorandomness/basic.pdf
deterministyczny i ślepy tutaj (sekcja 3.5.1) https://people.seas.harvard.edu/~salil/pseudorandomness/basic.pdf
nierówność Chernoffa tutaj (sekcja 5.10) https://www.designofapproxalgs.com/book.pdf
niekonstruktywny max cut tutaj (sekcja 2 i 3) https://drive.google.com/file/d/1OzaVDa_2P1yVS45GPKIVWgeoFHBruK0G/view?usp=sharing
dla zainteresowanych: konstruktywna ślepa i deterministyczna stałą aproksymacja dla max cuta, który wykorzystuje tylko logarytmiczną liczbę podzbiorów jest opisana tutaj (ćwiczenie 3.4) https://people.seas.harvard.edu/~salil/pseudorandomness/basic.pdf
4 22-03-2022
max-cut z ograniczeniem ilościowym za pomocą programowania liniowego i pipage roundingu
algorytm ślepy i randomizowany dla funkcji submodularnych
pipage rounding dla max cuta tutaj (ćwiczenie 4.7) https://www.designofapproxalgs.com/book.pdf
randomizowana i ślepa 1/4 aproksymacja dla ogólnych funkcji submodularnych tutaj (sekcja 2.1.1) https://theory.stanford.edu/~jvondrak/data/KAM_thesis.pdf
5 29-03-2022
adaptywna deterministyczna 1/3-aproksymacja i randomizowana 1/2-aproksymacja algorytm optymalizacji submodularnej bez ograniczeń
deterministyczna ślepa aproksymacja?
deterministyczny algorytm w sekcji 2 a randomizowany w sekcji 3 tutaj https://theory.epfl.ch/moranfe/Publications/FOCS2012.pdf
deterministyczna i ślepa stała aproksymacja dla stożka funkcji submodularnych rozpiętych przez wykładniczą liczbę promieni tutaj (sekcja 4 i 5) https://drive.google.com/file/d/1OzaVDa_2P1yVS45GPKIVWgeoFHBruK0G/view?usp=sharing
6 5-04-2022
ciągłe rozszerzenia funkcji submodularnych; probabilistyczna intuicja; rozszerzenie wieloliniowe i rozszerzenie Lovasza
minimalizacja funkcji submodularnych za pomocą rozszerzenia Lovasza
rozszerzenie Lovasza i minimalizacja tutaj (sekcja 1) https://theory.stanford.edu/~jvondrak/CS369P/lec17.pdf
na ten sam temat ale nieco bardziej mięsiście tutaj https://www.cs.princeton.edu/~singla/Fall20cos521/lec17.pdf
7 12-04-2022
metoda elipsoid
8 26-04-2022
rownowaznosc min-cuta i maksymalnego przeplywu
9 17-05-2022
luka korelacji
10 24-05-2022
maksymalizacja funkcji submodularnej wzgledem matroidu
continuous greedy
11 7-06-2022
maksymalizacja funkcji submodularnej wzgledem matroidu
continuous greedy
12 14-05-2022
matroidy i dlaczego wieloscian matroidów ma tylko całkowitoliczbowe wierzchołki