approximation-algorithms Archives

$G = (V, E, w)$

G=(V,E,w)

$w : E \to R$

w:E→R

arg max S \subset V \sum (u, v) \in E : u \in S, v \notin S w (u, v)

$w (e) \geq 0$

w(e)≥0

$e \in E$

e∈E

꼭짓점 의 무작위 하위 집합을 선택합니다 . $S$
정점에서 순서를 정하고, 정점 를 또는 에 탐욕스럽게 배치 하여 가장자리를 지금까지 최대화합니다. $v$ $S$ $\bar{S}$
로컬 개선 : $S$ 에 로 이동 $\bar{S}$ 하여 컷을 늘리거나 그 반대로 할 수있는 정점이있는 경우 이동합니다.

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

12∑e∈Ew(e)

이는 의 상한입니다. 가 음이 아닌 $1 / 2$

1/2

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

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

내 질문은 :

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

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

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

∑e∈Ew(e)>0

답변

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

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

$- a$

−a

$u$

$v$

$b - a$

b−a

$(b - a) / 2$

(b−a)/2

$(b - a) / 2$

(b−a)/2

$a$

$b$

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

≠

$16 / 17$

16/17

편집하다:

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

$v$

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

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

$G^{*}$

G∗

$G^{*}$

G∗

$G$

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

$v$

$- d$

−d

$(u, x)$

(u,x)

$(v, x)$

(v,x)

$x \neq u, v$

x≠u,v

$a$

$(u, v)$

(u,v)

$O P T$

OPT

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

$G$

$u$

$v$

$c - 2 d m$

c−2dm

$m$

$(u, v)$

(u,v)

$c$

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

c+a−(n−2)d

$d$

$u$

$v$

$G^{*}$

G∗

$u$

$v$

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

(a−(n−2)d)

$u$

$v$

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

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

$a$

$f \approx - 0.98 O P T$

f≈−0.98OPT

$c$

$G$

$u$

$v$

$c - 0.98 O P T$

c−0.98OPT

$G^{*}$

G∗

$0.02 O P T$

0.02OPT

$G^{*}$

G∗

$0.01 O P T$

0.01OPT

$G$

$0.99 O P T$

0.99OPT

$G^{*}$

G∗

$u$

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

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

$u$

$v$

$d$

$a$

$f \approx - .99 O P T$

f≈−.99OPT

$O P T$

OPT

$O P T$

OPT

$T$

$G$

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

12T≤OPT≤T

$f$

$- .49 T$

−.49T

$- .99 T$

−.99T

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

0.005T

$f \approx - 0.98 O P T$

f≈−0.98OPT

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

$f$

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

−.99T≤f≤−.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$

xTMx

$n \times n$

n×n

$M$

$x$

${\pm 1}^{n}$

{±1}n

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

M=12n(∑we)I−12A

$I$

$A$

$O (\log n)$

O(log⁡n)

$M$

$\sum w_{e} \geq 0$

∑we≥0

답변

Exit mobile version

How IT

언제든지 물어보세요.

태그 보관물: approximation-algorithms

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

답변

답변

답변

답변