랜덤화 반올림

이 글은 독자들에게 혼란스럽거나 불명확할 수 있다. 기사에 대해 명확하게 설명할 수 있도록 도와주십시오. 토크 페이지에서 이에 대한 논의가 있을 수 있다.(2010년 5월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

컴퓨터 과학과 운영 연구 내에서 많은 조합 최적화 문제는 정확히 (최적성에) 해결하기 위해 계산적으로 난해하게 된다.그러한 많은 문제들은 빠른(폴리놈 시간) 근사 알고리즘, 즉 입력이 주어지면 거의 최적의 솔루션을 반환할 수 있다고 보장되는 알고리즘을 인정한다.

무작위 반올림(Ragavan & Tompson 1987년)은 그러한 근사 알고리즘을 설계하고 분석하기 위해 널리 사용되는 접근법이다.^[1][2]기본적인 아이디어는 확률론적 방법을 사용하여 문제를 완화시키는 최적의 해결책을 원래 문제에 대한 대략 최적의 해결책으로 전환하는 것이다.

개요

기본 접근방식은 다음과 같은 세 가지 단계를 가진다.

1. 해결할 문제를 정수 선형 프로그램(ILP)으로 공식화한다.
2. ILP의 선형 프로그래밍 완화(Linear Programming Relation, LP)에$$ 대한 최적의 $분수{\displaystyle }$ 솔루션 x ${\displaystyle$ x$}$을 계산하십시오.
3. LP의 분수$$ 솔루션 $x{\displaystyle }$ ${\displaystyle$ x$}$을(를) ILP의 정수$$ 솔루션 x${\displaystyle {}^{}}x{\displaystyle {}^{}}$ ${\$ x$'}$에 반올림하십시오.

(접근법은 선형 프로그램에 가장 일반적으로 적용되지만, 다른 종류의 이완이 사용되기도 한다.예를 들어 Goemans 및 Williamson의 세미데마인 프로그래밍 기반 Max-Cut 근사 알고리즘을 참조하십시오.)

첫 번째 단계에서 과제는 적절한 정수 선형 프로그램을 선택하는 것이다.특히 선형 프로그램과 정수 선형 프로그램을 사용한 모델링, 선형 프로그래밍에 대한 친숙성이 요구된다.많은 문제의 경우, 아래의 Set Cover 예와 같이 잘 작동하는 자연 정수 선형 프로그램이 있다.(정수 선형 프로그램은 작은 통합성 차이를 가져야 한다. 실제로 무작위 반올림은 통합성 격차의 한계를 증명하기 위해 종종 사용된다.)

두 번째 단계에서 최적 분수 솔루션은 일반적으로 표준 선형 프로그래밍 알고리즘을 사용하여 다항식 시간으로 계산할 수 있다.

세 번째 단계에서는 분수용액을 정수용액(따라서 원래 문제에 대한 해결책)으로 변환해야 한다.이것을 분수용액 반올림이라고 한다.결과 정수 용액은 분수 용액의 비용보다 더 큰 비용이 들지 않아야 한다.이렇게 하면 정수용액의 원가가 최적 정수용액의 원가에 비해 그리 크지 않다는 것을 보장할 것이다.

세 번째 단계(회전)를 할 때 사용하는 주요 기법은 무작위화를 사용한 다음 반올림으로 인한 비용 증가를 구속하기 위해 확률론적 인수를 사용하는 것이다(결합에서 확률론적 방법에 따름).여기서, 확률론적 인수는 원하는 특성을 가진 이산형 구조의 존재를 나타내기 위해 사용된다.이런 맥락에서, 사람들은 다음과 같은 것을 나타내기 위해 그러한 주장을 사용한다.

LP의 소수$$ $용액{\displaystyle }$ x ${\displaystyle x}$을(를) 고려할 때, 임의 반올림 공정은 원하는 기준에 따라$$ $x{\displaystyle }$ ${\displaystyle$ x$}$에 근접한 정수 용액 $′{\$ $x$$'}$을(를) 생성한다.

마지막으로, 세 번째 단계를 계산적으로 효율적으로 만들기 위해, $x{\displaystyle {}^{}}$probability {\$displaystyle x'}$이(가) 높은 $확률$로 x ${\displaystyle x}$에 근사치$$ x {\displaystyle x}에 가깝다는 것을 보여주거나, 일반적으로 조건부 확률의 방법을 사용하여 라운딩 단계를 약화시킨다.후자의 방법은 무작위 반올림 공정을 효율적인 결정론적 공정으로 전환하여 좋은 결과를 얻을 수 있다.

확률론적 방법의 다른 적용과 비교

무작위 반올림 단계는 확률론적 방법의 대부분의 적용과 두 가지 측면에서 다르다.

1. 라운딩 단계의 계산적 복잡성이 중요하다.빠른(예: 다항식 시간) 알고리즘으로 구현할 수 있어야 한다.
2. 무작위 실험의 기초가 되는 확률 분포는 문제 인스턴스(instance) 완화의 $솔루션$ x ${\displaystyle x}$ 함수다.이 사실은 근사 알고리즘의 성능 보증을 입증하는 데 매우 중요하다. 즉, 어떤 문제라도 알고리즘이 해당 특정 인스턴스에 대한 최적 솔루션에 근접한 솔루션을 반환한다는 것이다.대조적으로 조합학에서 확률론적 방법의 적용은 전형적으로 특징이 입력의 다른 매개변수에 의존하는 구조의 존재를 보여준다.예를 들어, "$n{\displaystyle }$ ${\displaystyle n}$ 정점이$$ 평균 도 $d{\displaystyle }$ ${\displaystyle d}$인 그래프는 $최소{\displaystyle }$ n${\displaystyle }$/${\displaystyle }$(${\displaystyle \mathrm{d}}$+ 1${\displaystyle }$) ${\displaystyle$ n$/(d+1)}$의 독립된 크기 집합을 가져야$$ 한다."(투란의 정리를 확률적으로 증명하려면 이를 참조).이 바인딩이 엄격한 그래프가 있는 반면, $n{\displaystyle }$/${\displaystyle }$( d${\displaystyle }$+ ${\displaystyle 1}$) ${\displaystyle n/(d+1)$보다 훨씬 큰 독립 집합을 갖는 그래프도 있다$.$따라서, 그래프에서 투란의 정리에 의해 존재하는 것으로 보이는 독립 집합의 크기는 일반적으로 그 그래프에 대한 최대 독립 집합보다 훨씬 작을 수 있다.

커버 예제 설정

다음 예제는 무작위 반올림을 사용하여 Set Cover 문제에 대한 근사 알고리즘을 설계하는 방법을 보여준다.

${\displaystyle 우주\mathcal{}}$ $U{\displaystyle \mathcal{}}${\displaystyle$displaystyle \langle$ c$,{\mathcal$${S}\$$angle$ $\}$에 설정된 커버를$$ $고정$하십시오.

1단계의 경우 IP를 이 인스턴스에 대한 세트 커버에 대한 표준 정수 선형 프로그램이 되게 한다.

2단계에서는 LP를 IP의 선형 프로그래밍 완화가 되도록 하고, 표준 선형 프로그래밍 알고리즘을 사용하여 최적의 $솔루션{\displaystyle {}^{}}$ x$∗{\$ x$^{*}$을 LP로 계산한다.(입력 크기에서 다항식 시간이 소요됨).

(The feasible solutions to LP are the vectors ${\displaystyle x}$ that assign each set ${\displaystyle s\in {\mathcal {S}}}$ a non-negative weight ${\displaystyle x_{s}}$, such that, for each element ${\displaystyle e\in {\mathcal {U}}}$, ${\displaystyle x'}$ covers ${\display$$스타일 e}$ $$- $e{\displaystyle }$ ${\displaystyle e}$을(를) 포함하는 세트에 할당된 총 중량은 1$$ 이상, 즉,

${\displaystyle \sum _{s\ni e}x_{s}\geq 1.}$

최적의 솔루션 $∗{\$은(는) 비용을 부담하는 실현 가능한 솔루션이다$$.

${\displaystyle \sum _{s\in {\mathcal {S}c(S)x_{s}^{*}}}}}$

가능한 한 작다.)

---

Note that any set cover ${\displaystyle {\mathcal {C}}}$ for ${\displaystyle {\mathcal {S}}}$ gives a feasible solution ${\displaystyle x}$ (where ${\displaystyle x_{s}=1}$ for ${\displaystyle s\in {\mathcal {C}}}$, ${\displaystyle x_{s}=0}$ otherwise).이 $C{\displaystyle \mathcal{}}$ ${\$의 비용은 $x{\displaystyle }$ ${\displaystyle x}$의 비용,$$즉,

${\displaystyle \sum _{s\in {\mathcal {C}c=\sum_{s}s\in {\mathcal {S}c}x_{s}.}$

즉, 선형 프로그램 LP는 주어진 세트커버 문제를 완화하는 것이다.

$∗{\$는 LP에 대한 실현 가능한 솔루션 중 최소 비용이 있으므로$$, $∗{\$의 비용은 최적 세트 커버 비용보다 낮은 가격이다.

3단계: 무작위 반올림 단계

다음은 세 번째 단계인 반올림 단계에 대한 설명으로, 최소 비용 분수 세트 커버 $∗{\$ x$^{*}$를 실현 가능한 정수 솔루션 $′{\$참 세트 커버에 대응함)로$$ 변환해야 한다.

$라운딩{\displaystyle {}^{}}$ 단계에서 x${\displaystyle {}^{}}$′ ${\$ $x^{*}$의 작은 요소 내에서 x ${\displaystyle {\ast }^{}}$ ${\$ x^{*}의 원가가 x${\displaystyle {}^{}}$∗ ${\$ x$^{*}$의 원가가 최적$$ 세트 커버 원가에 대한 하한이기 때문에, $x{\displaystyle {}^{}}$′ ${\$ x$'}$의 원가가 생성되어야 한다$.$최적 비용의 작은 요소 안에 들어갈 것이다.

가장 자연스러운 라운딩 방식을 출발점으로 고려하십시오.

For each set ${\displaystyle s\in {\mathcal {S}}}$ in turn, take ${\displaystyle x'_{s}=1}$ with probability ${\displaystyle \min(1,x_{s}^{*})}$, otherwise take ${\displaystyle x'_{s}=0}$.

이 반올림 방식으로 선택한 세트의 예상 비용은 최대 ${\displaystyle \underset{}{}}{\displaystyle \underset{}{}}$s (${\displaystyle }$s )${\displaystyle x}$ ${\$ \sum $_{s}c(s)x_{s}^{*}}}}}$이다$.$좋아요.불행히도 그 보도는 좋지 않다.$변수{\displaystyle }$ $x{\displaystyle {}_{}^{}}$ ${\displaystyle s_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$이(가) 작을 때 요소 e ${\displaystyle$ e$}$이(가) 포함되지 않을$$ 확률은 대략

${\displaystyle \prod _{s\ni e}-x_{s}^{*}\prod _{s\ni e}\ex(-x_{s}^)=\ex {s}^{*{\Big )\comprety \ex(-1).}$

따라서 원소의 일정 부분만이 기대치에 의해 가려질 것이다.

$x{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$이(가) 높은 확률로 모든 요소를 덮도록$$ 하려면 먼저 표준 반올림 계획을 > 1 ${\displaystyle \lambda >1}$에 따라 반올림 확률을 스케일업한다. 다음은표준 반올림 방법:

$매개{\displaystyle }$ 변수 ${\displaystyle ▼}$ ${\displaystyle 1}$ ${\displaystyle \lambda \geq 1$을(를) 수정하십시오. 각 $세트{\displaystyle s\mathcal{}}$ S$${\$displaystyle$ s$\in${\$mathcal {S}$

take $x{\displaystyle {}_{}^{}}$ ${\displaystyle s_{}^{}}$=${\displaystyle }$1 ${\displaystyle \mathrm{확률}}$ ${\displaystyle min(}$ x ${\displaystyle s_{}^{}}$ 1$$)을$$ 가진 1 ${\$$displaystyle x$$'_{s}=1$$\},$ 그렇지 않으면 $x{\displaystyle {}_{}^{}}$ ${\displaystyle s_{}^{}}$ ${\displaystyle {}_{}^{}}$= ${\displaystyle 0}$ ${\day x_{s}^{*},1$}을 선택하십시오$.$

확률을 $\lambda {\displaystyle }$ ${\displaystyle \lambda }$까지 확대하면 예상 $비용$이 {$${\$displaystyle \lambda$만큼$$ 증가하지만 모든 요소에 대한 적용 범위가 될 가능성이 높다.모든 요소가 0이 아닌 확률로 확실히 덮일 수 있도록 가능한 한 작게$$ $\lambda {\displaystyle }$ ${\displaystyle \lambda }$을(를) 선택하는 것이다.여기에 상세한 분석이 있다.

---

보조정리(반올림 방식에 대한 근사치 보장)

Fix ${\displaystyle \lambda =\ln(2 {\mathcal {U}} )}$. With positive probability, the rounding scheme returns a set cover ${\displaystyle x'}$ of cost at most ${\displaystyle 2\ln(2 {\mathcal {U}} )c\cdot x^{*}}$ (and thus of cost ${\displaystyle O(\log \mathcal{U}}$${\displaystyle )}$ ${\displaystyle O(\log {\mathcal {U}}}$최적$$ 세트 커버 비용).

(참고: O${\displaystyle (}$log ${\displaystyle log\mathcal{}}$U${\displaystyle }$) ${\displaystyle$ O$(\log$ {\$mathcal {U})}을($를) ln ${\displaystyle n(U\mathcal{}}$)${\displaystyle }$+ $($ $displaystyle \ln({\mathcal {U})+O(\log \log \mathcal {U})$로 줄일 수 있다$$.$$

증명

랜덤 반올림 방식의 출력$$ $x{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$은(는) 다음 "나쁜" 이벤트가 발생하지 않는 한 원하는 속성을 갖는다.

1. $x$ ${\displaystyle \prime }$의 c${\displaystyle {}^{}}${$$x$display$ {\$displaystyle$ $c\cdot$ x$'}$이(가) $2{\displaystyle \mathrm{}}$ ${\displaystyle \lambda }$ ${\displaystyle {}^{}}$ ${\displaystyle \cdot }$ x${\displaystyle {}^{}}$⋅{\$displaystyle 2\lambda c\cdot$ x$^{*}$을 초과하거나$,$
2. 일부 요소 $e{\displaystyle }$ ${\displaystyle e}$에 대해$,$ $\$ {\$displaystyle x'}$이(가) $e{\displaystyle }$ ${\displaystyle e}$을(를) 포함하지 못함$$$.$

The expectation of each ${\displaystyle x'_{s}}$ is at most ${\displaystyle \lambda x_{s}^{*}}$. By linearity of expectation, the expectation of ${\displaystyle c\cdot x'}$ is at most ${\displaystyle \sum _{s}c(s)\lambda x_{s}^{*}=\lambda c\cdot$$x$ 따라서 마르코프의 불평등에 의해 위의 첫 번째 나쁜 사건의 확률은 최대${\displaystyle }$1/$[\displaystyle$1$/2]$이다$.$

나머지 불량 이벤트(각 요소 $e{\displaystyle }$ ${\displaystyle e}$에 대해 하나)$$의 경우, 주어진 요소 $e{\displaystyle }$ ${\displaystyle e}$에 대해 $\sum {\displaystyle \underset{}{}}$ s${\displaystyle \underset{}{}}$∋ ${\displaystyle \underset{}{e}}$ ${\displaystyle x_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle 1}$ ${\displaystyle \sum \{s\ni e}x_{s}^{*}}}\$$displaystylease$ e$}$에 $포함$되지 않을$$ 확률은 없다$.$

${\displaystyle {\begin{aligned}\prod _{s\ni e}{\big (}1-\min(\lambda x_{s}^{*},1){\big )}&<\prod _{s\ni e}\exp({-}\lambda x_{s}^{*})=\exp {\Big (}{-}\lambda \sum _{s\ni e}x_{s}^{*}{\Big )}\\&\leq \exp({-}\lambda )=1/(2 {\mathcal {U}} ).\end{정렬}}}$

(${\displaystyle \mathrm{이것}}$은 불평등 $1{\displaystyle \mathrm{}}$+ z ${\displaystyle \le }$ e ${\displaystyle z^{}}$ ${\$ e$^{z$를 사용하며, $z{\displaystyle }$ ${\displaystyle \ne }$ ${\displaystyle 0}$ ${\displaystyle z\neq 0}$에 대해 엄격하다.)$$

따라서 각 ${\displaystyle U\mathcal{}}$ $displaystyle {\mathcal{U}}$ 요소에$$ 대해 요소가 포함되지 않을 확률은 $1{\displaystyle \mathrm{}}$/ (${\displaystyle }$2 ${\displaystyle U\mathcal{}}$ $){\displaystyle$1/($2{\mathcal {U})$보다 작다$.$

By the naive union bound, the probability that one of the ${\displaystyle 1+ {\mathcal {U}} }$ bad events happens is less than ${\displaystyle 1/2+ {\mathcal {U}} /(2{\mathcal {U}})=1}$. Thus, with positive probability there are no bad events and ${\displaystyle x'$$}}$은(는) 최대 ${\displaystyle \mathrm{2\lambda }}$ ${\displaystyle c}$ ${\displaystyle \cdot }$ ${\displaystyle {}^{}}$ ${\displaystyle {\ast }^{}}$ ${\$ x$^\{*\}\}\}\}$QED의 비용 세트 커버.

조건부 확률 방법을 이용한 비완도화

위의 보조정리기는 $비용{\displaystyle }$ O${\displaystyle (}$로그 cover ( ${\displaystyle U\mathcal{}}$)${\displaystyle c}$ ⋅ ${\displaystyle {}^{}}$ ${\displaystyle \cdot }$ $displaystyle$ O$(\log({\mathcal{U}})c\cdot$ x$^{*}}}$의 세트 커버의 존재를 보여준다.$$이런 맥락에서 우리의 목표는 단지 존재 증명만이 아니라 효율적인 근사 알고리즘이기 때문에 우리는 끝나지 않았다.

한 가지 접근방식은 ${\displaystyle \lambda$}}을$$(를) 약간 증가시킨 다음, 성공 확률이 적어도 1/4이라는 것을 보여주는 것이다.이 수정으로 무작위 반올림 단계를 몇 번 반복하면 높은 확률로 성공적인 결과를 보장하기에 충분하다.

그 접근법은 근사비를 약화시킨다.다음으로 위의 존재 증명 근사 비율과 일치하도록 보장된 결정론적 알고리즘을 산출하는 다른 접근법을 설명한다.이 접근법을 조건부 확률의 방법이라고 한다.

The deterministic algorithm emulates the randomized rounding scheme: it considers each set ${\displaystyle s\in {\mathcal {S}}}$ in turn, and chooses ${\displaystyle x'_{s}\in \{0,1\}}$. But instead of making each choice randomly based on ${\displaystyle x^{*}}$, it makes the choice determin지금까지 선택했던 것들로 볼 때, 이성적으로, 실패의 조건부 확률을 1 이하로 유지한다.

조건부 고장 확률 제한

각 변수 $x{\displaystyle {}_{}^{}}$ ${\displaystyle s_{}^{}}$1${\$를 차례대로$$ 설정하여 고장 조건부 확률을 1 이하로 유지할 수 있기를 원한다.그러기 위해서는 조건부 실패 확률에 대한 좋은 구속력이 필요하다.본래의 존재 증명서를 다듬어 바운드가 올 것이다.그 증거는 무작위 변수의 예상에 의해 암묵적으로 실패의 확률을 제한한다.

${\displaystyle F}$= ${\displaystyle \frac{{}^{}}{}}$ ${\displaystyle \frac{\cdot }{}}$ x$$ ${\displaystyle \frac{2}{\mathrm{}}}$ ${\displaystyle \frac{{}^{}}{}}$c ${\displaystyle \frac{{\ast }^{}}{}}$ x${\displaystyle \frac{{}^{}}{}}$+ + ${\displaystyle U^{}}$( m${\displaystyle {}^{}}$) $displaystyle F={\frac {$c$\cdot x'}{2\lambda$ c$\cdot$ x$^{*}}}+{\mathcal {U$

어디에

${\displaystyle {\mathcal{U}^{{{}}={\Big \{}e:\prod_{s\ni e}(1-x'_{s})=1{\Big \}}}}}}$

마지막에 남은 원소들의 집합이다.

랜덤 변수 $F{\displaystyle }$ ${\displaystyle$ F$}$는 약간 신비하게 보일 수 있지만$$, 확률론적 증거를 체계적으로 반영한다.$F{\displaystyle }$ ${\displaystyle F}$에서 첫 번째 용어는 첫 번째 불량 사건의 확률을 구속하기 위해 마르코프의 불평등을 적용한 데서 유래한다$$(원가가 너무 높다).$x{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ x$'}$의 비용이 너무$$ 높을 경우$$ 최소 1 ~ $F{\displaystyle }$ ${\displaystyle$ $F$$}$에 기여한다.제2항은 제2종(발견되지 않은 원소)의 나쁜 사건의 수를 계상한다.$x{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ x$'}$이(가) 어떤 요소도 노출되지 않은 경우$$ 최소$$ $1{\displaystyle }$ ~ F ${\displaystyle$ $F$$}$에 기여한다.따라서 $F{\displaystyle }$ ${\displaystyle F}$이(가) 1 미만인 모든 결과에서 $x{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$은(는) 모든 요소를 포괄해야 하며$$ 보조정리로부터 원하는 경계를 충족하는 비용을 가져야 한다.간단히 말해서 라운딩 단계가 실패하면 $F{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle 1}$ ${\displaystyle F\geq 1$ 이것은 (마코프의 불평등에 의해) $E{\displaystyle }$[ ${\displaystyle F}$ ${\displaystyle ]}$ ${\displaystyle E[F]}$이 실패 확률의 상한임을 암시한다.상기 주장은 보조정리법의 증거에 이미 내포되어 있다는 점에 유의하십시오. 이 또한 계산으로 E < ${\displaystyle E[F]<1$}을$($를) 알 수 있다

조건부 확률의 방법을 적용하려면 반올림 단계가 진행됨에 따라 실패의 조건부 확률을 바인딩하도록 인수를 확장할 필요가 있다.일반적으로 이것은 기술적으로 지루할 수 있지만 체계적인 방법으로 이루어질 수 있다.

그렇다면 라운딩 단계가 세트를 통해 반복되면서 조건부 고장 확률은 어떨까?라운딩 ${\displaystyle \mathrm{단계}}$가 실패하는 모든 결과에서$$ $F{\displaystyle }$ ${\displaystyle \ge }$ 1 ${\displaystyle F\geq 1}$이(가) 마르코프의 불평등에 의해 실패의 조건부 확률은 기껏해야 $F{\displaystyle }$ {\$displaystyle F}$의 조건부 기대치가 된다$.$

다음으로 $우리$는 F$${\$displaystyle F$}의 조건부 기대치를 계산하는데, 이는 원본 증명에서$$ $F{\displaystyle }$ ${\displaystyle F}$의 조건부 기대치를 계산한 값이다$.$일부 반복 $t{\displaystyle }$ ${\displaystyle t}$의 끝에서 반올림 프로세스의 상태를 고려하십시오$.$ ${\displaystyle {\mathrm{Let}}^{}}$ S${\displaystyle {}^{}}$( t${\displaystyle {}^{}}$) ${\$는 지금까지 고려된 세트($S{\displaystyle \mathcal{}}$ ${\$의 첫 $번째{\displaystyle }$ t ${\displaystystystyle t}$ 세트$$)를 나타낸다$$.$$$let{\displaystyle {}^{}}$ x${\displaystyle {}^{}}$( $){\$ x$^{(t)}}$는 (부분적으로 할당된) $벡터{\displaystyle {}^{}}$ x${\displaystyle {}^{}}$′ ${\$${\displaystyle {\mathrm{그래서}}_{}^{}}$ x (${\displaystyle {}_{}^{}}$t )${\$ s $s$ ${\displaystyle {}^{}}$(${\displaystyle {}^{}}$t$) {\displaystystystylease$ s $(s$)})가 결정되는 경우에만$$ 결정된다.$$각 세트${\displaystyle s^{}}$ ${\displaystyle {}^{}}$( t${\displaystyle {}^{}}$) ${\$$displaystyle s$$\not \in S^{(t$에 ${\displaystyle {대해}_{}}$ p${\displaystyle {}_{}}$= ${\displaystyle min}$( ${\displaystyle {}_{}^{}}$ ${\displaystyle x_{}^{}}$ s ${\displaystyle {}_{}^{}}$,${\displaystyle 1}$ )$${\$displaystyle p_{s}=\min$$(\$$lambda$ $x_$${s$$}^{*,1)}}}$이 1로 설정될 확률을$$ 나타내도록$$ 한다${\displaystyle {}_{}^{}}$$U{\displaystyle {\mathcal{}}^{}}$( $){\$에 아직 덮이지 않은 원소가 포함되도록$$ 한다.그러면 $지금$까지의 선택, 즉 $x{\displaystyle {}^{}}$( ${\displaystyle t^{}}$) ${\$의 조건부 $기대$는 다음과 같다$.$

${\displaystyle E[F x^{(t)}]~=~{\frac {\sum _{s\in S^{(t)}}c(s)x'_{s}+\sum _{s\not \in S^{(t)}}c(s)p_{s}}{2\lambda c\cdot x^{*}}}~+~\sum _{e\in {\mathcal {U}}^{(t)}}\prod _{s\not \in S^{(t)},s\ni e}(1-p_{s}).}$

$E{\displaystyle }$[ ${\displaystyle F}$ ${\displaystyle x{}^{}}$( ${\displaystyle t^{}}$) ${\displaystyle {}^{}}$ ${\displaystyle E[F$ x$^{(t)}}]$은(는) 반복 $t{\displaystyle }$ ${\displaystyle$ t$} 후$에만 결정된다는$$ 점에 유의하십시오$.$

조건부 고장 확률을 1 미만으로 유지

실패의 조건부 확률을 1 미만으로 유지하기 $위해서$는 F ${\displaystyle F$}의 조건부 기대치를 1 미만으로$$ 유지하는 것으로 충분하다.이를 위해서는 $F{\displaystyle }$ ${\displaystyle F}$의 조건부 기대치가 높아지는 것을$$ 막는 것으로 충분하다.이것이 알고리즘이 할 일이다.각 반복마다$$ $x{\displaystyle {}_{}^{}}$ $′{\$를 설정하여 다음이 되도록 한다.

${\displaystyle E[F x^{(m)}]\leq E[F x^{(m-1)}]\leq \cdots \leq E[F x^{(1)]\leq E[F x^{(0)}]<1}$

(여기서 $m{\displaystyle }$= ${\displaystyle S\mathcal{}}$ $displaystyle m= {\mathcal{S}}$ $$)

In the ${\displaystyle t}$th iteration, how can the algorithm set ${\displaystyle x'_{s'}}$ to ensure that ${\displaystyle E[F x^{(t)}]\leq E[F S^{(t-1)}]}$? It turns out that it can simply set ${\displaystyle x'_{s'}}$ so as to minimize the$결과값{\displaystyle }$ E${\displaystyle }$[ ${\displaystyle F}$ ${\displaystyle x^{}}$( t${\displaystyle {}^{}}$) ${\displaystyle {}^{}}$ ${\displaystyle E[F x^{(t)}]}$.

이유를 보려면 반복 $t{\displaystyle }$ ${\displaystyle t}$이(가) 시작되는$$ 시점을 중심으로 하십시오.At that time, ${\displaystyle E[F x^{(t-1)}]}$ is determined, but ${\displaystyle E[F x^{(t)}]}$ is not yet determined --- it can take two possible values depending on how ${\displaystyle x'_{s'}}$ is set in iteration ${\displaystyle t}$. Let ${\displaystyle E^{(t-}}$${\displaystyle E^{(t-1)}}$ denote the value of ${\displaystyle E[F x'^{(t-1)}]}$. Let ${\displaystyle E_{0}^{(t)}}$ and ${\displaystyle E_{1}^{(t)}}$, denote the two possible values of ${\displaystyle E[F x^{(t)}]}$, depending o$n{\displaystyle {}_{}^{}}$ x ${\displaystyle {s{}^{}}_{}^{}}$ ${\displaystyle {\prime }_{}^{}}$ $\{\$s'}}}}을(를) 각각 0 또는 1로 설정할지$$ 여부.조건부 기대의 정의에 따르면

${\displaystyle E^{(t-1)}~=~\Pr[x'_{s'}=0]E_{0}^{0}^{(t)+\Pr[x'_{s'}=1]E_{1}^{(t)}}$

두 수량의 가중 평균은 항상 최소한 그 두 수량의 최소치이기 때문에, 그것은 다음과 같다.

${\displaystyle E^{(t-1)}~\geq ~\min(E_{0}^{(t)},E_{1}^{(t)}).}$

Thus, setting ${\displaystyle x'_{s'}}$ so as to minimize the resulting value of ${\displaystyle E[F x^{(t)}]}$ will guarantee that ${\displaystyle E[F x^{(t)}]\leq E[F x^{(t-1)}]}$. This is what the algorithm will do.

구체적으로, 이것은 무엇을 의미하는가?Considered as a function of ${\displaystyle x'_{s'}}$ (with all other quantities fixed) ${\displaystyle E[F x^{(t)}]}$ is a linear function of ${\displaystyle x'_{s'}}$, and the coefficient of ${\displaystyle x'_{s'}}$ in that function is

${\displaystyle{\frac{c_{s'}{2\lambda c\cdot x^{*}~~\sum_{e\in s'\cap {\mathcal{U}}}}{t-1}\pd_{s\not\in S^{(t)},s}}$

따라서 알고리즘은 이 식이 양이면 $x{\displaystyle {}_{}^{}}$ ${\displaystyle {s{}^{}}_{}^{}}$ ${\displaystyle {{\prime }^{}}_{}^{}}$ ${\displaystyle {\prime }_{}^{}}$ $\$ {\$displaystyle x'_{$s'}}}을(를) 0으로$$, 그렇지 않으면 1로 설정해야 한다.이것은 다음과 같은 알고리즘을 제공한다.

세트커버의 랜덤화 라운드 알고리즘

입력: 시스템 $S{\displaystyle \mathcal{}}$ ${\$ Universe $U{\displaystyle \mathcal{}}$ ${\$ 비용 $벡터{\displaystyle }$ c ${\displaystyc} 설정$

출력: set cover $x{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$set cover에 대한 표준 정수 선형 프로그램에 대한 솔루션)

---

1. Min-cost fractal set cover $∗{\$LP 이완에 대한 최적의 솔루션)를 계산한다.$$
2. Let ${\displaystyle \lambda \leftarrow \ln(2 {\mathcal {U}} )}$. Let ${\displaystyle p_{s}\leftarrow \min(\lambda x_{s}^{*},1)}$ for each ${\displaystyle s\in {\mathcal {S}}}$.
3. $각{\displaystyle {}^{}}$ s ${\displaystyle \prime }$ ${\displaystyle S\mathcal{}}$ ${\$ {$S}$에 대해 다음을 수행하십시오$$.
   1. $S{\displaystyle \mathcal{}}$ ${\displaystyle \leftarrow }$ ${\displaystyle S}$-${\displaystyle }${ ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\displaystyle \}}$ ${\displaystyle {\mathcal {S}\왼쪽$ 화살표 ${\mathcal {S}-\{s$ (${\displaystyle \mathcal{}}$ ${\$에 미결정 집합이 포함됨$$)
   2. If ${\displaystyle {\frac {c_{s'}}{2\lambda c\cdot x^{*}}}>\sum _{e\in s'\cap {\mathcal {U}}}\prod _{s\in {\mathcal {S}},s\ni e}(1-p_{s})}$

      $그런{\displaystyle {}_{}^{}}$ 다음 x ${\displaystyle s_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle \leftarrow }$ $(\displaystyle x'_{s}\왼쪽 화살표$ 0$\},$

      그 밖에 $x{\displaystyle {}_{}^{}}$ ${\displaystyle s_{}^{}}$ ${\displaystyle {}_{}^{}}$ $←$ ${\displaystyle 1}${\$displaystyle x'_{$s}\$왼쪽$ 화살표 $1}$ 및$$ $U{\displaystyle \mathcal{}}$ ${\displaystyle \leftarrow }$ ${\displaystyle U}$- ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ {U}-s$}을(를)$ 설정하십시오$.$

      (${\displaystyle \mathcal{}}$ ${\$에 미봉합 요소가 포함되어$$ 있음)

4. $x{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ x$'}$을(를) 반환하십시오$.$

---

보조정리(알고리즘에 대한 근사치 보장)

위의 알고리즘은 (수축) 세트 커버의 최소 비용의 $최대{\displaystyle \mathrm{}}$ 2 ${\displaystyle \ln }$ ${\displaystyle }$(${\displaystyle 2}$ $){\displaystyle 2\ln ($2${\mathcal {U})$에 대해 세트$$ 커버 $′{\$를 반환한다.

증빙의

---

알고리즘은$$$F{\displaystyle }$ ${\displaystyle F}$, $E{\displaystyle }$[ F ${\displaystyle x{}^{}}$( ${\displaystyle t^{}}$) ${\displaystyle {}^{}}$ ${\displaystyle E[F\, \,x^{(t)}}}$의 조건부 기대치가 반복마다 증가하지 않도록 보장한다.이 조건부 기대치는 초기에는 1보다 작기 때문에(앞에서 표시한 바와 같이), 알고리즘은 조건부 기대치가 1보다 낮게 유지되도록 보장한다.이러한 방식으로 알고리즘은 F ${\displaystyle F$의 조건부 기대치인 고장 확률을 $최대{\displaystyle }$ 1 미만으로 유지하도록 보장한다.따라서 결국 모든 선택이 결정되면 알고리즘은 성공적인 결과에 도달한다.즉, 위의 알고리즘은 (수축) 세트 커버의 최소 비용의 $최대{\displaystyle \mathrm{}}$ 2 ${\displaystyle \ln }$ ${\displaystyle }$ ${\displaystyle (2}$ $){\displaystyle 2\ln ($2${\mathcal {U}$)으로$$ 세트$$ 커버 $′{\$을 반환한다.

언급

위의 예에서 알고리즘은 $임의{\displaystyle }$ 변수 F ${\displaystyle F}$의 조건부 기대치에 의해 유도되었다$.$ 어떤 경우에는 정확한 조건부 기대 대신에 어떤 조건부 기대치에 대한 상한(또는 때로는 하한)이 대신 사용된다.이를 비관적 추정자라고 한다.

참고 항목

• 조건부 확률법

참조

• Raghavan, Prabhakar; Tompson, Clark D. (1987), "Randomized rounding: A technique for provably good algorithms and algorithmic proofs", Combinatorica, 7 (4): 365–374, doi:10.1007/BF02579324, S2CID 5749936.
• Raghavan, Prabhakar (1988), "Probabilistic construction of deterministic algorithms: approximating packing integer programs", Journal of Computer and System Sciences, 37 (2): 130–143, doi:10.1016/0022-0000(88)90003-7.

추가 읽기

• Althöfer, Ingo (1994), "On sparse approximations to randomized strategies and convex combinations", Linear Algebra and Its Applications, 199: 339–355, doi:10.1016/0024-3795(94)90357-3, MR 1274423
• Hofmeister, Thomas; Lefmann, Hanno (1996), "Computing sparse approximations deterministically", Linear Algebra and Its Applications, 240: 9–19, doi:10.1016/0024-3795(94)00175-8, MR 1387283
• Lipton, Richard J.; Young, Neal E. (1994), "Simple strategies for large zero-sum games with applications to complexity theory", STOC '94: Proceedings of the twenty-sixth annual ACM symposium on theory of computing, New York, NY: ACM, pp. 734–740, arXiv:cs.cc/0205035, doi:10.1145/195058.195447, ISBN 978-0-89791-663-9, S2CID 7524887