Matematyczna i obliczeniowa metoda znalezienia najlepszego wyniku w danym modelu matematycznym, w którym lista wymagań jest reprezentowana jako relacje liniowe.
Rozważ rozłącznych rodzin podzbiorów {1,2,…, n}, F 1 , F 2 , … F t .tttfa1, F.2), … FtF1,F2,…Ft{\cal F}_1,{\cal F_2},\dots {\cal F_t} Przypuszczam, że (*) Dla każdego i każdy R ∈ F ı i T ∈ K K , jest S ∈ F j , który zawiera R ∩ T .i < j < ki<j<ki \lt j \lt kR ∈ FjaR∈FiR \in {\cal...
Zawsze miałem problem ze zrozumieniem znaczenia luki integralności (IG) i ją ograniczam. IG jest stosunkiem (jakości) optymalnej liczby całkowitej do (jakości) optymalnego rzeczywistego rozwiązania złagodzenia problemu. Rozważmy przykrycie wierzchołków (VC) jako przykład. VC można określić jako...
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...
Jednym ze świętych graali projektowania algorytmów jest znalezienie silnie wielomianowego algorytmu programowania liniowego, tj. Algorytmu, którego czas działania jest ograniczony wielomianem w liczbie zmiennych i ograniczeń i jest niezależny od wielkości reprezentacji parametrów (przy założeniu...
Jestem raczej zdezorientowany literaturą o ciągłej optymalizacji i literaturą TCS o tym, które rodzaje (ciągłych) programów matematycznych (MP) można skutecznie rozwiązać, a które nie. Wydaje się, że społeczność ciągłej optymalizacji twierdzi, że wszystkie programy wypukłe można skutecznie...
Chciałbym znaleźć algorytm wielomianowy, który określa, czy rozpiętość danego zestawu macierzy zawiera macierz permutacji. Jeśli ktoś wie, czy ten problem ma inną klasę złożoności, byłoby to równie pomocne. EDYCJA: Oznacziłem to pytanie za pomocą programowania liniowego, ponieważ mam poważne...
Według D. den Hertoga, Podejście punktu wewnętrznego do programowania liniowego, kwadratowego i wypukłego, 1994 , program liniowy z zmiennymi, ograniczeniami i precyzją jest rozwiązywalny w czasie . Czy to zostało
Rozważ problemy z optymalizacją w poniższym formularzu. Niech f(x)f(x)f(x) będzie funkcją obliczalną w czasie wielomianowym, która odwzorowuje ciąg xxx na liczbę wymierną. Problem optymalizacji jest następujący: jaka jest maksymalna wartość f(x)f(x)f(x) ponad nnn bitowych ciągów xxx...
To pytanie jest inspirowane wielomianową hipotezą Hirscha (PHC). Biorąc pod uwagę -facet polytop w , czy szczelina widmowa jego wykresu wierzchołek-krawędź (nazwij to ) jest niższa ograniczona przez ? Zauważ, że wykres cyklu wierzchołków pokazuje, że nawet dla szczelina widmowa może być tak mała...
(Jest to kontynuacja tego pytania i odpowiedzi ). Mam następujący całkowicie nieimodularny (TU) całkowity program liniowy (ILP). Tutaj są dodatnimi liczbami całkowitymi podanymi jako część danych wejściowych. Określony podzbiór zmiennych x i j jest ustawiony na zero, a reszta może przyjmować...
Jaki byłby dobry nieformalny / intuicyjny dowód na „trafienie w sedno” na temat dualności LP? Jak najlepiej wykazać, że zminimalizowana funkcja celu jest rzeczywiście minimalna, z intuicyjnym sposobem rozumienia granicy? Sposób, w jaki mnie uczono, doprowadził do tego, że DUŻO ludzi, które znam,...
Dla konkretności rozważ LP za rozwiązanie gry dla dwóch graczy o sumie zerowej, w której każdy gracz ma akcji. Załóżmy, że każdy zapis macierzy wypłat ma najwyżej 1 wartość bezwzględną. Dla uproszczenia nie róbmy żadnych założeń sparity.nnnZAZAA Załóżmy, że środowisko wykonawcze jest dostępne w...
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane...
Gdy weźmiemy pod uwagę algorytm aproksymacji dla problemu minimalizacji, luka integralności formuły IP dla tego problemu daje dolną granicę współczynnika aproksymacji dla pewnej klasy algorytmów (takich jak algorytm zaokrąglania lub pierwotny podwójny). W rzeczywistości istnieje wiele problemów,...
Wiemy, że programy liniowe (LP) można rozwiązać dokładnie w czasie wielomianowym za pomocą metody elipsoidy lub metody punktu wewnętrznego, takiej jak algorytm Karmarkara. Niektóre LP z super-wielomianową (wykładniczą) liczbą zmiennych / ograniczeń można również rozwiązać w czasie wielomianowym,...
O ile rozumiem, wszyscy znają deterministyczne reguły przestawne dla algorytmów simpleksowych mają określone dane wejściowe, na których algorytm wymaga czasu wykładniczego (lub przynajmniej nie wielomianowego), aby znaleźć optymalne. Nazwijmy te przypadki „patologicznymi”, ponieważ zwykle (tj. Na...
Załóżmy, że mamy skończony zbiór LLL dysków w R2R2\mathbb{R}^2 , i chcemy obliczyć najmniejszą dysku DDD , dla którego ⋃L⊆D⋃L⊆D\bigcup L\subseteq D . Standardowy sposób ten jest użycie algorytmu Matousek, Sharir i Welzl [1], aby znaleźć podstawę BBB z LLL i pozwolić D=⟨B⟩D=⟨B⟩D=\langle B\rangle...
Jednym ze sposobów wykazania, że sprawdzenie wykonalności liniowego układu nierówności jest tak trudne, jak programowanie liniowe, jest zmniejszenie za pomocą metody elipsoidalnej. Jeszcze łatwiejszym sposobem jest odgadnięcie optymalnego rozwiązania i wprowadzenie go jako ograniczenia poprzez...
Mam politotop P.PP zdefiniowany przez { x : A x ≤ b , x ≥ 0 }{x:Ax≤b,x≥0}\{ x : Ax \leq b, x \geq 0\} . Pytanie: Z uwagi wierzchołek vvv z P.PP , czy istnieje algorytm wielomianowy czas równomiernie próbki od sąsiadów vvv na wykresie P.PP ? (Wielomian w wymiarze, liczba równań i reprezentacja bbb...
Algorytm węgierski jest kombinatorycznym algorytmem optymalizacyjnym, który rozwiązuje problem dwustronnego dopasowania maksymalnej masy w czasie wielomianowym i przewidywał późniejszy rozwój ważnej metody pierwotnej podwójnej . Algorytm został opracowany i opublikowany przez Harolda Kuhna w 1955...