Opracowałem nową technikę derandomizacji, która ma na celu rekurencyjne algorytmy randomizowane (lub) bardziej ogólnie algorytmy randomizowane, które wykorzystują stos. Niestety nie mogłem znaleźć naturalnych, losowych algorytmów do zastosowania moich technik. Rekurencyjne łańcuchy Markowa i gramatyki stochastyczne są bardzo zbliżone do tego, czego szukam. Czy istnieją inne (bardziej naturalne) randomizowane algorytmy, które wykorzystują stos w sposób „niezbędny”? Każda pomoc jest mile widziana, ponieważ utknąłem w tym od ponad sześciu miesięcy.
Aby dać ci więcej kontekstu, szukam listy problemów podobnych do tych w SivaKumar's Paper . Zauważ, że SivaKumar użył generatora pseudolosowego Nisana do derandomizacji tych problemów.
randomness
derandomization
Shiva Kintali
źródło
źródło
Odpowiedzi:
Jak zauważa Per Vognsen, a bardziej ogólnie, istnieje wiele algorytmów geometrycznych, które działają w następujący sposób: Wybierz losową próbkę i uruchom rekurencyjnie na próbce i innych pochodnych strukturach. Losowy algorytm Clarksona do programowania liniowego, a także Seidela, a nawet seria Matousek-Sharir-Welzl, o której wspomina, wszystkie działają w ten sposób, a paradygmat Clarkson rozciąga się na inne sytuacje, w których budujesz coś w rodzaju cięcia lub epsilon-net i rekurencję .
Niestety jest mało prawdopodobne, aby uzyskać z tego nowy wynik, ponieważ istnieją optymalne derandomizacje tych algorytmów, z powodu pracy Matouseka i Chazelle. Artykuł Chazelle jest dobrym punktem odniesienia dla tej pracy i wcześniejszej pracy Matouseka. Ale może to być dobry test twojej metody: ciężko było wymyślić te derandomizacje, a jeśli twoja metoda zapewnia podejście do czarnej skrzynki, zaczynając od (łatwiejszego) randomizowanego algorytmu, byłoby dobrze.
ps jest to prawdopodobnie najbardziej nudny przykład, ale czy twoja metoda działa na Quicksort, czy na dowolnej z losowych metod wyszukiwania mediany?
źródło
A co z przypadkowym algorytmem Welzla do minimalizowania otaczających elipsoid? Ma głębokość rekurencji O (d), gdzie d jest wymiarem przestrzeni.
Nie wiem prawie nic o derandomizacji, więc może to nie jest to, czego szukasz. Jeśli mój przykład się nie kwalifikuje (może z twojej definicji tylko nieistotne jest użycie rekurencji?), Być może mógłbyś wyjaśnić, dlaczego tak jest. Zwiększyłoby to szanse na wyższą jakość, bardziej trafne odpowiedzi od innych.
źródło
Szybsza wersja algorytmu min-cut jest rzeczywiście bardzo rekurencyjna. Zobacz rysunek 2.5 tutaj lub dowolny standardowy podręcznik algorytmów losowych.
źródło