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...
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...
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...
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,...