빈 덮개 문제

빈 덮개 문제에서, 크기가 다른 항목은 최소한 특정한 총 크기를 포함해야 하는 한정된 수의 빈이나 용기에 포장되어야 하며, 각각의 빈은 사용된 빈의 수를 최대화하는 방법으로, 각각의 빈은 최소한 특정한 총 크기를 포함해야 한다.

이 문제는 빈 포장 문제의 이중적 문제인데, 빈 덮개에서는 빈 크기가 아래로부터 경계되고 목표는 숫자를 최대화하는 것이다. 빈 패킹에서는 빈 크기가 위로부터 경계되고, 목표는 빈 크기를 최소화하는 것이다.^[1]

문제는 NP-hard이지만 다음과 같은 다양한 효율적인 근사 알고리즘이 있다.

최적 빈 카운트의 1/2, $O(n),O(n\log n),O(n{\log }^{2}n)$ /3 또는 3/4를 포함하는 알고리즘으로, 각각 $O(n),O(n\log n),O(n{\log }^{2}n)$ 시간 $O(n),O(n\log n),O(n{\log }^{2}n)$ $O(n),O(n\log n),O(n{\log }^{2}n)$ , $O(n),O(n\log n),O(n{\log }^{2}n)$ $O(n),O(n\log n),O(n{\log }^{2}n)$ $O(n),O(n\log n),O(n{\log }^{2}n)$ $O(n),O(n\log n),O(n{\log }^{2}n)$ ) ${\displaystyle$ $(n), O(n\log n),$ O(n(n) 및 O $(n{\log }^{2}n)}$ 에서 실행된다.^[1]^[2]
점근성 PTAS, 일부 이산형 분포에 대해 예상 동작이 점근성적으로 최적인 경계 최악의 경우 동작이 있는 알고리즘 및 모든 이산형 분포에 대해 점근성적으로 최적의 예상 동작을 갖는 학습 알고리즘.^[3]
점근성 FPTAS.^[4]

양방향 빈 채우기 알고리즘

Csirik, Frenk, Lebbe, Zhang은^[2]^{: 16–19} 2/3 근사치를 위해 다음과 같은 간단한 알고리즘을 제시한다.빈 크기가 1이고 항목이 n개라고 가정합시다.

가장 큰(1) 항목부터 가장 작은 항목(n)까지 정렬한다.
가장 큰 항목인 1, 2, ..., m으로 빈을 채우십시오. 여기서 m은 항목 1, ..., m의 합이 1보다 작은 가장 큰 정수입니다.
값이 1 이상으로 올라갈 때까지 가장 작은 항목(n, n-1, ...)을 이 상자에 추가하십시오.

임의의 경우, $\mathrm {OPT} (I)$ $\mathrm {OPT} (I)$ $\mathrm {OPT} (I)$ ( I $\mathrm {OPT} (I)$ ) ${\displaystyle \mathrm$ { $\mathrm {BDF} (I)$ $} (I)$ 최적 용액의 빈 수를 나타내고 $\mathrm {OPT} (I)$ , $\mathrm {BDF} (I)$ $\mathrm {BDF} (I)$ $\mathrm {BDF} (I)$ ( I $\mathrm {BDF} (I)$ ) ${\displaystyle \mathrm$ { $BDF} (I)$ 양방향 채우기 알고리즘의 전체 빈 수를 $\mathrm {BDF} (I)$ 나타낸다.Then $\mathrm {BDF} (I)\geq (2/3)\mathrm {OPT} (I)-(2/3)$ , or equivalently, $\mathrm {OPT} (I)\leq (3/2)\mathrm {BDF} (I)+1$ .

증빙의

그 증명에는 다음과 같은 용어가 사용된다.

$t:=\mathrm {BDF} (I)=$ $t:=\mathrm {BDF} (I)=$ $t:=\mathrm {BDF} (I)=$ $t:=\mathrm {BDF} (I)=$ $t:=\mathrm {BDF} (I)=$ ( $t:=\mathrm {BDF} (I)=$ ) $t:=\mathrm {BDF} (I)=$ = $t:=\mathrm {BDF}(I)=$ 알고리즘으로 채워진 빈의 수입니다 $t:=\mathrm {BDF} (I)=$ .
$B_{1},\ldots ,B_{t}:=$ $B_{1},\ldots ,B_{t}:=$ , $B_{1},\ldots ,B_{t}:=$ … , $B_{1},\ldots ,B_{t}:=$ $B_{1},\ldots ,B_{t}:=$ $B_{1},\ldots ,B_{t}:=$ $B_{1},\ldots ,B_{t}=$ 알고리즘에 의해 채워진 $B_{1},\ldots ,B_{t}:=$ t 빈.
초기 항목 - 각 t bin에 먼저 삽입되는 t 항목.
최종 항목 - 각 t bin에 마지막으로 삽입되는 t 항목.
중간 항목 - 초기 항목도 최종 항목도 아닌 모든 항목.
$w$ $w$ := $w$ 최대 1/2인 최종 항목의 수( $t-w$ t $t-w$ - $t-w$ $t-w$ 은 $t-w$ 1/2보다 큰 최종 항목의 수입니다.

각 빈 B $B_{1},\ldots ,B_{t}$ , $B_{1},\ldots ,B_{t}$ … $B_{1},\ldots ,B_{t}$ , $B_{1},\ldots ,B_{t}$ $B_{1},\ldots ,B_{t}$ ${\$ 의 합은 최소 1이지만 $B_{1},\ldots ,B_{t}$ , 최종 품목을 그 안에서 제거하면 나머지 합은 1보다 작다.처음 $w$ $w$ bins $w$ $B_{1},\ldots ,B_{w}$ 1, $B_{1},\ldots ,B_{w}$ … $B_{1},\ldots ,B_{w}$ , B $B_{1},\ldots ,B_{w}$ ${\$ 각각 초기 항목, 일부 중간 항목 및 최종 항목이 포함되어 $B_{1},\ldots ,B_{w}$ 있다.마지막 $t-w$ - $t-w$ $t-w$ $B_{w+1},\ldots ,B_{t}$ $B_{w+1},\ldots ,B_{t}$ $B_{w+1},\ldots ,B_{t}$ + 1 , $B_{w+1},\ldots ,B_{t}$ B $B_{w+1},\ldots ,B_{t}$ {\ $displaystyle B_{w+1},\ldots,B_{t}$ 는 모두 1/2보다 크고 합은 이미 1보다 크기 때문에 초기 항목과 최종 항목만 포함한다 $B_{w+1},\ldots ,B_{t}$ .

그 증거는 두 가지 경우를 고려한다.

쉬운 경우는 $w=t$ = $w=t$ ${\displaystyle w=t$ 즉 모든 최종 항목이 1/2보다 작다.그러면 채워진 $B_{i}$ ${\$ 의 합은 최대 $B_{i}$ 3/2이고, 나머지 항목의 합은 최대 $3t/2+1$ 이므로 모든 항목의 합은 최대 3 t $3t/2+1$ / $3t/2+1$ + $3t/2+1$ $[\displaystyle 3t/2+1}$ 이다 $3t/2+1$ On the other hand, in the optimal solution the sum of every bin is at least 1, so the sum of all items is at least $\mathrm {OPT} (I)$ . Therefore, $\mathrm {OPT} (I)\leq 3t/2+1$ as required.

하드 케이스는 $w<t$ < $w<t$ ${\displaystyle w<t$ 즉 일부 최종 항목이 1/2보다 크다.We now prove an upper bound on $\mathrm {OPT} (I)$ by presenting it as a sum $\mathrm {OPT} (I)= K_{0} + K_{1} + K_{2}$ where:

$K_{0}:=$ $K_{0}:=$ $K_{0}:=$ $K_{0}:$ 초기/최종 항목이 없는 최적의 $K_{0}:=$ 빈(중간 항목만)
$K_{1}:=$ $K_{1}:=$ $K_{1}:=$ $K_{1}:$ 초기/최종 항목(및 일부 중간 항목)이 정확히 한 개 있는 최적의 $K_{1}:=$ 빈.
$K_{2}:=$ $K_{2}:=$ $K_{2}:=$ $K_{2}:$ 초기/최종 항목(및 일부 중간 항목)이 두 개 이상인 최적의 $K_{2}:=$ 빈.

우리는 먼저 K ${\$ 과 $K_{0}$ $K_{1}$ ${\$ }의 최적 빈에 초점을 맞추고 $K_{1}$ 그러한 빈의 각 항목들 간의 편차를 $B_{1},\ldots ,B_{t}$ , … $B_{1},\ldots ,B_{t}$ , $B_{1},\ldots ,B_{t}$ $B_{1},\ldots ,B_{t}$ ${\$ 의 일부 항목에 제시한다 $B_{1},\ldots ,B_{t}$ .

$K_{1}$ $K_{1}$ ${\$ 빈의 $K_{1}$ 단일 초기/최종 항목은 B $B_{1},\ldots ,B_{|K_{1}|}$ , $B_{1},\ldots ,B_{|K_{1}|}$ $B_{1},\ldots ,B_{|K_{1}|}$ 1 $B_{1},\ldots ,B_{|K_{1}|}$ {\ $displaystyle B_{1},\ldots, B_{K_{1$ } $}}}}$ 의 초기 항목에 매핑된다 $B_{1},\ldots ,B_{|K_{1}|}$ 이러한 항목이 가장 큰 초기 항목임을 유의하십시오.
$K_{0}$ $K_{0}$ ${\$ 과 $K_{0}$ $K_{1}$ $K_{1}$ ${\$ 빈의 $K_{1}$ 중간 항목은 B $B_{1},\ldots ,B_{w}$ , $B_{1},\ldots ,B_{w}$ $B_{1},\ldots ,B_{w}$ $B_{1},\ldots ,B_{w}$ ${\$ 의 중간 항목에 매핑되어 있다 $B_{1},\ldots ,B_{w}$ 이 빈에는 중간 항목이 모두 포함되어 있다는 점에 유의하십시오.
Therefore, all items in $K_{0}$ and $K_{1}$ are mapped to all non-final items in $B_{1},\ldots ,B_{ K_{1} }$ , plus all middle items in $B_{ K_{1} +1},\ldots ,B_{w}$ .
최종 품목이 없는 $B_{1},\ldots ,B_{w}$ 각 빈 $B_{1},\ldots ,B_{w}$ $B_{1},\ldots ,B_{w}$ , $B_{1},\ldots ,B_{w}$ … $B_{1},\ldots ,B_{w}$ , $B_{1},\ldots ,B_{w}$ $B_{1},\ldots ,B_{w}$ ${\$ 의 합계는 1보다 작다.더구나 초기 항목이 1/2 이상이라 중간 항목만 합한 금액이 1/2 미만이다.Therefore, the sum of all non-final items in $B_{1},\ldots ,B_{ K_{1} }$ , plus all middle items in $B_{ K_{1} +1},\ldots ,B_{w}$ , is at most ${\$ $디스플레이$ 스타일 $K_{1$ } $+(w- K_{1$ } $)/2=(K_{1}$ $+w)/2$ } $.$
각 최적 빈의 합은 최소 1이다.따라서: $|K_{0}|+|K_{1}|\leq (|K_{1}|+w)/2$ $|K_{0}|+|K_{1}|\leq (|K_{1}|+w)/2$ + K $|K_{0}|+|K_{1}|\leq (|K_{1}|+w)/2$ $|K_{0}|+|K_{1}|\leq (|K_{1}|+w)/2$ ( $|K_{0}|+|K_{1}|\leq (|K_{1}|+w)/2$ $|K_{0}|+|K_{1}|\leq (|K_{1}|+w)/2$ + w $|K_{0}|+|K_{1}|\leq (|K_{1}|+w)/2$ ) $|K_{0}|+|K_{1}|\leq (|K_{1}|+w)/2$ / $|K_{0}|+|K_{1}|\leq (|K_{1}|+w)/2$ $K_{0$ + $K_{$ 1} + K_{1 $} \leq (K_{1}$ $+w)/2$ 즉 $2|K_{0}|+|K_{1}|\leq w\leq t$ $2|K_{0}|+|K_{1}|\leq w\leq t$ + $2|K_{0}|+|K_{1}|\leq w\leq t$ 1 + K $2|K_{0}|+|K_{1}|\leq w\leq t$ + $2|K_{0}|+|K_{1}|\leq w\leq t$ $2|K_{0}|+|K_{1}|\leq w\leq t$ $2|K_{0}|+|K_{1}|\leq w\leq t$ t ${\displaystyt$ 2 $K_{0}$ + $K_{1} \leq w$

현재 $K_{1}$ 는 K ${\$ }와 $K_{1}$ $K_{2}$ 2 ${\$ }}의 최적 빈에 초점을 맞추고 있다 $K_{2}$

$K_{1}$ $K_{1}$ ${\$ 및 $K_{1}$ $K_{2}$ 2 ${\$ }}개의 $K_{2}$ $K_{2}$ 빈에 있는 초기/최종 항목의 총 수는 $|K_{1}|+2|K_{2}|$ $|K_{1}|+2|K_{2}|$ 1 + $|K_{1}|+2|K_{2}|$ K 2 {\ $displaystyle K_{$ 1 $}$ + $2$ $|K_{1}|+2|K_{2}|$ K_ ${$ 2} $|K_{1}|+2|K_{2}|$ }}}이지만, 각 빈에는 정확히 두 $2t$ 의 초기/최종 항목이 있으므로 총 $2t$ 개수 또한 2 $2t$ ${\displaystyt}$ 이다.따라서 $|K_{1}|+2|K_{2}|\leq 2t$ 1 $|K_{1}|+2|K_{2}|\leq 2t$ + 2 $|K_{1}|+2|K_{2}|\leq 2t$ $|K_{1}|+2|K_{2}|\leq 2t$ $|K_{1}|+2|K_{2}|\leq 2t$ $|K_{1}|+2|K_{2}|\leq 2t$ t $K_{1$ $+$ 2 $K_{2} \leq 2t}$ .
후자의 두 불평등을 합산하면 $2\mathrm {OPT} (I)\leq 3t$ $2\mathrm {OPT} (I)\leq 3t$ P $2\mathrm {OPT} (I)\leq 3t$ ( $2\mathrm {OPT} (I)\leq 3t$ ) $2\mathrm {OPT} (I)\leq 3t$ $2\mathrm {OPT} (I)\leq 3t$ $2\mathrm {OPT} (I)\leq 3t$ $(\displaystyle 2\mathrm$ { $\mathrm {OPT} (I)\leq 3t/2$ $} (I)\leq 3t$ 을 의미하며, 이는 $\mathrm {OPT} (I)\leq 3t/2$ $\mathrm {OPT} (I)\leq 3t/2$ $\mathrm {OPT} (I)\leq 3t/2$ ( I $\mathrm {OPT} (I)\leq 3t/2$ ) $\mathrm {OPT} (I)\leq 3t/2$ $\mathrm {OPT} (I)\leq 3t/2$ t $\mathrm {OPT} (I)\leq 3t/2$ / $\mathrm {OPT} (I)\leq 3t/2$ ${\displaysty \mathrmatrm {OPT} (I)\leq 3t/2}$ 을 의미한다 $\mathrm {OPT} (I)\leq 3t/2$

BDF의 경우 2/3 인자가 팽팽하다.다음 인스턴스(여기서 $\epsilon >0$ > $\epsilon >0$ $\epsilon >0$ 이 $\epsilon >0$ (가) 충분히 작을 경우)를 고려하십시오.

{\begin{aligned}1-6k\epsilon ,~&~{\tfrac {1}{2}}-\epsilon ,\ldots ,{\tfrac {1}{2}}-\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\~&~\{\cdots 6k~{\text{units}}\cdots \}~&~\{\cdots 6k~{\text{units}}\cdots \}\end{aligned}}

BDF는 첫 번째 빈을 가장 큰 항목으로 초기화하고 6

6k

6k

개의

6k

가장 작은 항목으로 채운다.그런 다음

6k

6k

6k

항목은

6k

3중으로만 빈을 커버할 수 있으므로

2k+1

+

2k+1

{\displaystyle 2k+1

}개의

2k+1

2k+1

빈이 모두 채워진다.그러나 OPT에서는

[\displaystyle 3k}

빈을

3k

채울 수 있으며, 각 빈에는 중간 크기의 품목 2개와 작은 품목 2개가 들어 있다.

3등급 빈필링 알고리즘

Csirik, Frenk, Lebbe, Zhang은^[2]^{: 19–24} 3/4 근사치를 달성하는 또 다른 알고리즘을 제시한다.알고리즘은 항목을 큰 항목에서 작은 항목으로 정렬하고 세 가지 클래스로 분할한다.

X: 크기가 1/2 이상인 항목
Y: 크기가 1/2 미만이고 1/3 이상인 항목
Z: 크기가 1/3 미만인 항목.

알고리즘은 두 단계로 작동한다.1단계:

X에서 가장 큰 항목 또는 Y에서 가장 큰 항목 두 개 중 더 큰 항목으로 새 빈을 초기화하십시오.두 경우 모두 초기 빈 합계가 1보다 작다는 점에 유의하십시오.
값 오름차순으로 새 빈에 Z의 항목을 채우십시오.
X U Y 또는 Z 중 하나가 비워질 때까지 반복하십시오.

2단계:

X U Y가 비어 있는 경우 단순 다음 적합 규칙으로 Z의 항목으로 빈을 채우십시오.
Z가 비어 있는 경우, 남은 아이템을 쌍으로 X로, Y로 남은 아이템을 세 쌍씩 포장한다.

위의 예에서 BDF의 조임성을 보여 주는 세트는 다음과 같다.

{\begin{aligned}1-6k\epsilon ,~&~{\tfrac {1}{2}}-\epsilon ,\ldots ,{\tfrac {1}{2}}-\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\\{ X =1\}~&~\{\cdots  Y =6k\cdots \}~&~\{\cdots  Z =6k\cdots \}\end{aligned}}

TCF는 Y의

3k

쌍으로

3k

{\displaystyle

3k}

빈을

3k

모두 초기화하고, Z의 아이템 쌍으로 채우기 때문에 최적의 결과를 얻는다.

모든 경우 I는 $\mathrm {OPT} (I)$ $\mathrm {OPT} (I)$ T $\mathrm {OPT} (I)$ ( $\mathrm {OPT} (I)$ ) ${\displaystyle \mathrm$ { $\mathrm {TCF} (I)$ $} (I)}$ 최적 용액의 빈 수를 $\mathrm {OPT} (I)$ 나타내고, T $\mathrm {TCF} (I)$ $\mathrm {TCF} (I)$ ( I $\mathrm {TCF} (I)$ ) $\mathrmatrm {TCF$ ( $I)}$ 을(를) 3-classes 채우기 알고리즘의 전체 빈 수를 $\mathrm {TCF} (I)$ 나타낸다.그런 다음 T $\mathrm {TCF} (I)\geq (3/4)(\mathrm {OPT} (I)-4)$ $\mathrm {TCF} (I)\geq (3/4)(\mathrm {OPT} (I)-4)$ ( $\mathrm {TCF} (I)\geq (3/4)(\mathrm {OPT} (I)-4)$ ) $\mathrm {TCF} (I)\geq (3/4)(\mathrm {OPT} (I)-4)$ ( $\mathrm {TCF} (I)\geq (3/4)(\mathrm {OPT} (I)-4)$ / 4 $\mathrm {TCF} (I)\geq (3/4)(\mathrm {OPT} (I)-4)$ ) $\mathrm {TCF} (I)\geq (3/4)(\mathrm {OPT} (I)-4)$ ( O $\mathrm {TCF} (I)\geq (3/4)(\mathrm {OPT} (I)-4)$ T $\mathrm {TCF} (I)\geq (3/4)(\mathrm {OPT} (I)-4)$ ( $\mathrm {TCF} (I)\geq (3/4)(\mathrm {OPT} (I)-4)$ ) $\mathrm {TCF} (I)\geq (3/4)(\mathrm {OPT} (I)-4)$ - 4 $\mathrm {TCF} (I)\geq (3/4)(\mathrm {OPT} (I)-4)$ ) ${\displaystyle \mathrmat {TCF} (I)\geq (3/4)(\mathrmat {OPT} (I)-4$

TCF의 경우 3/4 인자가 팽팽하다.다음 인스턴스(여기서 $\epsilon >0$ > $\epsilon >0$ $\epsilon >0$ 이 $\epsilon >0$ (가) 충분히 작을 경우)를 고려하십시오.

{\begin{aligned}{\tfrac {1}{2}}-6k\epsilon ,{\tfrac {1}{2}}-6k\epsilon ,~&~{\tfrac {1}{3}}-\epsilon ,\ldots ,{\tfrac {1}{3}}-\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\~&~\{\cdots 12k~{\text{units}}\cdots \}~&~\{\cdots 12k~{\text{units}}\cdots \}\end{aligned}}

TCF는 첫 번째 빈을 가장 큰 두 개의 항목으로 초기화하고, 12 $12k$ $12k$ 개의 $12k$ 가장 작은 항목으로 채운다.그런 다음 $12k$ $12k$ $12k$ 항목은 $12k$ 4인 1조로만 빈을 커버할 수 있으므로 $3k+1$ + $3k+1$ ${\displaystyle 3k+1$ }개의 $3k+1$ $3k+1$ 빈이 모두 채워진다.그러나 OPT에서는 $[\displaystyle 4k}$ 빈을 $4k$ 채울 수 있으며, 각각의 빈에는 3개의 중간 크기의 항목과 3개의 작은 항목이 들어 있다.

다항식 시간 근사 체계

Csirik, Johnson, Kenyon은^[3] 증상이 없는 PTAS를 제시한다.모든 ε> 0,;,을 채우는 알고리즘 적어도 ⋅ OPT− 4{\displaystyle(1-5\varepsilon)\cdot \mathrm{오피티}(나는)(1− 5ε)(나는)-4}통 만약 모든 항목의 합은 13B/ϵ 3{\displaystyle 13B/\epsilon ^{3}}, 그리고 최소한 ⋅ OPT(나는)1{\displaystyle(1-2\varepsilon)\cdot \m −(1− 2ε).에서그렇지 $(1-2\varepsilon )\cdot \mathrm {OPT} (I)-1$ $않으면 hrm$ { $OPT}(I$ )-1 $}.$ 시간 $O(n^{1/\varepsilon ^{2}})$ ( n $O(n^{1/\varepsilon ^{2}})$ / $O(n^{1/\varepsilon ^{2}})$ $O(n^{1/\varepsilon ^{2}})$ ) $O(n^{1/\varepsilon ^{2})$ 에 실행된다 $O(n^{1/\varepsilon ^{2}})$ 알고리즘은 n $n^{1/\varepsilon ^{2}}$ / $n^{1/\varepsilon ^{2}}$ $n^{1/\varepsilon ^{2}}$ ${\$ n $^{1/\varepsilon ^{2$ }} $1+1/\varepsilon ^{2}$ $n^{1/\varepsilon ^{2}}$ 변수와 1 $1+1/\varepsilon ^{2}$ + 1 / $1+1/\varepsilon ^{2}$ 2 ${\$ }}개의 제약조건으로 $1+1/\varepsilon ^{2}$ 구성 선형 프로그램의 변형을 해결한다.이 알고리즘은 이론적으로만 흥미로운데, 3/4 근사치보다 나아지기 위해서는 $\varepsilon <1/20$ < 1 $\varepsilon <1/20$ / $\varepsilon <1/20$ $\varepsilon <1/20$ 을 $\varepsilon <1/20$ 를) 복용해야 하고, 그 다음에는 $n^{400}$ 수가 $n^{400}$ n $400$ {\ $displaystyle$ n $^{400}$ 을 초과하기 때문이다 $n^{400}$

그들은 또한 문제의 온라인 버전에 대한 알고리즘을 제시한다.온라인 설정에서는 1/2보다 좋은 점증적 최악의 경우 근사치를 얻을 수 없다.그러나 평균적인 경우에서 좋은 성능을 발휘하는 알고리즘이 있다.

얀센과 솔리스-오바가^[4] 점근증 FPTAS를 제시한다.모든 ε> 0,;, 적어도(1− ε)을 채우는 알고리즘 ⋅ OPT(나는)− 1{\displaystyle(1-\varepsilon)\cdot \mathrm{오피티}(나는)-1}통 만약 물품의 액수 그것보다는 적어 만약 모든 항목의 합은 13B/ϵ 3{\displaystyle 13B/\epsilon ^{3}}(들 때문은 대부분 13/ϵ 3∈에 O(1. / $13/\epsilon ^{3}\in O(1/\epsilon ^{3})$ $13/\epsilon ^{3}\in O(1/\epsilon ^{3})$ ) ${\displaystyle 13/\epsilon ^{3}\in$ O $(1/\epsilon ^{3}).$ It runs in time ${\displaystyle O\left({\frac {1}{\epsilon ^{5}}}\cdot \ln {\frac {n}{\varepsilon }}\cdot \max {(n^{2},{\frac {1}{\varepsilon }}\ln \ln {\frac {1}{\varepsilon ^{3}}})}+{\frac {1}{\varepsilo$ $n ^{4}}}{\mathcal {T_{M}}}({\frac {1}{\varepsilon ^{2}}})\right)}$ , where ${\mathcal {T_{M}}}(n)$ is the runtime complexity of the best available algorithm for matrix inversion (currently, around $O(n^{2.38})$ ).이 알고리즘은 $\varepsilon <1/4$ < $\varepsilon <1/4$ / $\varepsilon <1/4$ ${\displaystyle \varepsilon <1/4$ 이 경우 상수는 약 2 10n 2 + $2^{10}n^{2}+2^{18}$ $2^{10}n^{2}+2^{18}$ ${\$ 2 $^{10}n^{2}+2^{18}}}}$ 에 이미 3/ $2^{10}n^{2}+2^{18}$ 근사치보다 좋아지고 있다 $2^{10}n^{2}+2^{18}$

참조

^ ^a ^b Assmann, S. F; Johnson, D. S; Kleitman, D. J; Leung, J. Y. -T (1984-12-01). "On a dual version of the one-dimensional bin packing problem". Journal of Algorithms. 5 (4): 502–525. doi:10.1016/0196-6774(84)90004-X. ISSN 0196-6774.
^ ^a ^b ^c Csirik, János; J. B. G. Frenk and M. Labbé and S. Zhang (1999-01-01). "Two simple algorithms for bin covering". Acta Cybernetica. 14 (1): 13–25. ISSN 2676-993X.
^ ^a ^b Csirik, Janos; Johnson, David S.; Kenyon, Claire (2001-01-09). "Better approximation algorithms for bin covering". Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms. SODA '01. Washington, D.C., USA: Society for Industrial and Applied Mathematics: 557–566. ISBN 978-0-89871-490-6.
^ ^a ^b Jansen, Klaus; Solis-Oba, Roberto (2002-11-21). "An Asymptotic Fully Polynomial Time Approximation Scheme for Bin Covering". Proceedings of the 13th International Symposium on Algorithms and Computation. ISAAC '02. Berlin, Heidelberg: Springer-Verlag: 175–186. ISBN 978-3-540-00142-3.

[:0-1] Assmann, S. F; Johnson, D. S; Kleitman, D. J; Leung, J. Y. -T (1984-12-01). "On a dual version of the one-dimensional bin packing problem". Journal of Algorithms. 5 (4): 502–525. doi:10.1016/0196-6774(84)90004-X. ISSN 0196-6774.

[:1-2] Csirik, János; J. B. G. Frenk and M. Labbé and S. Zhang (1999-01-01). "Two simple algorithms for bin covering". Acta Cybernetica. 14 (1): 13–25. ISSN 2676-993X.

[:2-3] Csirik, Janos; Johnson, David S.; Kenyon, Claire (2001-01-09). "Better approximation algorithms for bin covering". Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms. SODA '01. Washington, D.C., USA: Society for Industrial and Applied Mathematics: 557–566. ISBN 978-0-89871-490-6.

[:3-4] Jansen, Klaus; Solis-Oba, Roberto (2002-11-21). "An Asymptotic Fully Polynomial Time Approximation Scheme for Bin Covering". Proceedings of the 13th International Symposium on Algorithms and Computation. ISAAC '02. Berlin, Heidelberg: Springer-Verlag: 175–186. ISBN 978-3-540-00142-3.

[1]

[2]

[3]

[4]

Search

빈 덮개 문제

네임스페이스

더

목차

양방향 빈 채우기 알고리즘

3등급 빈필링 알고리즘

다항식 시간 근사 체계

관련 문제

참조