균형 잡힌 번호 분할

균형 번호 파티셔닝은 멀티웨이 번호 파티셔닝의 변형으로, 각 세트에 할당된 항목 수에 제한이 있습니다.문제에 대한 입력은 크기가 다른 n개 항목 집합과 두 개의 정수 m, k입니다.출력은 항목을 m개의 서브셋으로 분할하여 각 서브셋의 항목 수가 k개까지 되도록 합니다.이에 따라 m 서브셋의 크기 합계는 가능한 한 유사해야 한다.

예를 들어 각 머신에 최대 k개의 작업을 ^[1]유지할 수 있는 작업큐가 있는 동일한 머신 스케줄링입니다.이 문제는 VLSI 칩 제조 및 유연한 제조 ^[2]시스템의 기계에 공구를 할당하는 데도 적용됩니다.

최적의 작업 스케줄링 문제에 대한 표준 3필드 표기법에서는 최대 합계를 최소화하는 문제가 "P # k k C_max"로 나타나기도 한다.중간 필드 "# k k"는 각 기계의 작업 수가 최대 k개임을 나타냅니다.This is in contrast to the unconstrained version, which is denoted by " $P\parallel C_{\max }$ ".^[3]

쌍방향 균형 파티셔닝

이원 균형 분할이라고 하는 일반적인 특수한 경우는 두 개의 부분 집합(m = 2)이 있어야 하는 경우입니다.2개의 서브셋에는 바닥(n/2)과 천장(n/2) 항목이 포함되어 있어야 합니다.파티션 문제의 일종입니다.두 부분 집합의 합계가 동일한 분할이 있는지 확인하는 것은 NP-어렵습니다. 문제를 참조하십시오[SP12].합계가 가능한 한 거의 동일한 균형 파티션을 찾는 것을 목표로 하는 알고리즘이 많이 있습니다.

Coffman, Frederickson 및 Lueker는^[5] 입력이 쌍으로 할당되는 LPT 알고리즘(RLPT라고 함)의 제한된 버전을 제시한다.입력이 균일하게 분포된 랜덤 변수일 경우 예상되는 RLPT의 최대 합계는 ${\frac {n}{4}}+{\frac {1}{2n+2}}$ ${\frac {n}{4}}+{\frac {1}{2n+2}}$ 4 ${\frac {n}{4}}+{\frac {1}{2n+2}}$ + ${\frac {n}{4}}+{\frac {1}{2n+2}}$ ${\frac {n}{4}}+{\frac {1}{2n+2}}$ n + ${\frac {n}{4}}+{\frac {1}{2n+2}}$ ({ $displaystyle$ { $frac$ { n $}$ { 4 $}$ + { \ frac { $1$ } { 2 n + 2 $}$ } ${\frac {n}{4}}+{\frac {1}{2n+2}}$ 。예상되는 워크차이(최대합계와 최소합계의 차이)는 $\Theta (1/n)$ ( $\Theta (1/n)$ n $)\displaystyle \Theta (1/n$ ^[2] 입니다.
Lueker는^[6] LDM 알고리즘의 변종(PDM(Pairwise Differencing Method)이라고 불립니다)을 제시합니다.예상되는 워크차이는 $\Theta (1/n)$ ( $\Theta (1/n)$ n $)$ { $displaystyle \Theta (1/n$ 입니다.
Tsai는^[2] RLD(Restricted Migest Difference)라는 알고리즘을 제공합니다.작업 차이는 O $O(\log n/n^{2})$ n / $O(\log n/n^{2})$ $O(\log n/n^{2})$ ) $O(\log n/n^{2})$ { $displaystyle$ O $(\log$ n $/n^{2})}$ 입니다 $O(\log n/n^{2})$ .
Yakir는^[7] BLDM이라고 불리는 m = 2에 대한 LDM 알고리즘의 균형 잡힌 변형을 제시한다.예상되는 작업 차이는 $n^{-\Theta (\log n)}$ - $n^{-\Theta (\log n)}$ （ log $nn$ ） { $displaystyle$ n^ { - \ $Theta$ ( \ $log$ n ) $n^{-\Theta (\log n)}$ } 입니다.
Mertens는^[8] 균형 잡힌 양방향 분할을 위한 완전한 시간 알고리즘을 제공합니다.BLDM 알고리즘과 완전한 Karmarkar-Karp 알고리즘을 조합합니다.

균형 잡힌 트리플렛 파티셔닝

3-가정이라고 하는 또 다른 특수한 경우는 각 부분 집합의 항목 수가 최대 3(k = 3)이어야 하는 경우입니다.합계가 동일한 분할이 존재하는지 확인하는 것은 NP-hard가 강한 것으로 알려진 정확히 3분할 문제입니다.합계가 가능한 한 거의 동일한 파티션을 찾는 것을 목표로 하는 근사 알고리즘이 있습니다.

Kelerer와 Woeginger는^[9] LPT 알고리즘을 트리플렛 파티셔닝(최대 3*m의 항목이 있고 각 서브셋에는 최대 3개의 항목이 포함되어야 함)에 적응시킵니다.이 알고리즘은 modified-LPT 또는 MLPT라고 불립니다.큰 것부터 작은 것까지 주문하고, 3개 미만의 아이템이 들어 있는 빈 중에서 가장 작은 합으로 각 아이템을 빈에 넣습니다.MLPT 알고리즘은 최대 ${\frac {4m-1}{3m}}$ . $({$ 4m-1 $}{3m$ }})의 ${\frac {4m-1}{3m}}$ 최소 합계에 도달하며, 이는 LPT가 제약되지 않은 문제에 대해 구하는 근사 비율과 동일합니다.MLPT에 대한 경계가 엄격합니다.
Chen, He 및^[10] Lin은 같은 문제에 대해 MLPT가 최소 $({displaystyle$ { $3m-1}{4m-2})$ 의 ${\frac {3m-1}{4m-2}}$ 최소 합계에 도달한다는 것을 보여주며, 이는 LPT가 제약되지 않은 문제에 대해 얻는 비율과 동일합니다.
Kelerrer와 Kotov는^[11] 최소 최대 금액의 7 $($ 표시 $스타일$ 7 $/6$ )을 $7/6$ 달성하는 다른 알고리즘(정확히 3*m 항목의 경우)을 제시한다.

더 큰 기수를 가진 균형 잡힌 파티셔닝

k ^[12]분할이라고 불리는 보다 일반적인 경우는 각 서브셋의 항목 수가 최대 k이어야 하는 경우입니다. 여기서 k는 임의의 양의 정수일 수 있습니다.

바벨, 켈러, 코토프는^[12] (일부 정수 k에 대해) k×m 항목이 있는 변종을 연구하며, 각 m 집합은 정확히 k개의 항목을 포함해야 한다.이들은 최소 최대 합계를 근사하기 위한 몇 가지 경험적 알고리즘을 제시합니다.
- 접이식 알고리즘: m = 2에 최적이며, 일반적으로 $2-{\frac {1}{m}}$ - $2-{\frac {1}{m}}$ m(\ $displaystyle 2-{\frac {1}{m$ 의 엄격한 근사 $2-{\frac {1}{m}}$ 을 갖습니다.
- 교환 알고리즘: 엄밀한 $2-{\frac {2}{m+1}}$ $2-{\frac {2}{m+1}}$ - $2-{\frac {2}{m+1}}$ 2 $2-{\frac {2}{m+1}}$ + $2-{\frac {2}{m+1}}$ 1 (\ $displaystyle 2-{\frac {2}{m+1$ 다항식으로 동작하는지는 알 수 없습니다.
- Primal-Dual 알고리즘(LPT와 MultiFit의 조합): 최대 $/$ 의 근사비({ $displaystyle 4$ /3 $4/3$ m이 충분히 클 경우 k = 4에 대해 엄격합니다.정확한 ${\frac {4m}{3m+1}}$ 은 ${\frac {4m}{3m+1}}$ ${\frac {4m}{3m+1}}$ ({ $displaystyle {4m}{$ ^[12]^{: Thm.11} $3m+1})$ 입니다.
- 또한 Modified-LPT의 ${\frac {4m-1}{3m}}$ 가 ${\frac {4m-1}{3m}}$ ${\frac {4m-1}{3m}}$ ${\frac {4m-1}{3m}}$ $({displaystyle {4m-1}{3m}})$ 라는 추측도 현재 k = ^[9]3에 대해서만 해당되는 것으로 알려져 있으며 k > 3에 대해서는 그 근사비가 최대 ^[3]2인 것으로 알려져 있다.
Michels, Korst, Aarts, van^[13] Leeuwen 및 Spiksma는^[14] 각 m 세트에 천장(n/m) 또는 바닥(n/m) 항목이 포함되어야 하는 변형을 연구합니다(so k = 천장(n/m).BLDM(Balanced-LDM)을 m=2에서 일반 m으로 확장합니다.범용 알고리즘은 $O(n\log n)$ O $O(n\log n)$ log $O(n\log n)$ n $){$ $displaystyle$ O $(n\log$ n $O(n\log n)$ 로 실행됩니다.이들은 최소 최대 합계에 대한 근사 비율이 k = 3의 경우 정확히 4/3이고 k = 4의 경우 19/12, k = 5의 경우 103/60, k = 6의 경우 643/360, k = 7의 경우 4603/2520임을 증명한다.이 비율은 혼합 정수 선형 프로그램을 풀어서 구했습니다.일반적으로(임의의 k에 대하여) 근사비는 최소 $2-\sum _{j=0}^{k-1}{\frac {j!}{k!}}$ - $2-\sum _{j=0}^{k-1}{\frac {j!}{k!}}$ j $2-\sum _{j=0}^{k-1}{\frac {j!}{k!}}$ $2-\sum _{j=0}^{k-1}{\frac {j!}{k!}}$ k - $2-\sum _{j=0}^{k-1}{\frac {j!}{k!}}$ j ! $2-\sum _{j=0}^{k-1}{\frac {j!}{k!}}$ ! k ! {\ $displaystyle 2-\sum$ _ ${j=0}^{k-1}{\frac {j!$ $}{k!}},$ $2-1k-1({$ 2- ${\frac$ {1 $}{k-1$ 입니다.3,4,5,6,7에 대한 정확한 MILP 결과는 하한에 해당합니다.k>7의 경우 정확한 결과는 알려져 있지 않지만 하한과 상한의 차이는 0.3% 미만입니다.파라미터가 서브셋의 수(m)인 경우 근사비는 $2-{\frac {1}{m}}$ 2 - $({$ 2- ${\frac$ { $1}{m$ 입니다.
Zhang, Mouratidis 및^[1] Pang은 입력이 균일하게 분포되어 있을 때와 분포가 치우쳐 있을 때 모두 BLDM이 높은 작업 차이(가장 높은 합계와 가장 낮은 합계의 차이)로 파티션을 생성할 수 있음을 보여준다.이들은 두 가지 다른 휴리스틱을 제안합니다.분포가 균일할 경우 LRM은 BLDM의 워크차이를 1/3로 줄이고, 멜드는 분산이 치우치면 워크차이를 줄입니다.하이브리드 알고리즘은 BLDM, LRM 및 멜드를 결합하여 다양한 데이터 분포에 동적으로 적응합니다.
k가 고정되면 Hochbaum과 Shmoys의^[15] PTAS를 사용하여 균등하게 ^[14]분할할 수 있습니다.k가 입력의 일부일 경우 현재 알려진 ^[14]PTAS는 없습니다.
Dell'Amico와 Martello는^[3] 모든 세트의 항목 수가 최대 k개일 때 가장 큰 금액을 최소화하는 문제를 연구합니다.이들은 이 변종의 선형 프로그램 완화가 구속되지 않은 변종의 LP 완화와 동일한 최적 값을 갖는다는 것을 보여준다. $\max((\sum x_{i})/m,x_{1})$ max ( $\max((\sum x_{i})/m,x_{1})$ $\max((\sum x_{i})/m,x_{1})$ i $\max((\sum x_{i})/m,x_{1})$ ) / $\max((\sum x_{i})/m,x_{1})$ , $\max((\sum x_{i})/m,x_{1})$ 1 ) $\max((\sum x_{i})/m,x_{1})$ { $displaystyle \max$ ( ( ( \ $sum$ x _ { $i$ } / $m$ , $x _$ { $\max((\sum x_{i})/m,x_{1})$ )는, x 는 큰 것부터 작은 것의 순서로 정렬된 입력입니다.여기서_i x 는 최적의 최대 합의 하한이며, 최악의 경우의 비율은 양쪽에서 1/2 입니다.개선된 $\max((\sum x_{i})/m,x_{1},x_{k}+x_{m+1})$ max ( $\max((\sum x_{i})/m,x_{1},x_{k}+x_{m+1})$ $\max((\sum x_{i})/m,x_{1},x_{k}+x_{m+1})$ i $\max((\sum x_{i})/m,x_{1},x_{k}+x_{m+1})$ ) / $\max((\sum x_{i})/m,x_{1},x_{k}+x_{m+1})$ , $\max((\sum x_{i})/m,x_{1},x_{k}+x_{m+1})$ 1 , $\max((\sum x_{i})/m,x_{1},x_{k}+x_{m+1})$ k + $\max((\sum x_{i})/m,x_{1},x_{k}+x_{m+1})$ m + $\max((\sum x_{i})/m,x_{1},x_{k}+x_{m+1})$ 1 ) $\max((\sum x_{i})/m,x_{1},x_{k}+x_{m+1})$ （ $display$ \ $max$ ( ( ( \ $sum x_{i}$ ) / $m$ , x $_ {$ 1} , x _ { $k}$ + $x$ _ { $m+1}$ } has $\max((\sum x_{i})/m,x_{1},x_{k}+x_{m+1})$ has has----- 2- 2 2 2 2 2 2 2 2 23 233333 22/3/3 / 2/3 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 . 1 。변경된 리스트스케줄링의 대략적인 비율은 제약이 없는 바리안트에서는 1/2이지만 제약이 있는 바리안트에서는0 이 됩니다(임의로 나쁠 수 있습니다).변경된 LPT 알고리즘의 근사비는 최대 2입니다.또한 하한의 최악의 경우 퍼포먼스 비율이 3/4이고 PD 알고리즘의 퍼포먼스 비율이 4/3(m이 충분히 클 경우)인 것도 알 수 있습니다.
그와 탄, 주 그리고^[16] 야오는 최소 금액을 최대화하는 문제를 고려하고 있다.폴딩 알고리즘의 $\max \left({\frac {2}{k}},{\frac {1}{m}}\right)$ 는 $\max \left({\frac {2}{k}},{\frac {1}{m}}\right)$ max( $\max \left({\frac {2}{k}},{\frac {1}{m}}\right)$ $)$ ${\displaystyle \max$ \left $({\frac {$ 2}{k $}}, {\frac {1}{m}}\right$ 인 것을 나타냅니다.이들은 최소 $\max \left({\frac {1}{k}},{\frac {1}{\lceil \sum _{i=1}^{m}{\frac {1}{i}}\rceil +1}}\right)$ $\max \left({\frac {1}{k}},{\frac {1}{\lceil \sum _{i=1}^{m}{\frac {1}{i}}\rceil +1}}\right)$ $\max \left({\frac {1}{k}},{\frac {1}{\lceil \sum _{i=1}^{m}{\frac {1}{i}}\rceil +1}}\right)$ $\max \left({\frac {1}{k}},{\frac {1}{\lceil \sum _{i=1}^{m}{\frac {1}{i}}\rceil +1}}\right)$ † + $\max \left({\frac {1}{k}},{\frac {1}{\lceil \sum _{i=1}^{m}{\frac {1}{i}}\rceil +1}}\right)$ )의 최악의 경우 비율을 갖는 새로운 알고리즘 HAMAPONI1을 제시합니다 $.{$ displaystyle $\max \leftfrac {1} {$ k}, ${\frac {1}{i=1}^{\lce$ }{\ $frac {$ 1}{\ $right}$ + $lce}}$ 정확한 가치보다는요.이들은 서수 알고리즘이 최소 합계를 최대화하기 위해 $O(1/\ln {m})$ O $($ / $ln µ$ m $)$ 의 $O(1/\ln {m})$ $비율$ 을 갖는다는 것을 증명합니다 $.$ 이는 HAMAPON1이 점근적으로 최적임을 나타냅니다.임의의 고정 k에 대해 서수 알고리즘은 방정식의 최대 제곱근 $\sum _{i=1}^{m}\left\lfloor \left\lfloor {\frac {k+i-1}{i}}\right\rfloor x\right\rfloor =k$ i $\sum _{i=1}^{m}\left\lfloor \left\lfloor {\frac {k+i-1}{i}}\right\rfloor x\right\rfloor =k$ 1 $\sum _{i=1}^{m}\left\lfloor \left\lfloor {\frac {k+i-1}{i}}\right\rfloor x\right\rfloor =k$ $\sum _{i=1}^{m}\left\lfloor \left\lfloor {\frac {k+i-1}{i}}\right\rfloor x\right\rfloor =k$ $\sum _{i=1}^{m}\left\lfloor \left\lfloor {\frac {k+i-1}{i}}\right\rfloor x\right\rfloor =k$ + $\sum _{i=1}^{m}\left\lfloor \left\lfloor {\frac {k+i-1}{i}}\right\rfloor x\right\rfloor =k$ $\sum _{i=1}^{m}\left\lfloor \left\lfloor {\frac {k+i-1}{i}}\right\rfloor x\right\rfloor =k$ x $\sum _{i=1}^{m}\left\lfloor \left\lfloor {\frac {k+i-1}{i}}\right\rfloor x\right\rfloor =k$ \ $displaystyle$ \ $sum _$ { i $\sum _{i=1}^{m}\left\lfloor \left\lfloor {\frac {k+i-1}{i}}\right\rfloor x\right\rfloor =k$ = $1$ }^{ $m$ } \ $left$ \ $lfloor$ \ $frac { k$ + i - $1$ } $\sum _{i=1}^{m}\left\lfloor \left\lfloor {\frac {k+i-1}{i}}\right\rfloor x\right\rfloor =k$ { i } { i } \ $loork$ = right . $loork =$ right = loork = right = loor = lo = lo = lo = right = lo = right . lo =

균형잡힌 문제와 제약없는 문제 간의 관계

균형 파티션 문제와 표준(제한되지 않음) 파티션 문제 사이에는 몇 가지 일반적인 관계가 있습니다.

Babel, Kelerer 및^[12] Kotov는 구속되지 않은 최적과 구속되지 않은 최적 사이의 비율이 $2-{\frac {2}{m}}$ 2 - $2-{\frac {2}{m}}$ 2 $2-{\frac {2}{m}}$ ({ $displaystyle 2-{\frac {2}{m$ 이며, 촘촘하다는 것을 증명한다.
Kellerer과 Kotov[11]이 균형 있게 분할을 위해 용량 k와 approximation-ratio r(최소로 큰 돈을)과 매주 heuristic 자유로운 분할을 위해(r, k+2k+1− 1m(k+1)){\displaystyle \max \left(r,{\frac{k+2}{k+1 approximation-ratio 정도 들 것과 경험을 얻기 위해 인용할 수 있다는 것을 입증한다.}}-{ $\frac {1}{m(k+1)}}\right$ 특히 $7/6$ 파티션용 7 $6($ k = 3) - 근사 $7/6$ 알고리즘을 사용하여 근사 $\max \left({\frac {7}{6}},{\frac {5}{4}}-{\frac {1}{4m}}\right)$ 6, $\max \left({\frac {7}{6}},{\frac {5}{4}}-{\frac {1}{4m}}\right)$ 5 $\max \left({\frac {7}{6}},{\frac {5}{4}}-{\frac {1}{4m}}\right)$ - $\max \left({\frac {7}{6}},{\frac {5}{4}}-{\frac {1}{4m}}\right)$ - 4 $m)$ 을 사용하여 제약 없는 파티션에 대한 휴리스틱을 얻을 수 있습니다.{ $display$ \ $max$ left \ $frac 7$ } ${4m}}\right$

다른 카디널리티 제약

카디널리티 제약은 각 서브셋에 다른 제약을 허용함으로써 일반화할 수 있습니다.이 변형은 k 파티션 문제를_i 호출하는 의 "^[12]미해결 문제" 섹션에 소개되어 있습니다.그와 탄, 주 및^[16] 야오는 다른 카디널리티 제약으로 최소 합계를 최대화하기 위해 HAMAPONI2라고 불리는 알고리즘을 제시한다.최악의 경우 비율이 $\max \left({\frac {1}{k_{m}}},{\frac {k_{1}}{k_{m}}}{\frac {1}{\left\lceil \sum _{i=1}^{m}{\frac {1}{i}}\right\rceil +1}}\right)$ ( $\max \left({\frac {1}{k_{m}}},{\frac {k_{1}}{k_{m}}}{\frac {1}{\left\lceil \sum _{i=1}^{m}{\frac {1}{i}}\right\rceil +1}}\right)$ k $\max \left({\frac {1}{k_{m}}},{\frac {k_{1}}{k_{m}}}{\frac {1}{\left\lceil \sum _{i=1}^{m}{\frac {1}{i}}\right\rceil +1}}\right)$ , $\max \left({\frac {1}{k_{m}}},{\frac {k_{1}}{k_{m}}}{\frac {1}{\left\lceil \sum _{i=1}^{m}{\frac {1}{i}}\right\rceil +1}}\right)$ $\max \left({\frac {1}{k_{m}}},{\frac {k_{1}}{k_{m}}}{\frac {1}{\left\lceil \sum _{i=1}^{m}{\frac {1}{i}}\right\rceil +1}}\right)$ k $\max \left({\frac {1}{k_{m}}},{\frac {k_{1}}{k_{m}}}{\frac {1}{\left\lceil \sum _{i=1}^{m}{\frac {1}{i}}\right\rceil +1}}\right)$ 1 $\max \left({\frac {1}{k_{m}}},{\frac {k_{1}}{k_{m}}}{\frac {1}{\left\lceil \sum _{i=1}^{m}{\frac {1}{i}}\right\rceil +1}}\right)$ ⌈ $\max \left({\frac {1}{k_{m}}},{\frac {k_{1}}{k_{m}}}{\frac {1}{\left\lceil \sum _{i=1}^{m}{\frac {1}{i}}\right\rceil +1}}\right)$ $\max \left({\frac {1}{k_{m}}},{\frac {k_{1}}{k_{m}}}{\frac {1}{\left\lceil \sum _{i=1}^{m}{\frac {1}{i}}\right\rceil +1}}\right)$ $\max \left({\frac {1}{k_{m}}},{\frac {k_{1}}{k_{m}}}{\frac {1}{\left\lceil \sum _{i=1}^{m}{\frac {1}{i}}\right\rceil +1}}\right)$ $\max \left({\frac {1}{k_{m}}},{\frac {k_{1}}{k_{m}}}{\frac {1}{\left\lceil \sum _{i=1}^{m}{\frac {1}{i}}\right\rceil +1}}\right)$ $\max \left({\frac {1}{k_{m}}},{\frac {k_{1}}{k_{m}}}{\frac {1}{\left\lceil \sum _{i=1}^{m}{\frac {1}{i}}\right\rceil +1}}\right)$ 1 $\max \left({\frac {1}{k_{m}}},{\frac {k_{1}}{k_{m}}}{\frac {1}{\left\lceil \sum _{i=1}^{m}{\frac {1}{i}}\right\rceil +1}}\right)$ + $\max \left({\frac {1}{k_{m}}},{\frac {k_{1}}{k_{m}}}{\frac {1}{\left\lceil \sum _{i=1}^{m}{\frac {1}{i}}\right\rceil +1}}\right)$ ) { $displaystyle$ \ $max \$ left \ $frac$ { $1$ } { k $_$ { $m$ } { k _ { $m$ } { \ $frac$ { { { m } } ${\ frac$ { $k_$ { { \ $lce =$ 1 $} _ sumi$ }) $임$ 을 증명합니다.

분류된 카디널리티 제약 조건

카디널리티 제약조건의 다른 일반화는 다음과 같습니다.입력 항목은 k개의 카테고리로 분할됩니다.각 카테고리 h에는 용량 제약_h k가 있다.각 m개의 서브셋은 카테고리 h의 최대_h k개의 항목을 포함할 수 있다.즉, 모든 m개의 서브셋은 특정 파티션 매트로이드의 독립된 집합이어야 합니다.이 문제의 두 가지 특별한 사례가 연구되었다.

커널 파티셔닝

커널 밸런스 파티셔닝 문제에서는 m개의 사전 지정된 항목이 커널이며, 각 m개의 서브셋은 단일 커널(및 무제한의 비커널)을 포함해야 합니다.여기서는 용량이 1인 커널 카테고리와 용량이 무제한인 비커널 카테고리의 두 가지 카테고리가 있습니다.

Chen, He 및^[17] Yao는 k = 3에 대해서도 문제가 NP-hard임을 증명합니다(k = 2에 대해서는 최대 무게 일치를 찾아 효율적으로 해결할 수 있습니다).그런 다음 커널 LPT(Kernel-LPT)라는 알고리즘을 제시합니다.각 서브셋에 커널을 할당하고 수정된 LPT 알고리즘을 실행합니다(각 항목을 k개 미만의 항목 중 가장 작은 합으로 서브셋에 넣습니다).이들은 KLPT가 k = 3일 때 최소 최대 ^[17]^{: 3}합계에 ${\frac {4m-1}{3m}}$ $($ 표시 $스타일 {frac {4m-1}{3m})$ 의 ${\frac {4m-1}{3m}}$ 근사 ${\frac {4m-1}{3m}}$ 을 갖는다는 것을 증명한다.그러나 Chen, He, Lin은^[10]^{: 2} 최소합계는 ^{[clarification needed]} ${\frac {3m-1}{2m}}$ ${\frac {2m-1}{3m-2}}$ $디스플레이스타일 3m-1)$ 이고 ${\frac {3m-1}{2m}}$ 최소합계는 $(디스플레이스타일 3m-1)$ 이다 ${\frac {2m-1}{3m-2}}$ .

카테고리당 1개의 파티션

이 문제의 또 다른 변형에서는 크기 m의 k개의 카테고리가 있으며 각 서브셋에는 각 카테고리에서 정확히1개의 아이템이 포함되어 있어야 합니다.즉, 각_h 범주 h에 대해 k = 1이다.

Wu와^[18]^[19] Yao는 LPT 알고리즘의 변형인 레이어드 LPT 알고리즘을 제시했습니다.이들은 그 근사비가 최대합 최소화를 $2-{\frac {1}{m}}$ 2 - $2-{\frac {1}{m}}$ m ( $디스플레이스타일$ 2- ${\frac {1}{m}),$ ${\frac {1}{m}}$ 인 $2-{\frac {1}{m}}$ 경우 최소합 최대화를 위한 1 ${\frac {1}{m}}$ ( $디스플레이스타일 {1}{m})$ 이며 ${\frac {1}{m}}$ , 특별한 경우 m ${\frac {m}{2m-1}}$ - ${\frac {m}{2m-1}}$ ( $디스플레이스타일 2-m},$ 일반 k1 ${\frac {m}{2m-1}}$ )로 ${\frac {m}{2m-1}}$ 개선될 수 있음을 증명한다. ${\frac {m-1}{2m-3}}$ - ${\frac {m-1}{2m-3}}$ - 3(k = 3의 경우 { $displaystyle {m-1}{2m-3})$
Li와^[20] Li는 동일한 문제에 대해 서로 다른 알고리즘을 제시했습니다.최대 합계를 최소화하기 위해 상수 k에 대해 EPTAS를 제시하고 상수 m에 대해 FPTAS를 제시합니다.최소 합계를 최대화하기 위해 일반 케이스에 대한 1/(k - 1) 근사 알고리즘과 상수 k에 대한 EPTAS를 제시한다.그들은 또한 보다 일반적인 목표를 연구한다. 즉, 합계의 벡터의 lp-norm을 최소화하는 것이다.이들은 계층 LPT 알고리즘이 모든 규범에 대한 2-근사 알고리즘임을 증명한다.
Dell'Olmo, Hansen, Palottino 및 Storchi는^[21] 이 문제에 대해 32가지 다른 목표를 연구했습니다.4개의 연산자 max,min,sum,diff 각각에 대해 각 서브셋 내의 k개의 항목에 1개의 연산자를 적용한 후 다른 서브셋에 대한 m개의 결과에 1개의 연산자를 적용할 수 있다.이 16가지 목표는 각각 최대화 또는 최소화할 수 있으며 총 32가지입니다.이러한 문제 중 21개는 선형 시간으로 해결할 수 있음을 보여줍니다. 7개는 더 복잡하지만 여전히 다항식 시간 알고리즘이 필요합니다. 3개는 NP-hard입니다. 최대화(min, sum), 최소화(max, sum), 최소화(diff, sum)입니다.그들은 최소화(diff, diff) 상태를 열어두었다.

「」를 참조해 주세요.

매트로이드 제약 번호 분할은 고정 매트로이드가 매개 변수로 주어지는 일반화이며, 각 m개의 부분 집합은 이 매트로이드의 독립 집합 또는 베이스여야 합니다.

카디널리티 제약 조건은 매트로이드가 균일한 매트로이드인 매트로이드 제약 조건의 특수한 경우입니다.
범주화된 카디널리티 제약 조건은 매트로이드가 파티션 매트로이드인 특수한 경우입니다.

레퍼런스

^ ^a ^b Zhang, Jilian; Mouratidis, Kyriakos; Pang, HweeHwa (2011-06-28). "Heuristic Algorithms for Balanced Multi-Way Number Partitioning". Twenty-Second International Joint Conference on Artificial Intelligence.
^ ^a ^b ^c Tsai, Li-Hui (1992-02-01). "Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling". SIAM Journal on Computing. 21 (1): 59–64. doi:10.1137/0221007. ISSN 0097-5397.
^ ^a ^b ^c Dell'Amico, Mauro; Martello, Silvano (2001). "Bounds for the cardinality constrained P∥Cmax problem". Journal of Scheduling. 4 (3): 123–138. doi:10.1002/jos.68. ISSN 1099-1425.
^ Garey, Michael; Johnson, David (1979). Computers and Intractability; A Guide to the Theory of NP-Completeness. pp. 96–105. ISBN 978-0-7167-1045-5.
^ Coffman, E. G.; Frederickson, G. N.; Lueker, G. S. (1984-05-01). "A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors". Mathematics of Operations Research. 9 (2): 260–266. doi:10.1287/moor.9.2.260. ISSN 0364-765X.
^ Lueker, George S (1987-12-01). "A note on the average-case behavior of a simple differencing method for partitioning". Operations Research Letters. 6 (6): 285–287. doi:10.1016/0167-6377(87)90044-7. ISSN 0167-6377.
^ Yakir, Benjamin (1996-02-01). "The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp". Mathematics of Operations Research. 21 (1): 85–99. doi:10.1287/moor.21.1.85. ISSN 0364-765X.
^ Mertens, Stephan (1999-03-11). "A complete anytime algorithm for balanced number partitioning". arXiv:cs/9903011.
^ ^a ^b Kellerer, Hans; Woeginger, Gerhard (1993-09-07). "A tight bound for 3-partitioning". Discrete Applied Mathematics. 45 (3): 249–259. doi:10.1016/0166-218X(93)90013-E. ISSN 0166-218X.
^ ^a ^b Chen, Shi Ping; He, Yong; Lin, Guohui (2002-03-01). "3-Partitioning Problems for Maximizing the Minimum Load". Journal of Combinatorial Optimization. 6 (1): 67–80. doi:10.1023/A:1013370208101. ISSN 1573-2886. S2CID 9053629.
^ ^a ^b Kellerer, Hans; Kotov, Vladimir (1999-02-01). "A 7/6–Approximation Algorithm For 3-Partitioning And Its Application To Multiprocessor Scheduling". INFOR: Information Systems and Operational Research. 37 (1): 48–56. doi:10.1080/03155986.1999.11732368. ISSN 0315-5986.
^ ^a ^b ^c ^d ^e ^f Babel, Luitpold; Kellerer, Hans; Kotov, Vladimir (1998-02-01). "The k-partitioning problem". Mathematical Methods of Operations Research. 47 (1): 59–82. doi:10.1007/BF01193837. ISSN 1432-5217. S2CID 5594197.
^ Michiels, Wil; Korst, Jan; Aarts, Emile; van Leeuwen, Jan (2003), Performance Ratios for the Differencing Method Applied to the Balanced Number Partitioning Problem, Lecture Notes in Computer Science, vol. 2607, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 583–595, doi:10.1007/3-540-36494-3_51, ISBN 978-3-540-00623-7, retrieved 2021-10-15
^ ^a ^b ^c Michiels, W.; Aarts, E.; Korst, J.; van Leeuwen, J.; Spieksma, F. C. R. (2012-02-01). "Computer-assisted proof of performance ratios for the Differencing Method". Discrete Optimization. 9 (1): 1–16. doi:10.1016/j.disopt.2011.10.001. ISSN 1572-5286.
^ Hochbaum, Dorit S.; Shmoys, David B. (1987-01-01). "Using dual approximation algorithms for scheduling problems theoretical and practical results". Journal of the ACM. 34 (1): 144–162. doi:10.1145/7531.7535. ISSN 0004-5411. S2CID 9739129.
^ ^a ^b He, Yong; Tan, Zhiyi; Zhu, Jing; Yao, Enyu (2003-11-01). "κ-Partitioning problems for maximizing the minimum load". Computers & Mathematics with Applications. 46 (10): 1671–1681. doi:10.1016/S0898-1221(03)90201-X. ISSN 0898-1221.
^ ^a ^b Chen, S. -P.; He, Y.; Yao, E. -Y. (1996-09-01). "Three-partitioning containing kernels: Complexity and heuristic". Computing. 57 (3): 255–271. doi:10.1007/bf02247409. ISSN 0010-485X. S2CID 21935917.
^ Wu, Biao; Yao, Enyue (2007-04-20). "m-Partitioning problems with partition matroid constraint". Theoretical Computer Science. 374 (1): 41–48. doi:10.1016/j.tcs.2006.11.016. ISSN 0304-3975.
^ Wu, Biao; Yao, En-yu (2008-03-01). "Lower bounds and modified LPT algorithm for m-partitioning problems with partition matroid constraint". Applied Mathematics-A Journal of Chinese Universities. 23 (1): 1–8. doi:10.1007/s11766-008-0101-8. ISSN 1993-0445. S2CID 16565038.
^ Li, Weidong; Li, Jianping (2013-04-06). "Approximation algorithms for $m$-partitioning problems with partition matroid constraint". Optimization Letters. 8 (3): 1093–1099. doi:10.1007/s11590-013-0637-2. ISSN 1862-4472. S2CID 3385030.
^ Dell’Olmo, Paolo; Hansen, Pierre; Pallottino, Stefano; Storchi, Giovanni (2005-09-01). "On uniform k-partition problems". Discrete Applied Mathematics. 150 (1): 121–139. doi:10.1016/j.dam.2005.02.013. ISSN 0166-218X.

[:8-1] Zhang, Jilian; Mouratidis, Kyriakos; Pang, HweeHwa (2011-06-28). "Heuristic Algorithms for Balanced Multi-Way Number Partitioning". Twenty-Second International Joint Conference on Artificial Intelligence.

[:52-2] Tsai, Li-Hui (1992-02-01). "Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling". SIAM Journal on Computing. 21 (1): 59–64. doi:10.1137/0221007. ISSN 0097-5397.

[:9-3] Dell'Amico, Mauro; Martello, Silvano (2001). "Bounds for the cardinality constrained P∥Cmax problem". Journal of Scheduling. 4 (3): 123–138. doi:10.1002/jos.68. ISSN 1099-1425.

[Garey_&_Johnson-4] Garey, Michael; Johnson, David (1979). Computers and Intractability; A Guide to the Theory of NP-Completeness. pp. 96–105. ISBN 978-0-7167-1045-5.

[5] Coffman, E. G.; Frederickson, G. N.; Lueker, G. S. (1984-05-01). "A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors". Mathematics of Operations Research. 9 (2): 260–266. doi:10.1287/moor.9.2.260. ISSN 0364-765X.

[6] Lueker, George S (1987-12-01). "A note on the average-case behavior of a simple differencing method for partitioning". Operations Research Letters. 6 (6): 285–287. doi:10.1016/0167-6377(87)90044-7. ISSN 0167-6377.

[:1-7] Yakir, Benjamin (1996-02-01). "The Differencing Algorithm LDM for Partitioning: A Proof of a Conjecture of Karmarkar and Karp". Mathematics of Operations Research. 21 (1): 85–99. doi:10.1287/moor.21.1.85. ISSN 0364-765X.

[8] Mertens, Stephan (1999-03-11). "A complete anytime algorithm for balanced number partitioning". arXiv:cs/9903011.

[:0-9] Kellerer, Hans; Woeginger, Gerhard (1993-09-07). "A tight bound for 3-partitioning". Discrete Applied Mathematics. 45 (3): 249–259. doi:10.1016/0166-218X(93)90013-E. ISSN 0166-218X.

[:2-10] Chen, Shi Ping; He, Yong; Lin, Guohui (2002-03-01). "3-Partitioning Problems for Maximizing the Minimum Load". Journal of Combinatorial Optimization. 6 (1): 67–80. doi:10.1023/A:1013370208101. ISSN 1573-2886. S2CID 9053629.

[:6-11] Kellerer, Hans; Kotov, Vladimir (1999-02-01). "A 7/6–Approximation Algorithm For 3-Partitioning And Its Application To Multiprocessor Scheduling". INFOR: Information Systems and Operational Research. 37 (1): 48–56. doi:10.1080/03155986.1999.11732368. ISSN 0315-5986.

[:4-12] ^ ^a ^b ^c ^d ^e ^f Babel, Luitpold; Kellerer, Hans; Kotov, Vladimir (1998-02-01). "The k-partitioning problem". Mathematical Methods of Operations Research. 47 (1): 59–82. doi:10.1007/BF01193837. ISSN 1432-5217. S2CID 5594197.

[13] Michiels, Wil; Korst, Jan; Aarts, Emile; van Leeuwen, Jan (2003), Performance Ratios for the Differencing Method Applied to the Balanced Number Partitioning Problem, Lecture Notes in Computer Science, vol. 2607, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 583–595, doi:10.1007/3-540-36494-3_51, ISBN 978-3-540-00623-7, retrieved 2021-10-15

[:7-14] Michiels, W.; Aarts, E.; Korst, J.; van Leeuwen, J.; Spieksma, F. C. R. (2012-02-01). "Computer-assisted proof of performance ratios for the Differencing Method". Discrete Optimization. 9 (1): 1–16. doi:10.1016/j.disopt.2011.10.001. ISSN 1572-5286.

[:02-15] Hochbaum, Dorit S.; Shmoys, David B. (1987-01-01). "Using dual approximation algorithms for scheduling problems theoretical and practical results". Journal of the ACM. 34 (1): 144–162. doi:10.1145/7531.7535. ISSN 0004-5411. S2CID 9739129.

[:10-16] He, Yong; Tan, Zhiyi; Zhu, Jing; Yao, Enyu (2003-11-01). "κ-Partitioning problems for maximizing the minimum load". Computers & Mathematics with Applications. 46 (10): 1671–1681. doi:10.1016/S0898-1221(03)90201-X. ISSN 0898-1221.

[:3-17] Chen, S. -P.; He, Y.; Yao, E. -Y. (1996-09-01). "Three-partitioning containing kernels: Complexity and heuristic". Computing. 57 (3): 255–271. doi:10.1007/bf02247409. ISSN 0010-485X. S2CID 21935917.

[18] Wu, Biao; Yao, Enyue (2007-04-20). "m-Partitioning problems with partition matroid constraint". Theoretical Computer Science. 374 (1): 41–48. doi:10.1016/j.tcs.2006.11.016. ISSN 0304-3975.

[19] Wu, Biao; Yao, En-yu (2008-03-01). "Lower bounds and modified LPT algorithm for m-partitioning problems with partition matroid constraint". Applied Mathematics-A Journal of Chinese Universities. 23 (1): 1–8. doi:10.1007/s11766-008-0101-8. ISSN 1993-0445. S2CID 16565038.

[20] Li, Weidong; Li, Jianping (2013-04-06). "Approximation algorithms for $m$-partitioning problems with partition matroid constraint". Optimization Letters. 8 (3): 1093–1099. doi:10.1007/s11590-013-0637-2. ISSN 1862-4472. S2CID 3385030.

[21] Dell’Olmo, Paolo; Hansen, Pierre; Pallottino, Stefano; Storchi, Giovanni (2005-09-01). "On uniform k-partition problems". Discrete Applied Mathematics. 150 (1): 121–139. doi:10.1016/j.dam.2005.02.013. ISSN 0166-218X.

[1]

[2]

[3]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

Search

균형 잡힌 번호 분할

네임스페이스

더

목차

쌍방향 균형 파티셔닝

균형 잡힌 트리플렛 파티셔닝