Pytania otagowane jako linear-programming

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 najmniejsza dysku zawierającej ⋃B⋃B\bigcup B . …

17 cg.comp-geom  linear-programming  computational-geometry 

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, pod warunkiem, że możemy dla nich zaprojektować wielomianową wyrocznię z separacją czasu. …

17 linear-programming  semidefinite-programming  convex-optimization 

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 większości danych wejściowych) algorytm simpleks kończy się szybko. Pamiętam z mojego kursu programowania matematycznego, …

17 cc.complexity-theory  reference-request  linear-programming  simplex 

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 wyszukiwanie binarne. Obie te redukcje są wielomianowe, ale nie silnie wielomianowe (tzn. Zależą od liczby …

15 ds.algorithms  linear-programming 

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 …

15 reference-request  np-hardness  counting-complexity  linear-programming  polytope 

Rozważmy wektor zmiennych i zestaw wiązań liniowych określonych przez A → x ≤ b .x⃗ x→\vec{x}Ax⃗ ≤bAx→≤bA\vec{x}\leq b Ponadto rozważ dwa polytopy P1P2={(f1(x⃗ ),⋯,fm(x⃗ ))∣Ax⃗ ≤b}={(g1(x⃗ ),⋯,gm(x⃗ ))∣Ax⃗ ≤b}P1={(f1(x→),⋯,fm(x→))∣Ax→≤b}P2={(g1(x→),⋯,gm(x→))∣Ax→≤b}\begin{align*} P_1&=\{(f_1(\vec{x}), \cdots, f_m(\vec{x}))\mid A\vec{x}\leq b\}\\ P_2&=\{(g_1(\vec{x}), \cdots, g_m(\vec{x}))\mid A\vec{x}\leq b\} \end{align*} gdzie ' ig ' s są odwzorowaniami afinicznymi . Mianowicie …

14 cc.complexity-theory  linear-algebra  linear-programming  polytope 

W artykule Randomized Primal-Dual analiza RANKING dla Online Dwustronnego dopasowywania , udowadniając jednocześnie, że algorytm RANKING jest -konkurencyjne, autorzy pokazują, że dualność jest wykonalna w oczekiwaniu (patrz Lemat 3 na stronie 5). Moje pytanie brzmi:(1−1e)(1−1e)\left(1 - \frac{1}{e}\right) Czy wystarczy, aby ograniczenia programu liniowego były spełnione w oczekiwaniu? Jedną rzeczą jest …

14 linear-programming  randomized-algorithms  online-algorithms  matching  primal-dual 

Rozważmy nnn -wymiarowej przestrzeni {0,1}n{0,1}n\{0,1\}^n , niech ccc być liniowy ograniczenie formy 1 x 1 + 2 x 2 + 3 x 3 + . . . + a n - 1 x n - 1 + a n x n ≥ k , gdzie a i ∈ R , …

14 reference-request  co.combinatorics  optimization  linear-programming  convex-optimization 

Wiemy, że jeśli różnica między wartościami programu liczb całkowitych i jego dualności („dualność”) wynosi zero, wówczas liniowe relaksacje programowania programu liczb całkowitych i dualność relaksacji dopuszczają rozwiązania integralne (integralność zerowa) luka"). Chcę wiedzieć, czy konwersacja się utrzymuje, przynajmniej w niektórych przypadkach. Załóżmy, że mam program liczb całkowitych 0-1 , gdzie …

14 ds.algorithms  optimization  linear-programming  integrality-gap 

Interesuje mnie implementacja SM dla zadania LP, jednak słyszałem o możliwych pułapkach: książka Cormena mówi, że możliwe jest posiadanie danych wejściowych, które sprawią, że naiwna implementacja zachowa się w wykładniczym czasie. Słyszałem również, że naiwna implementacja może zapętlać dane. Czy istnieje książka / artykuł / źródło wyjaśniające niuanse praktycznego wdrażania …

14 ds.algorithms  linear-programming  software  implementation  simplex 

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 r., Który nadał mu nazwę „algorytm węgierski”, ponieważ algorytm był oparty na wcześniejszych pracach dwóch …

14 graph-theory  reference-request  graph-algorithms  linear-programming  primal-dual 

Napisałem implementację algorytmu Kuhna-Munkresa dla problemu dwustronnego idealnego dopasowania minimalnej wagi w oparciu o notatki z wykładu, które znalazłem tu i tam w Internecie. Działa naprawdę dobrze, nawet na tysiącach wierzchołków. I zgadzam się, że teoria jest naprawdę piękna. A jednak wciąż zastanawiam się, dlaczego musiałem tak bardzo się starać. …

14 ds.algorithms  graph-theory  linear-programming  simplex 

Jak trudno jest znaleźć najrzadsze rozwiązanie układu równań liniowych? Bardziej formalnie, rozważ następujący problem decyzyjny: Instancja: układ równań liniowych o współczynnikach całkowitych i liczbie ccc . Pytanie: Czy istnieje rozwiązanie dla systemu z co najmniej ccc zmiennymi przypisanymi do zera? Próbuję również ustalić, na czym polega zależność od ccc . …

13 np-hardness  linear-algebra  linear-programming  matrices  sparse-matrix 

Próbowałem następującej relaksacji LP maksymalnie niezależnego zestawu max∑iximax∑ixi\max \sum_i x_i s.t. xi+xj≤1 ∀(i,j)∈Es.t. xi+xj≤1 ∀(i,j)∈E\text{s.t.}\ x_i+x_j\le 1\ \forall (i,j)\in E xi≥0xi≥0x_i\ge 0 Dostaję 1/21/21/2 za każdą zmienną za każdy sześcienny dwudzielny wykres, który próbowałem. Czy to prawda dla wszystkich połączonych sześciennych dwudzielnych grafów? Czy istnieje relaksacja LP, która działa lepiej …

13 graph-theory  co.combinatorics  linear-programming 

Próbując rozwiązać problem, ostatecznie wyraziłem jego część jako następujący program liczbowy całkowity. Tutaj są dodatnimi liczbami całkowitymi podanymi jako część danych wejściowych. Określony podzbiór zmiennych jest ustawiony na zero, a reszta może przyjmować dodatnie wartości całki:ℓ,m,n1,n2,…,nℓ,c1,c2,…,cm,wℓ,m,n1,n2,…,nℓ,c1,c2,…,cm,w\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},wxijxijx_{ij} Zminimalizować ∑mj=1cj∑ℓi=1xij∑j=1mcj∑i=1ℓxij\sum_{j=1}^{m}c_{j}\sum_{i=1}^{\ell}x_{ij} Z zastrzeżeniem: ∑mj=1xij=ni∀i∑j=1mxij=ni∀i\sum_{j=1}^{m}x_{ij}=n_{i}\,\,\forall i ∑ℓi=1xij≥w∀j∑i=1ℓxij≥w∀j\sum_{i=1}^{\ell}x_{ij}\ge w\,\,\forall j Chciałbym wiedzieć, czy ten program …

13 reference-request  linear-programming  polynomial-time  integer-programming  integrality-gap