Pytania otagowane jako linear-programming

Matematyczna i obliczeniowa metoda znalezienia najlepszego wyniku w danym modelu matematycznym, w którym lista wymagań jest reprezentowana jako relacje liniowe.

8
Znaczenie luki w integralności
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 znalezienie optymalnego rozwiązania liczb całkowitych następującego zestawu równań liniowych: Mamy zero / jednego o …
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ę …
1
Przykłady zabawek dla solverów Plotkin-Shmoys-Tardos i Arora-Kale
Chciałbym zrozumieć, w jaki sposób solver Arora-Kale SDP aproksymuje relaksację Goemansa-Williamsona w prawie liniowym czasie, jak solver Plotkin-Shmoys-Tardos aproksymuje ułamkowe problemy „upakowania” i „pokrycia” w prawie liniowym czasie oraz jak algorytmy są instancjami abstrakcyjnych ram „uczenia się od ekspertów”. Teza Kale'a ma doskonałą prezentację, ale bardzo trudno mi przejść bezpośrednio …
2
Jakie klasy programów matematycznych można rozwiązać dokładnie lub w przybliżeniu w czasie wielomianowym?
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 rozwiązać, ale uważam, że ich definicja „wydajnego” nie pokrywa się z definicją TCS. …
3
Konsekwencje istnienia silnie wielomianowego algorytmu programowania liniowego?
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 arytmetyka kosztów jednostkowych). Czy rozwiązanie tego pytania miałoby implikacje poza lepszymi algorytmami programowania liniowego? Na …
2
Czy istnieje algorytm wielomianowy do określania, czy rozpiętość zbioru macierzy zawiera macierz permutacji?
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 podejrzenia, że ​​gdyby istniało takie rozwiązanie, byłby to rodzaj algorytmu programowania …
3
Problemy z optymalizacją przy dobrej charakterystyce, ale bez algorytmu czasu wielomianowego
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 ? gggmaxxf(x)=minyg(y)maxxf(x)=minyg(y)\max_x f(x) = \min_y g(y)xxxnnnyyymmmnnnmmm Wiele naturalnych i ważnych problemów związanych z optymalizacją …
3
Jak szybko możemy rozwiązać całkowicie nieimodularny program liniowy liczb całkowitych?
(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ć dodatnie wartości całkowite:ℓ , m , n1, n2), …
1
Jakie są najlepsze możliwe kompromisy czas / błąd dla przybliżonego rozwiązania programów liniowych?
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 celu przybliżenia wartości tej gry.T.T.T Jedną …
2
Intuicyjny / nieformalny dowód na LP Duality?
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, podziela jedno zrozumienie: jestem pewien, że dla …
5
Czy można sprawdzić, czy liczba obliczalna jest wymierna czy całkowita?
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 z faktem, że nie można sprawdzić, czy dwie …
18 computability  computing-over-reals  lambda-calculus  graph-theory  co.combinatorics  cc.complexity-theory  reference-request  graph-theory  proofs  np-complete  cc.complexity-theory  machine-learning  boolean-functions  combinatory-logic  boolean-formulas  reference-request  approximation-algorithms  optimization  cc.complexity-theory  co.combinatorics  permutations  cc.complexity-theory  cc.complexity-theory  ai.artificial-intel  p-vs-np  relativization  co.combinatorics  permutations  ds.algorithms  algebra  automata-theory  dfa  lo.logic  temporal-logic  linear-temporal-logic  circuit-complexity  lower-bounds  permanent  arithmetic-circuits  determinant  dc.parallel-comp  asymptotics  ds.algorithms  graph-theory  planar-graphs  physics  max-flow  max-flow-min-cut  fl.formal-languages  automata-theory  finite-model-theory  dfa  language-design  soft-question  machine-learning  linear-algebra  db.databases  arithmetic-circuits  ds.algorithms  machine-learning  ds.data-structures  tree  soft-question  security  project-topic  approximation-algorithms  linear-programming  primal-dual  reference-request  graph-theory  graph-algorithms  cr.crypto-security  quantum-computing  gr.group-theory  graph-theory  time-complexity  lower-bounds  matrices  sorting  asymptotics  approximation-algorithms  linear-algebra  matrices  max-cut  graph-theory  graph-algorithms  time-complexity  circuit-complexity  regular-language  graph-algorithms  approximation-algorithms  set-cover  clique  graph-theory  graph-algorithms  approximation-algorithms  clustering  partition-problem  time-complexity  turing-machines  term-rewriting-systems  cc.complexity-theory  time-complexity  nondeterminism 
3
Luka integralności i współczynnik aproksymacji
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, których najlepszy współczynnik aproksymacji odpowiada luce integralności. Niektóre algorytmy mogą mieć lepszy współczynnik …
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.