max-cut Archives

$G = (V, E, w)$

G = (V, E, w)

$G = (V, E, w)$ $w : E \to R$

w : E \to R

$w:E\rightarrow \mathbb{R}$

\arg max_{S \subset V} \sum_{(u, v) \in E : u \in S, v \notin S} w (u, v)

$\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, v \not \in S}w(u,v)$ $w (e) \geq 0$

w (e) \geq 0

$w(e) \geq 0$ $e \in E$

e \in E

$e \in E$

꼭짓점 의 무작위 하위 집합을 선택합니다 . $S$
정점에서 순서를 정하고, 정점 를 또는 에 탐욕스럽게 배치 하여 가장자리를 지금까지 최대화합니다. $v$
로컬 개선 : $S$

이러한 모든 알고리즘의 표준 분석에 따르면 결과 컷의 크기는 적어도 만큼 크며 $\frac{1}{2} \sum_{e \in E} w (e)$

\frac{1}{2} \sum_{e \in E} w (e)

$\frac{1}{2}\sum_{e \in E}w(e)$ 이는 의 상한입니다. 가 음이 아닌 $1 / 2$

1 / 2

$1/2$ 경우 최대 컷의 무게 -일부 모서리에 음의 무게가 허용되는 경우에는 그렇지 않습니다! $w$

w

$w$

예를 들어 알고리즘 1 (정점의 임의의 하위 집합 선택)은 음의 가중치를 갖는 그래프에서 명확하게 실패 할 수 있습니다.

내 질문은 :

음의 간선 가중치를 가질 수있는 그래프에서 최대 컷 문제에 대한 O (1) 근사값을 얻는 간단한 조합 알고리즘이 있습니까?

최대 컷 촬영 값의 가능한 접착 문제를 방지하기 위해 , 그 수 , 및 / 또는 알고리즘을 만족할뿐만 아니라 작은 첨가제 오류가 발생할 것을 곱셈 계수 근사치. $0$

0

$0$ $\sum_{e \in E} w (e) > 0$

\sum_{e \in E} w (e) > 0

$\sum_{e \in E}w(e) > 0$

답변

여기 논쟁에 대한 첫 번째 시도가있었습니다. 잘못되었지만 “EDIT :”다음에 수정했습니다.

네거티브 엣지 웨이트로 최대 컷 문제를 효율적으로 거의 해결할 수 있다면, 포지티브 엣지 웨이트로 최대 컷 문제를 해결하는 데 사용할 수 없습니까? 최적의 해가 인 해결하고자하는 최대 컷 문제로 시작하십시오 . 이제 와 사이에 큰 음의 가중치 가장자리 (weight )를 넣으십시오 . 새로운 문제의 최적 솔루션은 이므로 가설 근사 알고리즘은 최대 값이 최대 최적 컷 보다 더 큰 최대 컷을 가진 솔루션을 제공 합니다. 원래 그래프에서 최대 컷은 여전히 최적보다 최대 나빠졌습니다. 가까운 것을 선택 $b$

b

$b$ $- a$

- a

$-a$ $u$

u

$u$ $v$

v

$v$ $b - a$

b - a

$b-a$ $(b - a) / 2$

(b - a) / 2

$(b-a)/2$ $(b - a) / 2$

(b - a) / 2

$(b-a)/2$ $a$

a

$a$ $b$

b

$b$ 이는 P NP 인 경우 최대 컷을 팩터 보다 더 잘 근사화 할 수 없다는 근사치 결과를 위반합니다 . $\neq$

\neq

$\neq$ $16 / 17$

16 / 17

$16/17$

편집하다:

와 가 원래 그래프 인 경우에도 와 가 컷의 반대쪽에 있다고 보장 할 수 없기 때문에 위의 알고리즘은 작동하지 않습니다 . 그래도 다음과 같이 해결할 수 있습니다. $u$

u

$u$ $v$

v

$v$

모든 엣지 가중치의 합이 양수인 한 OPT의 계수 2 내에서 컷을 제공하는 근사 알고리즘이 있다고 가정합시다.

위와 같이 모서리에 모든 음이 아닌 가중치 가있는 그래프 로 시작하십시오 . 우리는 수정 된 그래프 찾을 수 있습니다 우리의 최대 컷에 근접 할 수 있다면 그런 부정적인 무게와 함께 2 배 내에서, 우리의 최대 컷에 근접 할 수 아주 잘. $G$

G

$G$ $G^{*}$

G^{*}

$G^*$ $G^{*}$

G^{*}

$G^*$ $G$

G

$G$

두 개의 정점 와 선택 하고 최대 컷의 반대편에 있기를 바랍니다. ( 한 번의 시도가 작동하도록 가능한 모든 에 대해이 작업을 반복 할 수 있습니다 .) 이제 에 대해 모든 모서리 및 에 큰 음의 가중치 를 입력 하고 a 큰 양의 가중치 on edge . 최적 절단의 중량이 라고 가정하십시오 . $u$

u

$u$ $v$

v

$v$ $v$

v

$v$ $- d$

- d

$-d$ $(u, x)$

(u, x)

$(u,x)$ $(v, x)$

(v, x)

$(v,x)$ $x \neq u, v$

x \neq u, v

$x \neq u,v$ $a$

a

$a$ $(u, v)$

(u, v)

$(u,v)$ $O P T$

O P T

$OPT$

정점 와 가 절단의 같은면에있는 값 가 인 절단은 이제 값을 여기서 은 절단의 다른면에있는 정점의 수입니다. 원래 값이 반대쪽에 를 사용한 컷의 값은 입니다. 우리의 선택에 따라서, 큰만큼, 우리는 모든 상처 강제로 와 때문에 양의 값을 가진 임의의 절단이 있다면 음의 값을 가지고 동일한 측을,의 다음 최적 절단 것이다 및 $c$

c

$c$ $G$

G

$G$ $u$

u

$u$ $v$

v

$v$ $c - 2 d m$

c - 2 d m

$c - 2dm$ $m$

m

$m$ $(u, v)$

(u, v)

$(u,v)$ $c$

c

$c$ $c + a - (n - 2) d$

c + a - (n - 2) d

$c + a - (n-2)d$ $d$

d

$d$ $u$

u

$u$ $v$

v

$v$ $G^{*}$

G^{*}

$G^*$ $u$

u

$u$ $v$

v

$v$ 반대쪽에. 우리는 반대쪽에 와 가있는 컷에 고정 무게 a- 를 추가하고 있습니다. $(a - (n - 2) d)$

(a - (n - 2) d)

$(a - (n-2)d)$ $u$

u

$u$ $v$

v

$v$

이라고하자 . 되도록 선택하십시오 (나중에 이것을 정당화 할 것입니다). 중량으로 잘라 에서 갖는 및 양측에 현재 체중과 절단하게 . 이는 의 최적 절단 중량이 임을 의미합니다 . 우리의 새로운 알고리즘은 무게가 이상인 에서 컷을 찾습니다 . 이는 중량이 이상인 원래 그래프 의 컷으로 변환됩니다 ( 양의 가중치가 분리 된 모든 컷이므로 $f = (a - (n - 2) d)$

f = (a - (n - 2) d)

$f=(a - (n-2)d)$ $a$

a

$a$ $f \approx - 0.98 O P T$

f \approx - 0.98 O P T

$f \approx - 0.98 OPT$ $c$

c

$c$ $G$

G

$G$ $u$

u

$u$ $v$

v

$v$ $c - 0.98 O P T$

c - 0.98 O P T

$c - 0.98 OPT$ $G^{*}$

G^{*}

$G^*$ $0.02 O P T$

0.02 O P T

$0.02 OPT$ $G^{*}$

G^{*}

$G^*$ $0.01 O P T$

0.01 O P T

$0.01 OPT$ $G$

G

$G$ $0.99 O P T$

0.99 O P T

$0.99OPT$ $G^{*}$

G^{*}

$G^*$ $u$

u

$u$ 및 )는 근사치 결과보다 낫습니다. $v$

v

$v$

를 원하는만큼 크게 선택할 수 있기 때문에 같은 쪽의 와 를 자르기에 충분한 를 선택해도 아무런 문제가 없습니다 . 그러나 때 되도록 어떻게 선택 했 습니까? 우리는 대략 수 우리가 허락한다면 … 정말 잘 에서 에지 가중치의 합 , 우리는 알고 . 따라서 우리는 에 대해 상당히 좁은 범위의 값을 , 와 사이의 모든 값을 를 반복 할 수 있습니다 $d$

d

$d$ $u$

u

$u$ $v$

v

$v$ $d$

d

$d$ $a$

a

$a$ $f \approx - .99 O P T$

f \approx - .99 O P T

$f \approx -.99OPT$ $O P T$

O P T

$OPT$ $O P T$

O P T

$OPT$ $T$

T

$T$ $G$

G

$G$ $\frac{1}{2} T \leq O P T \leq T$

\frac{1}{2} T \leq O P T \leq T

$\frac{1}{2}T \leq OPT \leq T$ $f$

f

$f$ $f$

f

$f$ $- .49 T$

- .49 T

$-.49T$ $- .99 T$

- .99 T

$-.99T$ 간격으로 . 이러한 간격 중 하나에 대해 가 보장되므로 이러한 반복 중 하나가 양호한 컷을 반환합니다. $0.005 T$

0.005 T

$0.005T$ $f \approx - 0.98 O P T$

f \approx - 0.98 O P T

$f \approx -0.98 OPT$

마지막으로, 새 그래프의 합이 양인 모서리 가중치를 가지고 있는지 확인해야합니다. 우리는 그 에지 가중치 합산 한 그래프를 시작 , 그리고 추가 에지의 가중치의 합. 이후 , 우린 OK $T$

T

$T$ $f$

f

$f$ $- .99 T \leq f \leq - .49 T$

- .99 T \leq f \leq - .49 T

$-.99T \leq f \leq -.49T$

답변

S. Har-Peled의 ” Approximate Max Cut ” 기사 에서, 논문의 마지막 줄은 max-cut의 실제 가중 버전이

SIAM Journal on Computing, grothendieck의 불평등 , Noga Alon 및 Assaf Naor 를 통한 컷 노름 근사 .

실제로 SDP 알고리즘이며, 논문에서 논의 된 감소가 비율 보존인지 확실하지 않지만 근사 비율은 0.56 인 것 같습니다. 종이를 더 깊이 들여다 보면 도움이 될 것입니다!

답변

문제는 2 차 프로그래밍 문제로 축소하여 로그 근사값을 갖습니다.

MaxQP 문제는 행렬 대해 이차 형태 를 근사하는 문제입니다 . 여기서 는 입니다. MaxCut은 를 설정하여이 형식으로 작성할 수 있습니다 여기서 은 항등 행렬이고 는 인접 행렬입니다. Charikar 및 Wirth 의 MaxQP 알고리즘은 이 음이 아닌 대각선을 갖는 한 MaxQP에 대해 근사값을 제공합니다 . 따라서 이면 가중치가 음수 인 MaxCut은 로그 근사값을 갖습니다. $x^{T} M x$

x^{T} M x

$x^TMx$ $n \times n$

n \times n

$n \times n$ $M$

M

$M$ $x$

x

$x$ ${\pm 1}^{n}$

{\pm 1}^{n}

$\{\pm 1\}^n$ $M = \frac{1}{2 n} (\sum w_{e}) I - \frac{1}{2} A$

M = \frac{1}{2 n} (\sum w_{e}) I - \frac{1}{2} A

$M = \frac{1}{2n}(\sum{w_e})I - \frac{1}{2}A$ $I$

I

$I$ $A$

A

$A$ $O (\log n)$

O (\log n)

$O(\log n)$ $M$

M

$M$ $\sum w_{e} \geq 0$

\sum w_{e} \geq 0

$\sum{w_e} \geq 0$

How IT

언제든지 물어보세요.

태그 보관물: max-cut

마이너스 웨이트 엣지로 최대 컷 선택합니다 .SSS 정점에서 순서를 정하고, 정점 를

답변

답변

답변

답변