Pytania otagowane jako smoothed-analysis

6
Złożoność algorytmu simpleks
Jaka jest górna granica algorytmu simpleks dla znalezienia rozwiązania dla programu liniowego? Jak mam znaleźć dowód na taką sprawę? Wydaje się, że najgorszym przypadkiem jest konieczność odwiedzenia każdego wierzchołka, czyli . Jednak w praktyce algorytm simpleks będzie działał znacznie szybciej niż w przypadku bardziej standardowych problemów.O ( 2n)O(2n)O(2^n) Jak mogę …
2
Paradygmaty analizy złożoności algorytmów
Analiza najgorszych i średnich przypadków to dobrze znane miary złożoności algorytmu. Niedawno wygładzona analiza pojawiła się jako kolejny paradygmat wyjaśniający, dlaczego niektóre algorytmy wykładnicze w najgorszym przypadku działają tak dobrze w praktyce, na przykład algorytm simpleksowy. Moje pytanie brzmi - czy istnieją jakieś inne paradygmaty do pomiaru złożoności algorytmu? Szczególnie …
1
Płynna analiza algorytmów aproksymacyjnych
Wygładzona analiza była stosowana wiele razy, aby zrozumieć czas działania dokładnych algorytmów dla wielu problemów, takich jak programowanie liniowe i k-średnich. Istnieją dość ogólne wyniki w tej dziedzinie, na przykład Heiko Röglin i Berthold Vöcking, Analiza wygładzania programowania liczb całkowitych , 2005. Niektóre z tych ogólnych wyników wydają się polegać …
1
Analiza wygładzona: jeśli problem ma złożoność pseudopolinomialną, czy jest on płynny?
Zafascynowała mnie niezwykła eksplozja w analizie wygładzonej i uderzyło mnie stwierdzenie w artykule Analiza wygładzonego programowania liczb całkowitych . Stwierdzono, że programowanie liniowe w liczbach całkowitych jest wygładzone P, jeśli jest ograniczone wielomianowo. Było to niezbędne, ponieważ programowanie liczb całkowitych jest pseudo-wielomianowe! Pytanie zatem brzmi: Czy to uniwersalnie przenosi się …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.