Teoretyczne informatyka max-cut

3

G=(V,E,w)G = (V, E, w)w:E→Rw:E\rightarrow \mathbb{R}arg max S ⊂ V ∑ ( u , v ) ∈ E : u ∈ S , v ∉ S w ( u , v ) w ( e ) ≥ 0 e ∈ EargmaxS⊂V∑(u,v)∈E:u∈S,v∉Sw(u,v)\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, …

35 ds.algorithms graph-theory approximation-algorithms max-cut

2

Algorytm Max-Cut, który nie powinien działać, nie wiadomo dlaczego

OK, może się to wydawać pytaniem o pracę domową iw pewnym sensie tak jest. Jako zadanie domowe w klasie algorytmów licencjackich podałem następujący klasyk: Biorąc pod uwagę nieukierowany wykres , podaj algorytm, który znajdzie cięcie taki sposób, że , gdzie to liczba krawędzi przecinających cięcie. Złożoność czasowa musi wynosić .G=(V,E)G=(V,E)G=(V,E)(S,S¯)(S,S¯)(S,\bar{S})δ(S,S¯)≥|E|/2δ(S,S¯)≥|E|/2\delta(S,\bar{S})\geq …

21 graph-algorithms max-cut greedy-algorithms

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

2

Maksymalne cięcie w kształcie euklidesa w małych wymiarach

x1,…,xnx1,…,xnx_1, \ldots, x_nR2R2\mathbb{R}^2∥xi−xj∥2‖xi−xj‖2\|x_i - x_j\|^22323\frac 2 32323\frac 2 3 Najgorszy przykład, jaki mogę znaleźć, to 3 punkty na równobocznym trójkącie, który osiąga . Zauważ, że losowy podział dałby , ale intuicyjnie wydaje się intuicyjnie, że w niskich wymiarach można skupić się lepiej niż losowo.2323\frac 2 31212\frac 1 2 Co się …

12 ds.algorithms graph-algorithms application-of-theory max-cut clustering

3

Problem wielokrotnego cięcia

Szukam nazwy lub jakichkolwiek odniesień do tego problemu. Biorąc pod uwagę wykres ważony G=(V,E,w)G=(V,E,w)G = (V, E, w) znajdź podział wierzchołków na n=|V|n=|V|n = |V|ustawia S1,…,SnS1,…,SnS_1,\ldots,S_n tak, aby zmaksymalizować wartość przyciętych krawędzi: c(S1,…,Sn)=∑i≠j⎛⎝∑(u,v)∈E:u∈Si,v∈Sjw(u,v)⎞⎠c(S1,…,Sn)=∑i≠j(∑(u,v)∈E:u∈Si,v∈Sjw(u,v))c(S_1,\ldots,S_n) = \sum_{i \ne j}\left(\sum_{(u,v)\in E : u \in S_i, v \in S_j}w(u,v)\right) Zauważ, że niektóre zestawySiSiS_imogą być …

12 ds.algorithms reference-request approximation-algorithms max-cut

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

sieci w odniesieniu do normy cięcia

Przeciętna norma ||A||C||ZA||do||A||_C rzeczywistej macierzy A=(ai,j)∈Rn×nZA=(zaja,jot)∈Rn×nA = (a_{i,j}) \in \mathcal{R}^{n\times n} jest maksimum we wszystkich I⊆ [ n ] ,J⊆ [ n ]ja⊆[n],jot⊆[n]I \subseteq [n], J \subseteq [n] ilości ∣∣∑i ∈I, j ∈ Jzaja , j∣∣|∑ja∈ja,jot∈jotzaja,jot|\left|\sum_{i \in I, j \in J}a_{i,j}\right|. Zdefiniuj odległość między dwiema macierzami ZAZAA i bbB aby …

10 graph-theory co.combinatorics metrics max-cut epsilon-nets

1

Czysto teoretyczne objaśnienie redukcji z Unique Label Cover do Max-Cut

Studiuję Unique Games Conjecture i słynną redukcję do Max-Cut Khota i in. Ze swojej pracy i innych stron internetowych większość autorów używa (jak dla mnie) niejawnej równoważności między redukcją MAX-CUT a budowaniem konkretnych testów dla długich kodów. Z powodu mojego braku jasności co do tej równoważności staram się podążać tym …

9 cc.complexity-theory approximation-hardness pcp max-cut unique-games-conjecture

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

Pytania otagowane jako max-cut