다중 부분집합합

다중 부분집합 문제는 컴퓨터 과학 및 운영 연구의 최적화 문제입니다.이것은 부분집합 문제의 일반화이다.이 문제에 대한 입력은 n개의 정수와 서브셋의 수를 나타내는 양의 정수 m으로 이루어진 $(\displaystyle$ S $)$ 입니다 $S$ .목표는 입력 정수로 m개의 부분 집합을 구성하는 것입니다.이 문제에는 몇 가지 종류가 있습니다.

Max-sum MSSP: 1,...m의 각 서브셋 j에 대해 용량_j C가 있습니다.목표는 각 부분 집합 j의 합이 최대 ^[1]C가_j 되도록 모든 부분 집합의 합을 최대한 크게 만드는 것입니다.
Max-min MSSP(병목현상 MSSP 또는 BMSSP라고도 함) : 각 서브셋에는 용량이 있지만, 현재 목표는 최소 서브셋 합계를 가능한 ^[1]크게 만드는 것입니다.
공정한 SSP: 서브셋은 고정 용량이 없지만 각 서브셋은 다른 사람에게 속합니다.각 개인의 효용은 하위 집합에 있는 항목의 합계입니다.목표는 max-min 항목 할당과 같이 주어진 공정성 기준을 충족하는 하위 집합을 구성하는 것이다.

Max-sum 및 Max-min MSSP

m이 변수(입력 부분)인 경우, 두 문제 모두 3-분할에서 감소하여 NP-난이 강합니다.즉, P=NP가 아닌 한 FPTAS가 존재하지 않습니다.

m=2인 경우에도 P=NP가 아니면 FPTAS가 없다.이는 Equal-Cardinality Partition Problem(EPART; 동등 카디널리티 파티션 문제)를 줄임으로써 알 수 있습니다.

목표합이 T인 EPART의 인스턴스₁ a, …, a가_n 주어지면, 양쪽 서브셋에 대해서 목표합(n+1)T를 가지는 MSSP의 인스턴스 2T₁+a, …, 2T_n+a를 구축한다.
EPART에 대한 솔루션은 두 부분으로 구성되며, 각 부분에는 T의 합을 갖는 n/2개의 요소가 있습니다.양쪽 MSP 바리안트의 최적 솔루션에 대응하고 있습니다.즉, 가능한 한 큰 (n+1)T의 합계를 가지는 2개의 서브셋입니다.마찬가지로 MSSP의 각 최적 솔루션은 EPART에 대한 솔루션에 해당합니다.
MSSP에 대한 최적의 솔루션이 아닌 솔루션은 적어도1개의 항목을 할당되지 않은 상태로 두기 때문에 합계는 2nT, 최소값은 nT입니다.T입니다.두 모델 모두 근사비는 $1-1/(n+1)$ 1 - $1-1/(n+1)$ / ( $1-1/(n+1)$ + $1-1/(n+1)$ $){$ $displaystyle$ 1 - 1 / ( n + 1) $1-1/(n+1)$ } 입니다.
$(1-\epsilon )$ $\epsilon <1/(n+1)$ < $\epsilon <1/(n+1)$ / $\epsilon <1/(n+1)$ ( $\epsilon <1/(n+1)$ + $\epsilon <1/(n+1)$ $){$ $displaystyle \epsilon$ < $1$ / ( $\epsilon <1/(n+1)$ $(1-\epsilon )$ + 1) $(1-\epsilon )$ $displaystyle$ ( $1$ - $(1-\epsilon )$ ){ displaystyle ( 1 - \ $epsilon$ )}의 $(1-\epsilon )$ 알고리즘이 존재할 경우 최적의 솔루션을 찾아야 합니다.
FPTAS가 있으면 런타임 다항식이 n인 $\epsilon =1/(n+2)$ $\epsilon =1/(n+2)$ / ( $n$ + $\epsilon =1/(n+2)$ ) $\epsilon =1/(n+2)$ \ $displaystyle$ \ $explon$ = $1$ / ( n + 2) $\epsilon =1/(n+2)$ }과 같은 알고리즘을 사용할 수 있습니다.이 알고리즘은 EPART를 시간 다항식으로 n으로 푸는 데 사용할 수 있습니다.그러나 이것은 P=NP가 아니면 불가능하다.

다음의 근사 알고리즘이 ^[1]알려져 있습니다.

max-sum MSSP의 경우 변수 m:
- $"\displaystyle\epsilon"$ 이 $\epsilon$ 고정된 경우 시간 O(m+n)에 실행되는 PTAS.런타임은 적어도 1/ $1/\epsilon ^{2}$ † $({$ 1 $/\epsilon$ ^{ $2$ 에서 지수화되어 있으며, 저자들은 이것이 실용적이지 않다고 생각합니다.
- 서브셋 용량이 ^[2]다른 경우의 보다 일반적인 PTAS.
- 시간 O(mn)로² 실행되는 3/4 근사 알고리즘.^[3]
max-min MSSP의 경우:
- 변수 m: 시간 O(n log n)의 2/3 근사치.P=NP(3-표준에서 감소)가 아니면 더 나은 근사치가 불가능하다.
- 고정 m: $O(n^{2m/\epsilon })$ ( $O(n^{2m/\epsilon })$ $O(n^{2m/\epsilon })$ / $O(n^{2m/\epsilon })$ ) $O(n^{2m/\epsilon })$ { $displaystyle$ O ( $n^$ 2 $m$ / \ $epsilon }$ } $O(n^{2m/\epsilon })$ } 。
- Lenstra 알고리즘을 사용한 PTAS의 고유 입력값 고정 수.

부분집합 균등화 문제

Fair Subset Sum^[4] Problem(FSSP; 균등화 서브셋합 문제)는 SSP의 일반화입니다.SSP에서는 서브셋을 선택한 후 아이템이 2개 이상의 에이전트 간에 할당됩니다.각 에이전트의 효용은 자신에게 할당된 항목의 가중치 합계와 같습니다.목적은 효용 프로파일이 평등주의 규칙이나 비례적 공정 규칙과 같은 공정성의 기준을 충족시키는 것이다.이 문제에는 다음 두 가지 종류가 있습니다.

공유 항목: 각 항목을 모든 에이전트에 할당할 수 있습니다.이 설정은 동일한 가치의 공정한 항목 배분과 유사하지만(각 항목의 가치는 모든 대리인에게 동일하며 항목 가중치와 동일) 항목의 총 가중치에는 추가적인 역량 제약이 있다.예를 들어, 항목 가중치가 3,5,7,9이고 용량이 15라고 가정합니다.그런 다음 ({3,5,7}, {}), ({3,5}, {7}), ({5}), {3,7}), ({5}, {9}) 등의 할당이 가능합니다.이러한 할당 중 max-min 기준을 충족하는 할당은 ({3,5}, {7})입니다.
개별 항목: 에이전트별로 해당 에이전트에게만 할당할 수 있는 개별 항목 세트가 있습니다.이 설정은 각 프로젝트가 고유한 에이전트에 속하는 서로 다른 프로젝트에 할당해야 하는 예산이 있는 경우에 적합합니다.

두 배리언트 모두 NP 하드입니다.단,^[5] 2개의 에이전트가 있는 경우 모든 Pareto 최적 솔루션을 열거하는 의사 다중 시간 알고리즘이 있습니다.

공유 항목의 경우: 에이전트 i에 총 가중치_i w를 주는 솔루션이 존재하는 $Q(w_{1},w_{2})={\text{true}}$ 경우 Q $Q(w_{1},w_{2})={\text{true}}$ , $Q(w_{1},w_{2})={\text{true}}$ w 2) $Q(w_{1},w_{2})={\text{true}}$ true( $w_{$ 1}, $w_$ {2} $= truetext{$ true})가 되도록 $2차원$ 배열 Q(\ $displaystyle$ Q)를 $Q$ 정의합니다.가능한 $O(n\cdot c^{2})$ 유틸리티 프로파일을 $O(n\cdot c^{2})$ O $O(n\cdot c^{2})$ $O(n\cdot c^{2})$ $O(n\cdot c^{2})$ 2) $O(n\cdot c^{2})$ { $displaystyle$ O $(n\cdot$ c $^{2}})$ 에 $O(n\cdot c^{2})$ 열거할 수 있습니다.여기서 n은 항목의 수이고 c는 항목의 최대 크기입니다.
개별 항목: 각 에이전트 j에 $Q_{j}(w)={\text{true}}$ $Q_{j}$ 배열 Q $Q_{j}$ j $Q_{j}(w)={\text{true}}$ $displaystyle Q_$ $Q_{j}(w)={\text{true}}$ }) $=$ true $(\displaystyle Q_{j}($ w)= $text{$ true})를 $Q_{j}(w)={\text{true}}$ 정의합니다.각 $Q_{j}$ $({$ 는 $Q_{j}$ 에이전트 j의 개별 항목을 사용하여 개별적으로 구성할 수 있습니다.그런 다음 두 배열을 서로 반대 방향으로 이동하고 파레토 프런티어의 모든 할당을 열거할 수 있습니다.실행시간은 $O(n\cdot c)$ ( $O(n\cdot c)$ c $O(n\cdot c)$ ) { $displaystyle$ O ( $n$ \ $cdot$ c ) $O(n\cdot c)$ 。

Nicosia, Pacifici 및 Pferschy는 공정성의 가격, 즉 공정 솔루션의 최대 전력 총합과 최대 전력 총합 사이의 비율을 연구한다.

공유 아이템의 경우: 공정가격의 최대값(max-min fairity)에 제한이 없습니다.예를 들어 값이 1, e, e, e, e인 4개의 항목이 일부 작은 e>0에 있다고 가정합니다.최대 합계는 1입니다.한쪽 에이전트는 값이 1인 항목을 지정하고 다른 쪽 에이전트는 값을 지정하지 않습니다.단, max-min 할당에서는 각 에이전트 값이 최소e이므로 합계는 최대 3e여야 합니다.따라서 POF는 1/(3e)로 제한되지 않습니다.
앨리스에는 값이 1과 e인 2개의 항목이 있으며, 일부 작은 e>0의 경우입니다.George는 값이 e인 두 개의 아이템을 가지고 있습니다.용량은 1 입니다.최대 합계는 1입니다. 앨리스에게 값이 1인 아이템을 주고 조지는 아무것도 주지 않습니다.단, max-min 할당은 두 에이전트 모두에 값 e를 부여합니다.따라서 POF는 1/(2e)로 제한되지 않습니다.
개별 항목의 경우: max-min 공정성의 공정성 가격에는 한계가 없습니다.예를 들어 Alice에 값이 1과 e인 2개의 항목이 있다고 가정합니다(일부 작은 e>0).George는 값이 e인 두 개의 아이템을 가지고 있습니다.용량은 1 입니다.최대 합계는 1입니다. 앨리스가 값이 1인 항목을 얻고 George가 아무것도 얻지 못한 경우입니다.단, max-min 할당은 두 에이전트 모두에 값 e를 부여합니다.따라서 POF는 1/(2e)로 제한되지 않습니다.

두 경우 모두 항목 값이 상수 a에 의해 제한되면 POF는 ^[5]a의 함수에 의해 제한된다.

다중 배낭 문제

Multiple Napsack Problem(MKP; 다중 배낭 문제)는 max-sum MSSP와 배낭 문제를 모두 일반화한 것입니다.이 문제에는 각 항목이 값과 무게를 모두 갖는 mn개의 배낭과 n개의 항목이 있습니다.목표는 각 빈의 총 무게가 최대 용량이 되도록 가능한 많은 값을 m개의 빈에 채우는 것입니다.

Max-sum MSSP는 각 항목의 값이 무게와 동일한 MKP의 특수한 경우입니다.
배낭 문제는 m=1인 MKP의 특수한 경우입니다.
부분합 문제는 MKP의 특수한 경우로, 각 항목의 값이 모두 무게와 같고 m=1이다.

MKP에는 다항식 시간 근사 ^[6]방식이 있습니다.

레퍼런스

^ ^a ^b ^c Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000-02-01). "The Multiple Subset Sum Problem". SIAM Journal on Optimization. 11 (2): 308–319. doi:10.1137/S1052623498348481. ISSN 1052-6234.
^ "A PTAS for the Multiple Subset Sum Problem with different knapsack capacities". Information Processing Letters. 73 (3–4): 111–118. 2000-02-29. doi:10.1016/S0020-0190(00)00010-7. ISSN 0020-0190.
^ Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2003-03-01). "A 3/4-Approximation Algorithm for Multiple Subset Sum". Journal of Heuristics. 9 (2): 99–111. doi:10.1023/A:1022584312032. ISSN 1572-9397.
^ Nicosia, Gaia; Pacifici, Andrea; Pferschy, Ulrich (2015). Hoefer, Martin (ed.). "Brief Announcement: On the Fair Subset Sum Problem". Algorithmic Game Theory. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 309–311. doi:10.1007/978-3-662-48433-3_28. ISBN 978-3-662-48433-3.
^ ^a ^b "Price of Fairness for allocating a bounded resource". European Journal of Operational Research. 257 (3): 933–943. 2017-03-16. arXiv:1508.05253. doi:10.1016/j.ejor.2016.08.013. ISSN 0377-2217.
^ Chandra Chekuri and Sanjeev Khanna (2005). "A PTAS for the multiple knapsack problem". SIAM Journal on Computing. 35 (3): 713–728. CiteSeerX 10.1.1.226.3387. doi:10.1137/s0097539700382820.

[:1-1] Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000-02-01). "The Multiple Subset Sum Problem". SIAM Journal on Optimization. 11 (2): 308–319. doi:10.1137/S1052623498348481. ISSN 1052-6234.

[2] "A PTAS for the Multiple Subset Sum Problem with different knapsack capacities". Information Processing Letters. 73 (3–4): 111–118. 2000-02-29. doi:10.1016/S0020-0190(00)00010-7. ISSN 0020-0190.

[3] Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2003-03-01). "A 3/4-Approximation Algorithm for Multiple Subset Sum". Journal of Heuristics. 9 (2): 99–111. doi:10.1023/A:1022584312032. ISSN 1572-9397.

[4] Nicosia, Gaia; Pacifici, Andrea; Pferschy, Ulrich (2015). Hoefer, Martin (ed.). "Brief Announcement: On the Fair Subset Sum Problem". Algorithmic Game Theory. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 309–311. doi:10.1007/978-3-662-48433-3_28. ISBN 978-3-662-48433-3.

[:2-5] "Price of Fairness for allocating a bounded resource". European Journal of Operational Research. 257 (3): 933–943. 2017-03-16. arXiv:1508.05253. doi:10.1016/j.ejor.2016.08.013. ISSN 0377-2217.

[6] Chandra Chekuri and Sanjeev Khanna (2005). "A PTAS for the multiple knapsack problem". SIAM Journal on Computing. 35 (3): 713–728. CiteSeerX 10.1.1.226.3387. doi:10.1137/s0097539700382820.

[1]

[2]

[3]

[4]

[5]

[6]

Search

다중 부분집합합

네임스페이스

더

목차

Max-sum 및 Max-min MSSP

부분집합 균등화 문제

다중 배낭 문제

레퍼런스