Teoretyczne informatyka approximation-algorithms

2

Rozważ problem z zestawem dominującym na ogólnych wykresach i niech będzie liczbą wierzchołków na wykresie. Chciwy algorytm aproksymacji daje gwarancję aproksymacji współczynnika , tzn. Możliwe jest znalezienie w czasie wielomianowym rozwiązania takiego, że , gdzie jest rozmiarem minimalnego zestawu dominującego. Istnieją ograniczenia wskazujące, że nie możemy poprawić zależności od dużo …

10 cc.complexity-theory approximation-algorithms approximation-hardness

1

Przykłady trudnych instancji dla algorytmu Goemans i Williamson

Interesują mnie wyraźne przykłady wykresów, dla których zastosowanie algorytmu Goemansa i Williamsona do przybliżania maksymalnych cięć skutkuje współczynnikiem aproksymacji 0,878… Algorytm do tworzenia takich instancji byłby idealny, wyraźne przykłady i referencje są zadowalające.

10 ds.algorithms approximation-algorithms max-cut hard-instances

1

Relaks

Mam pytanie wykonalności, które można sformułować w następujący sposób. Ja dany punkt w -wymiarowej przestrzeni wektorowej i chcę, aby znaleźć najbliższy punkt do że spełnia zestaw „ ograniczeń” formularzadpppreddp ℓ 0qqqpppℓ0ℓ0\ell_0 Biorąc pod uwagę zestaw , co najwyżej jeden z może być niezerowy.S.∈ [ 1 … d]S∈[1…d]S \in [1\ldots d]{ …

10 ds.algorithms approximation-algorithms linear-programming

1

Dlaczego komplementarność jest ważna?

Komplementarny luz (CS) jest powszechnie nauczany, gdy mówi się o dualności. Ustanawia ładny związek między pierwotnym a podwójnym ograniczeniem / zmiennymi z matematycznego punktu widzenia. Dwa główne powody stosowania CS (zgodnie z nauczaniem na kursach dla absolwentów i podręcznikach): Aby sprawdzić optymalność LP Aby pomóc rozwiązać problem podwójny Biorąc pod …

10 ds.algorithms approximation-algorithms linear-programming primal-dual

1

Podzielić zbiór punktów na dwa optymalne podzbiory

Chcę podzielić zestaw punktów na dwa równe podzbiory, aby zminimalizować sumę kwadratów wewnątrz klastra. Możemy założyć, że punkty znajdują się w dwuwymiarowej przestrzeni euklidesowej. Mam nadzieję na coś szybszego niż ogólny algorytm grupowania k-średnich, biorąc pod uwagę, że k = d = 2. Czy ktoś może wskazać mi dobry algorytm? …

9 ds.algorithms approximation-algorithms clustering

2

Przybliżenie problemów trudnych do # P

Rozważ klasyczny problem # P-zupełny nr 3SAT, tj. Policz liczbę wycen, aby uzyskać 3CNF z nnnzmienne zadowalające. Interesuje mnie przybliżalność addytywna . Najwyraźniej istnieje prosty algorytm do osiągnięcia2)n - 12n−12^{n-1}- błąd, ale jeśli k <2)n - 1k<2n−1k<2^{n-1}, czy można mieć skuteczny algorytm aproksymacyjny, czy ten problem jest również trudny do …

9 approximation-algorithms sat counting-complexity approximation-hardness

3

Posadzona klika w G (n, p), zmieniająca się p

W przypadku problemu sadzonej kliki należy odzyskać kkk-klinka posadzona na losowym wykresie Erdosa-Renyi G ( n , p )G(n,p)G(n,p). To było głównie rozpatrywanep =12)p=12p=\frac{1}{2}, w którym to przypadku wiadomo, że można rozwiązać czas wielomianowy, jeśli k >n--√k>nk > \sqrt{n} i przypuszczalnie trudne k <n--√k<nk< \sqrt{n}. Moje pytanie brzmi: co wiadomo …

9 cc.complexity-theory approximation-algorithms approximation-hardness

4

Treewidth i pakowanie

Moje pytanie jest trochę niejasne. Zastanawiam się, czy (i jak) możemy zastosować pojęcie szerokości do problemów z upakowaniem na wykresach. Byłbym zadowolony z wszelkich spostrzeżeń lub odniesień do wcześniejszych prac badawczych na ten temat (zakładając, że jest to jakaś relacja). Dzięki.

9 ds.algorithms reference-request graph-theory graph-algorithms approximation-algorithms

1

Czy Max-Cut APX-complete na grafach bez trójkątów?

W problemie Max-Cut szuka się podzbioru S wierzchołków danego prostego niekierowanego wykresu, tak że liczba krawędzi między S a dopełnieniem S jest tak duża, jak to możliwe. Max-Cut jest kompletny APX na wykresach ograniczonego stopnia [PY91], i faktycznie APX-kompletny na wykresach sześciennych (tj. Grafach stopnia 3) [AK00]. Max-Cut jest NP-kompletny …

9 cc.complexity-theory approximation-algorithms approximation-hardness max-cut

1

Euklidesowy problem z pojemną lokalizacją obiektu

W instrumentu Capacitated Lokalizacja problem (CFLP) , daje nam szereg klientów oraz zestaw potencjalnych obiektów . Każdy klient ma żądanie które musi być obsługiwane przez jedno lub więcej otwartych obiektów. Każdy obiekt ma koszt otwarcia i ma pojemność , które jest popyt, że maksymalny zakład może służyć. Koszt obsługi jednej …

9 ds.algorithms cg.comp-geom approximation-algorithms

2

Maksymalizacja sumarycznych wag krawędzi

Zastanawiam się, czy następujący problem ma nazwę lub wyniki z nim związane. Niech będzie wykresem ważonym, gdzie oznacza wagę krawędzi między i , a dla wszystkich , . Problem polega na znalezieniu podzbioru wierzchołków, który maksymalizuje sumę wag sąsiadujących z nimi krawędzi: Zauważ, że liczę krawędzie, które są wewnątrz podzbioru …

9 reference-request graph-theory approximation-algorithms terminology approximation-hardness

1

Decyzja, czy ciąg znaków zastępczych jest całkowicie dopasowany do innego ciągu znaków zastępczych w zestawie

Oto problem, który dręczy mnie od dłuższego czasu. Powiedzmy, że łańcuch jest sekwencją 1 i 0, a łańcuch wieloznaczny to sekwencja 1, 0 i? S. Wszystkie ciągi znaków i symbole wieloznaczne mają tę samą długość. Są to standardowe symbole wieloznaczne UNIX; 10 ?? 1 pasuje do 10011, 10111 itd. - …

9 ds.algorithms ds.data-structures approximation-algorithms string-matching string-search

Pytania otagowane jako approximation-algorithms