고다중성 빈 패킹

고다중도 빈 패킹은 빈 패킹 문제의 특수한 경우로, 다양한 항목 크기 수는 적은 반면 각 크기의 항목 수는 많습니다.일반적인 빈 패킹 문제는 NP-hard이지만 크기가 다른 수가 고정 상수라고 가정하면 고다중도 설정은 다항식 시간 내에 해결할 수 있습니다.

문제의 정의

문제에 대한 입력은 양의 정수입니다.

d - 다양한 크기의 수(문제의 차원이라고도 함)
B - 빈 용량.
s₁, ..., s_d - 크기.크기의 벡터는 s로 표시됩니다.
n₁, ..., n_d - 배수, n은_i 크기가_i s인 항목의 수입니다.곱셈의 벡터는 n으로 나타난다.
- n은 항목의 총수를 나타낸다. 즉, n₁ = n+...+n_d.
- V는 문제의 설명에 나타나는 가장 큰 정수, 즉 V = max(s₁, ..., s_d, n₁, ..., n_d, n, n, b)를 나타냅니다.

출력은 각 빈의 총 항목 크기가 최대 B가 되도록 항목을 빈에 할당한 패킹이며, 이에 따라 빈의 수는 가능한 한 작습니다.

예: d=2, s₁=30, s₂=40, n₁=n₂=5, B=120이라고 가정합니다.그래서 30, 30, 30, 30, 30, 40, 40, 40, 40, 40, 40, 40, 40, 40의 n=10개의 아이템이 있습니다.그런 다음 가능한 패킹은 {30,30,30,30},{40,40},{30,40,40}이며, 3개의 빈을 사용합니다.

구성

구성은 단일 보관함에 들어갈 수 있는 항목 집합입니다.이것은 d개의 정수로 이루어진 벡터로 나타낼 수 있으며, 설정 내의 다양한 크기의 배수를 나타냅니다.형식적으로는 각 구성 c에 대해 a θ n 및 a_c·s θ B가 되도록_c 정수 벡터_c a=a_c,1, …를_c,d 정의한다.

위의 예에서는 1*30+2*40}, 120이므로 설정 중 하나는 c={30,40,40}입니다.대응하는 벡터는 a=(1,2)이다_c.기타 설정 벡터는 (4,0), (3,0), (2,1), (1,0), (1,2), (0,1), (0,2), (0,3)입니다.사이즈가 3인 아이템이 3개밖에 없는 경우 (4.0) 설정을 사용할 수 없습니다.

구성 선형 프로그램을 사용하여 문제를 나타낼 수 있습니다. 각 구성 c에는 변수 x가_c 있으며, 이는 c가 사용되는 빈의 수를 나타냅니다.사용된 빈의 총 수는 단순히 모든 구성에 대한 x의_c 합이며, 1·x로 표시됩니다.각 사이즈에서 사용되는 아이템의 총수는 모든 구성 c에_c 대한 벡터_c a · x의 합계입니다.문제는 모든 구성 c에 걸쳐_c a·x의_c 합이 n이 되도록 1·x를 최소화하고 모든 항목을 포장하는 것이다.

알고리즘

기본 알고리즘

먼저 모든 항목이 크다고 가정합니다. 즉, e>0의 일부 분수에 대해 모든_i s가 최소 e/B입니다.그러면 각 빈의 총 항목 수는 최대 1/e이므로 총 구성 수는 최대^1/e d개입니다.각 설정은 최대 n 회 표시됩니다. $n^{d^{1/e}}$ 확인해야 할 조합은 $n^{d^{1/e}}$ $n^{d^{1/e}}$ 의 $n^{d^{1/e}}$ / $e(\displaystyle$ n^{d^{ $1/e})$ 입니다 $n^{d^{1/e}}$ .각 조합에 대해 d 구속조건(크기마다 1개씩)을 체크해야 하므로 실행시간은 d $d\cdot n^{d^{1/e}}$ n $d\cdot n^{d^{1/e}}$ / e \ $displaystyle$ d $\cdot$ n $^{d^{1/$ e $d\cdot n^{d^{1/e}}$ 입니다.이것은 d, e가 ^[1]일정할 때 n의 다항식입니다.

이 알고리즘의 주요 문제점은 (항목이 클 때만 작동한다는 사실을 제외하고) 실행 시간이 n 단위에서는 다항식이지만 입력의 길이(이진수 표현)는 log(V) 단위에서는 linear이며 log(n)의 크기 순서이다.

입력 크기의 런타임 다항식

Filippi와 Agnetis는^[2] OPT+d-2 빈을 최대 시간 O(poly(log V))로 하는 솔루션을 찾는 알고리즘을 제시했습니다.특히 d=2개의 서로 다른 크기의 경우 해당 알고리즘은 시간 O(log V)에서 최적의 솔루션을 찾습니다.

Goemans와 Rothvoss는^[3]^[4] 모든 숫자가 이진 인코딩으로 주어졌을 때 최적의 솔루션을 찾는 고정 d에 대한 알고리즘을 제시했습니다.이들의 알고리즘은 다음 문제를 해결합니다.두 개의 d차원 폴리톱 P와 Q가 주어졌을 때 합계가 Q에 있는 P의 최소 정수점 수를 구합니다.알고리즘은 시간 $(\log V)^{2^{O(d)}}$ log V $(\log V)^{2^{O(d)}}$ ) $(\log V)^{2^{O(d)}}$ ( $(\log V)^{2^{O(d)}}$ $){$ $displaystyle (\log$ V $)^{2^{O(d)}}$ )로 실행됩니다.알고리즘은 다양한 제약이 있는 동일 머신의 스케줄링이나 관련 없는 머신의 스케줄링 등 다른 문제에 적용할 수 있습니다.

일반 인스턴스를 고다중 인스턴스로 반올림

일반적인 빈 패킹 문제에 대한 몇 가지 근사 알고리즘은 다음 방식을 사용합니다.

항목을 "소"(eB보다 작음, (0,1)의 일부 부분 e)와 "대"(최소한 eB)로 구분합니다.
큰 아이템을 먼저 처리합니다.
- 다양한 크기의 수가 최대 일정 d가 되도록 항목 크기를 반올림합니다.
- 결과적으로 발생하는 고다중성 문제를 해결합니다.
예를 들어, 소품(next-fit bin packing)은 탐욕스럽게 할당합니다.새 빈이 생성되지 않으면 종료됩니다.새 빈이 생성되면 마지막 빈을 제외한 모든 빈이 최소 (1-e)B까지 가득 찬 것입니다.따라서 빈의 수는 최대 OPT/(1-e)+1 µ(1+2e)입니다.OPT+1.

알고리즘은 인스턴스 반올림 방식이 다릅니다.

선형 반올림

Lueker와 de-la-Vega는 적응형 입력 반올림 개념을 발명했습니다.아이템을 사이즈별로 정렬하여 카디널리티의² 1/e² 그룹으로 그룹화합니다.각 그룹에서 크기를 그룹 내 최대 크기로 반올림합니다.현재는 d=1/e² 사이즈 밖에 없습니다.반올림 인스턴스 솔루션은 원래 인스턴스에도 가능하지만 빈의 수가 필요 이상으로 많을 수 있습니다.손실을 수량화하려면 이전 그룹의 최대 크기로 반올림된 인스턴스를 고려합니다(첫 번째 그룹은 0으로 반올림됨).반올림된 인스턴스 D는 반올림된 인스턴스 U와 거의 동일하지만, D에는 0이 몇 개 있는² 반면 U에는 큰 항목이 몇 개 있지만² 크기는 최대 B이다.따라서 U는 D보다 더 많은² 빈을 필요로 합니다.D는 최적보다 적은 빈을 필요로 하기 때문에 빈(U) + OPT² + ne를 얻을 수 있습니다.즉, e를 선택하면 원하는 만큼 작게 만들 수 있는 가산 오차가 있습니다.

모든 항목이 큰 경우(eB 이상의 크기), OPT의 각 빈에는 1/e 항목(eB 이상의 크기)이 포함되어 있으므로 OPT는 en 이상이어야 합니다.따라서 빈(U) ( (1+e)OPT입니다.소품 취급 후 최대 $(1+2e)\mathrm {OPT} +1$ ( $(1+2e)\mathrm {OPT} +1$ + $(1+2e)\mathrm {OPT} +1$ e) $(1+2e)\mathrm {OPT} +1$ + $(1+2e)\mathrm {OPT} +1$ (\ $displaystyle (1+2$ e)\ $mathrm {OPT}$ + $1$ )을 얻을 수 있습니다.

기하학적 반올림

카르마르카 및 카르프는^[6] 기하학적 반올림이라고 불리는 보다 효율적인 반올림 방법을 제시한다(de-la-Vega 및 Lueker의 선형 반올림과는 대조적으로).이러한 혁신을 바탕으로 런타임 다항식을 n $(\$ $displaystyle$ n $)$ $1/\varepsilon$ $1/\varepsilon$ / ${\$ {\varepsilon $}(\displaystyle$ 1/\varepsilon $1/\varepsilon$ 으로 하는 알고리즘을 제시합니다.이 알고리즘은 $\mathrm {OPT} +{\mathcal {O}}(\log ^{2}(\mathrm {OPT} ))$ $\mathrm {OPT} +{\mathcal {O}}(\log ^{2}(\mathrm {OPT} ))$ + $\mathrm {OPT} +{\mathcal {O}}(\log ^{2}(\mathrm {OPT} ))$ O ( $\mathrm {OPT} +{\mathcal {O}}(\log ^{2}(\mathrm {OPT} ))$ 2 $\mathrm {OPT} +{\mathcal {O}}(\log ^{2}(\mathrm {OPT} ))$ ( $\mathrm {OPT} +{\mathcal {O}}(\log ^{2}(\mathrm {OPT} ))$ + { $displaystyle$ \ $mathrm { OPT$ } ^calo } { $log$ 2 } } ^calo } } $^2$ } ^cal ^cal } 。

개선점

이 기법은 이후 여러 저자에 의해 개선되었다.

Rothvoss는^[7] $\mathrm {OPT} +O(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))$ $\mathrm {OPT} +O(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))$ T $\mathrm {OPT} +O(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))$ + $\mathrm {OPT} +O(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))$ ( $\mathrm {OPT} +O(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))$ $\mathrm {OPT} +O(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))$ log $\mathrm {OPT} +O(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))$ $\mathrm {OPT} +O(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))$ $\mathrm {OPT} +O(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))$ （ $\mathrm {OPT} +O(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))$ \ $displaystyle$ \ $mathrm { OPT$ ） + $O$ ( \ $log$ ( \ $mathrm { OPT$ } ) \ $cdot \ log$ ( \ $mathrm$ { $OPT }$ $\mathrm {OPT} +O(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))$ 。

Hoberg와 Rothvoss는^[8] 이 알고리즘을 개량하여 $\mathrm {OPT} +O(\log(\mathrm {OPT} ))$ $\mathrm {OPT} +O(\log(\mathrm {OPT} ))$ $O$ ( $\mathrm {OPT} +O(\log(\mathrm {OPT} ))$ ) ( $)\displaystyle \mathrm {OPT}$ + O ( \ $log$ ( \ $mathrm {OPT$ } )의 솔루션을 생성하였습니다 $\mathrm {OPT} +O(\log(\mathrm {OPT} ))$ 알고리즘은 랜덤화되어 실행 시간은 총 항목 수에서 다항식입니다.

「」를 참조해 주세요.

절삭 재고 문제 - 고다중도 빈 패킹과 유사하지만 목표는 빈의 수가 아니라 각 빈에서 낭비되는 총 공간의 양을 최소화하는 것입니다.또한, 일부 변형에서는 각 크기의 항목 수가 고정되지 않지만 주어진 하한과 상한 사이에서 이동할 수 있습니다.

레퍼런스

^ Claire Mathieu. "Approximation Algorithms Part I, Week 3: bin packing". Coursera.{{cite web}}: CS1 maint :url-status (링크)
^ Filippi, Carlo; Agnetis, Alessandro (2005-09-01). "An asymptotically exact algorithm for the high-multiplicity bin packing problem". Mathematical Programming. 104 (1): 21–37. doi:10.1007/s10107-004-0567-y. ISSN 1436-4646.
^ Goemans, Michel X.; Rothvoß, Thomas (2013-12-18), "Polynomiality for Bin Packing with a Constant Number of Item Types", Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, Society for Industrial and Applied Mathematics, pp. 830–839, doi:10.1137/1.9781611973402.61, hdl:1721.1/92865, ISBN 978-1-61197-338-9, S2CID 14006427, retrieved 2021-08-17
^ Goemans, Michel X.; Rothvoss, Thomas (2020-11-07). "Polynomiality for Bin Packing with a Constant Number of Item Types". Journal of the ACM. 67 (6): 38:1–38:21. doi:10.1145/3421750. ISSN 0004-5411.
^ Fernandez de la Vega, W.; Lueker, G. S. (1981). "Bin packing can be solved within 1 + ε in linear time". Combinatorica. 1 (4): 349–355. doi:10.1007/BF02579456. ISSN 1439-6912. S2CID 10519631.
^ Karmarkar, Narendra; Karp, Richard M. (November 1982). "An efficient approximation scheme for the one-dimensional bin-packing problem". 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982): 312–320. doi:10.1109/SFCS.1982.61. S2CID 18583908.
^ Rothvoß, T. (2013-10-01). "Approximating Bin Packing within O(log OPT * Log Log OPT) Bins". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science: 20–29. arXiv:1301.4010. doi:10.1109/FOCS.2013.11. ISBN 978-0-7695-5135-7. S2CID 15905063.
^ Hoberg, Rebecca; Rothvoss, Thomas (2017-01-01), "A Logarithmic Additive Integrality Gap for Bin Packing", Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, Society for Industrial and Applied Mathematics, pp. 2616–2625, doi:10.1137/1.9781611974782.172, ISBN 978-1-61197-478-2, S2CID 1647463, retrieved 2021-02-10

[:2-1] Claire Mathieu. "Approximation Algorithms Part I, Week 3: bin packing". Coursera.{{cite web}}: CS1 maint :url-status (링크)

[2] Filippi, Carlo; Agnetis, Alessandro (2005-09-01). "An asymptotically exact algorithm for the high-multiplicity bin packing problem". Mathematical Programming. 104 (1): 21–37. doi:10.1007/s10107-004-0567-y. ISSN 1436-4646.

[3] Goemans, Michel X.; Rothvoß, Thomas (2013-12-18), "Polynomiality for Bin Packing with a Constant Number of Item Types", Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, Society for Industrial and Applied Mathematics, pp. 830–839, doi:10.1137/1.9781611973402.61, hdl:1721.1/92865, ISBN 978-1-61197-338-9, S2CID 14006427, retrieved 2021-08-17

[4] Goemans, Michel X.; Rothvoss, Thomas (2020-11-07). "Polynomiality for Bin Packing with a Constant Number of Item Types". Journal of the ACM. 67 (6): 38:1–38:21. doi:10.1145/3421750. ISSN 0004-5411.

[5] Fernandez de la Vega, W.; Lueker, G. S. (1981). "Bin packing can be solved within 1 + ε in linear time". Combinatorica. 1 (4): 349–355. doi:10.1007/BF02579456. ISSN 1439-6912. S2CID 10519631.

[:12-6] Karmarkar, Narendra; Karp, Richard M. (November 1982). "An efficient approximation scheme for the one-dimensional bin-packing problem". 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982): 312–320. doi:10.1109/SFCS.1982.61. S2CID 18583908.

[:22-7] Rothvoß, T. (2013-10-01). "Approximating Bin Packing within O(log OPT * Log Log OPT) Bins". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science: 20–29. arXiv:1301.4010. doi:10.1109/FOCS.2013.11. ISBN 978-0-7695-5135-7. S2CID 15905063.

[:3-8] Hoberg, Rebecca; Rothvoss, Thomas (2017-01-01), "A Logarithmic Additive Integrality Gap for Bin Packing", Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, Society for Industrial and Applied Mathematics, pp. 2616–2625, doi:10.1137/1.9781611974782.172, ISBN 978-1-61197-478-2, S2CID 1647463, retrieved 2021-02-10

[1]

[2]

[3]

[4]

[6]

[7]

[8]

Search

고다중성 빈 패킹

네임스페이스

더

목차

문제의 정의

구성