Pytania otagowane jako integrality-gap

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 …

44 cc.complexity-theory  ds.algorithms  approximation-algorithms  linear-programming  integrality-gap 

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 …

18 ds.algorithms  approximation-algorithms  linear-programming  integrality-gap 

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 

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