This article provides a comprehensive exploration of submodular maximization problems, focusing on those subject to uniform and partition matroids. Crucial for a wide array of applications in fields ranging from computer science to systems engineering, submodular maximization entails selecting elements from a discrete set to optimize a submodular utility function under certain constraints. We explore the foundational aspects of submodular functions and matroids, outlining their core properties and illustrating their application through various optimization scenarios. Central to our exposition is the discussion on algorithmic strategies, particularly the sequential greedy algorithm and its efficacy under matroid constraints. Additionally, we extend our analysis to distributed submodular maximization, highlighting the challenges and solutions for large-scale, distributed optimization problems. This work aims to succinctly bridge the gap between theoretical insights and practical applications in submodular maximization, providing a solid foundation for researchers navigating this intricate domain.
๋
ผ๋ฌธ ID : 2501.01071์ ๋ชฉ : Submodular Maximization Subject to Uniform and Partition Matroids: From Theory to Practical Applications and Distributed Solutions์ ์ : Solmaz S. Kia (University of California Irvine)๋ถ๋ฅ : cs.DS (๋ฐ์ดํฐ ๊ตฌ์กฐ ๋ฐ ์๊ณ ๋ฆฌ์ฆ)๋ฐํ ์๊ฐ : 2025๋
1์ 2์ผ๋
ผ๋ฌธ ๋งํฌ : https://arxiv.org/abs/2501.01071 ๋ณธ ๋
ผ๋ฌธ์ ๊ท ๋ฑ ๋งคํธ๋ก์ด๋์ ๋ถํ ๋งคํธ๋ก์ด๋ ์ ์ฝ ์กฐ๊ฑด์ ๋ฐ๋ ๋ถ๋ถ๋ชจ๋ ์ต๋ํ ๋ฌธ์ ์ ๋ํ ํฌ๊ด์ ์ธ ํ๊ตฌ๋ฅผ ์ ๊ณตํฉ๋๋ค. ๋ถ๋ถ๋ชจ๋ ์ต๋ํ๋ ์ปดํจํฐ ๊ณผํ์์ ์์คํ
๊ณตํ์ ์ด๋ฅด๋ ๊ด๋ฒ์ํ ์์ฉ ๋ถ์ผ์์ ์ค์ํ๋ฉฐ, ํน์ ์ ์ฝ ์กฐ๊ฑด ํ์์ ๋ถ๋ถ๋ชจ๋ ํจ์ฉ ํจ์๋ฅผ ์ต์ ํํ๊ธฐ ์ํด ์ด์ฐ ์งํฉ์์ ์์๋ฅผ ์ ํํ๋ ๊ฒ์ ํฌํจํฉ๋๋ค. ๋ณธ ๋
ผ๋ฌธ์ ๋ถ๋ถ๋ชจ๋ ํจ์์ ๋งคํธ๋ก์ด๋์ ๊ธฐ์ด ์ธก๋ฉด์ ํ๊ตฌํ๊ณ , ํต์ฌ ์ฑ์ง์ ๊ฐ๊ดํ๋ฉฐ ๋ค์ํ ์ต์ ํ ์๋๋ฆฌ์ค๋ฅผ ํตํด ์์ฉ์ ์ค๋ช
ํฉ๋๋ค. ๋
ผ์์ ํต์ฌ์ ์๊ณ ๋ฆฌ์ฆ ์ ๋ต, ํนํ ์์ฐจ ํ์ ์๊ณ ๋ฆฌ์ฆ๊ณผ ๋งคํธ๋ก์ด๋ ์ ์ฝ ์กฐ๊ฑด ํ์์์ ํจ์จ์ฑ์
๋๋ค. ๋ํ ๋ถ์ฐ ๋ถ๋ถ๋ชจ๋ ์ต๋ํ์ ๋ํ ๋ถ์์ ํ์ฅํ์ฌ ๋๊ท๋ชจ ๋ถ์ฐ ์ต์ ํ ๋ฌธ์ ์ ๋์ ๊ณผ์ ์ ํด๊ฒฐ์ฑ
์ ๊ฐ์กฐํฉ๋๋ค.
๋ณธ ๋
ผ๋ฌธ์ด ๋ค๋ฃจ๋ ํต์ฌ ๋ฌธ์ ๋ ์กฐํฉ ์ต์ ํ ๋ฌธ์ ์
๋๋ค:
max f(S) subject to S โ F(P)
์ฌ๊ธฐ์ ๋ชฉํ๋ ๊ธฐ์ด ์งํฉ P์์ ์ด์ฐ ์์ ๋ถ๋ถ์งํฉ S๋ฅผ ์ ํํ์ฌ ์ ์ฝ ์กฐ๊ฑด F ํ์์ ํจ์ฉ ํจ์ f : 2^P โ Rโฅ0์ ์ต๋ํํ๋ ๊ฒ์
๋๋ค.
๊ด๋ฒ์ํ ์ ์ฉ์ฑ : ๋ถ๋ถ๋ชจ๋ ์ต๋ํ ๋ฌธ์ ๋ ๋ค์์ ํฌํจํ ์๋ง์ ์ค์ ์์ฉ์์ ๋ํ๋ฉ๋๋ค:๋ฐ์ดํฐ ์์ฝ ๋ฐ ์ผ์ ๋ฐฐ์น ๋คํธ์ํฌ ์์ ๊ด๋ฆฌ ํด๋ฌ์คํฐ๋ง ์๊ณ ๋ฆฌ์ฆ ์ถ์ฒ ์์คํ
์์
๋คํธ์ํฌ ๋ถ์ ๊ณ์ฐ ๋ณต์ก์ฑ : ์ด๋ฌํ ์กฐํฉ ์ต์ ํ ๋ฌธ์ ๋ ์ผ๋ฐ์ ์ผ๋ก NP-hard์ด๋ฉฐ, ๋ณด์ฅ๋ ๊ทผ์ฌ๋น๋ฅผ ๊ฐ๋ ๋คํญ์ ์๊ฐ ์๊ณ ๋ฆฌ์ฆ์ ์ฐพ์์ผ ํฉ๋๋ค.๋ถ์ฐ ์๊ตฌ์ฌํญ : ํ๋ ์ง๋ฅํ ์์คํ
์์ ๋ฐ์ดํฐ๋ ๋ฐฉ๋ํ๊ณ ๋ถ์ฐ ์ ์ฅ๋์ด ์์ผ๋ฏ๋ก ๊ฐ์ธ์ ๋ณด ๋ณดํธ ๋ฐ ํ์ค์ํ ๊ณ์ฐ์ ํ์์ฑ์ ๊ณ ๋ คํด์ผ ํฉ๋๋ค.์ค์ํ ์๊ณ ๋ฆฌ์ฆ : ์ ํต์ ์๊ณ ๋ฆฌ์ฆ์ ์ ์ญ ์ ๋ณด๊ฐ ํ์ํ์ฌ ๋ถ์ฐ ํ๊ฒฝ์ ๋ถ์ ํฉํฉ๋๋คํต์ ์ค๋ฒํค๋ : ๋ถ์ฐ ๊ตฌํ์ ํต์ ๋น์ฉ ๋ฐ ๋๊ธฐํ ๋ฌธ์ ์ ์ง๋ฉดํฉ๋๋ค๊ฐ์ธ์ ๋ณด ๋ณดํธ ๋ฌธ์ : ์์ด์ ํธ๋ ์ค์ ๊ถํ๊ณผ ์ ๋ณด ๊ณต์ ๋ฅผ ๊บผ๋ฆด ์ ์์ต๋๋คํ์ฅ์ฑ : ๋๊ท๋ชจ ๋ฐ์ดํฐ ์งํฉ์ ์ฒ๋ฆฌ ํจ์จ์ฑ์ด ์ ํ๋ฉ๋๋ค๋ณธ ๋
ผ๋ฌธ์ ๋ถ๋ถ๋ชจ๋ ์ต๋ํ์ ์ด๋ก ์ ํต์ฐฐ๊ณผ ์ค์ ์์ฉ ๊ฐ์ ๊ฒฉ์ฐจ๋ฅผ ์ขํ๋ ๊ฒ์ ๋ชฉํ๋ก ํ๋ฉฐ, ํนํ ๋ค์์ ์ค์ ์ ๋ก๋๋ค:
๊ท ๋ฑ ๋งคํธ๋ก์ด๋ ์ ์ฝ: |S| โค ฮบ ๋ถํ ๋งคํธ๋ก์ด๋ ์ ์ฝ: |S โฉ Pi| โค ฮบi, i โ {1,...,N} ์ด๋ก ์ ๊ธฐ์ด ํตํฉ : ๋ถ๋ถ๋ชจ๋ ํจ์์ ๋งคํธ๋ก์ด๋์ ๊ธฐ์ด ์ด๋ก ์ ์ฒด๊ณ์ ์ผ๋ก ์ ๋ฆฌํ๋ฉฐ, ํ๊ณ ์์ต ์ฒด๊ฐ ์ฑ์ง ๋ฐ ๊ณก๋ฅ ๊ฐ๋
์ ํฌํจํฉ๋๋ค์๊ณ ๋ฆฌ์ฆ ์ ๋ต ๊ฐ์ : ์์ฐจ ํ์ ์๊ณ ๋ฆฌ์ฆ๊ณผ ์ฐ์ ํ์ ์๊ณ ๋ฆฌ์ฆ์ ์ฑ๋ฅ ๋ณด์ฅ์ ๋ํ ์ฌ์ธต ๋ถ์์ค์ ์์ฉ ์์ฐ : ์ผ์ ๋ฐฐ์น, ๋ฐ์ดํฐ ์์ง, ์ง์์ ๋ชจ๋ํฐ๋ง ๋ฑ ์ฌ๋ฌ ๊ตฌ์ฒด์ ์์ฉ ์ฌ๋ก๋ฅผ ํตํด ์ด๋ก ์ ์ค์ฉ์ฑ์ ์์ฐ๋ถ์ฐ ์๋ฃจ์
: ๋ถ์ฐ ํ๊ฒฝ์์์ ์๊ณ ๋ฆฌ์ฆ ์ ์ ๋ฐ ์ฑ๋ฅ ๋ถ์ ๋
ผ์์ฑ๋ฅ ๊ฒฝ๊ณ ๋ถ์ : ๋ค์ํ ์ ์ฝ ์กฐ๊ฑด ํ์์์ ๊ทผ์ฌ๋น ๋ถ์ ์ ๊ณตํจ์ f : 2^P โ Rโฅ0๋ ๋ค์์ ๋ง์กฑํ ๋ ๋ถ๋ถ๋ชจ๋์
๋๋ค:
f(R) + f(S) โฅ f(R โช S) + f(R โฉ S), โS,R โ P
๋ถ๋ถ๋ชจ๋ ํจ์๋ ํ๊ณ ์์ต ์ฒด๊ฐ์ ๋ง์กฑํ๋ ๊ฒ๊ณผ ๋์น์
๋๋ค:
f(S โช {p}) - f(S) โฅ f(R โช {p}) - f(R), โS โ R โ P, p โ P\R
๊ท ๋ฑ ๋งคํธ๋ก์ด๋ : M = {S โ P | |S| โค ฮบ}๋ถํ ๋งคํธ๋ก์ด๋ : M = {S โ P | |S โฉ Pi| โค ฮบi, i โ {1,...,N}}๊ท ๋ฑ ๋งคํธ๋ก์ด๋ ์ ์ฝ์ ๊ฒฝ์ฐ:
Si = Si-1 โช argmax_{pโP\Si-1} ฮf(p|Si-1), i โ {1,...,ฮบ}
์ฑ๋ฅ ๋ณด์ฅ : ฮฑuniform = 1 - 1/e โ 0.63
๋ถํ ๋งคํธ๋ก์ด๋ ์ ์ฝ์ ๊ฒฝ์ฐ, ์ฑ๋ฅ ๋ณด์ฅ์ ฮฑpartition = 1/2์
๋๋ค.
๋ค์ค์ ํ ํ์ฅ F(x)๋ฅผ ์ด์ฉํ์ฌ ์ด์ฐ ๋ฌธ์ ๋ฅผ ์ฐ์ ์ต์ ํ๋ก ๋ณํํฉ๋๋ค:
F(x) = ฮฃ_{RโP} f(R) ฮ _{pโR} [x]_p ฮ _{pโR} (1-[x]_p)
์ฐ์ ์ต์ ํ ๋ฌธ์ ๋ฅผ ํ์ด์:
max F(x), s.t. x โ P(M)
์ฌ๊ธฐ์ P(M)์ ๋งคํธ๋ก์ด๋ ๋ค๋ฉด์ฒด์
๋๋ค.
๊ณก๋ฅ ๋ถ์ : ์ด ๊ณก๋ฅ c โ 0,1 ์ ๋์
ํ์ฌ ๊ทผ์ฌ๋น๋ฅผ ์ ๋ฐํํฉ๋๋ค:๊ท ๋ฑ ๋งคํธ๋ก์ด๋: ฮฑuniform = (1/c)(1 - 1/e^c) ๋ถํ ๋งคํธ๋ก์ด๋: ฮฑpartition = 1/(1+c) ๋ถ์ฐ ์ ์ :ํด๋ฐํด ๊ฒฝ๋ก ๋ฌธ์ ์ฒ๋ฆฌ๋ฅผ ์ํ ๋ฉ์์ง ์ ๋ฌ ๋ฉ์ปค๋์ฆ ์ ๋ณด ๊ณต์ ๊ทธ๋ํ์ ํด๋ฆฌํฌ ์ ๋ถ์ ํ๋ฅ ์ ํต์ ํ๋ ์์ํฌ ๋ค์ค์ ํ ํ์ฅ์ ํ๋ฅ ์ ํด์ : ์ฌ๊ธฐ์ Rx๋ ๊ฐ ์์๊ฐ ํ๋ฅ x _p๋ก ํฌํจ๋๋ ๋ฌด์์ ์งํฉ์
๋๋ค.๋ชฉํ : ฮบ๊ฐ์ ์์ ํฌ์ธํธ๋ฅผ ์ ํํ์ฌ ๋๊ท๋ชจ ๋ฐ์ดํฐ ์งํฉ์ ์ต์ ์ผ๋ก ํํํจ์ฉ ํจ์ : f(R) = L({d0}) - L(R โช {d0})์ ์ฝ : ๊ท ๋ฑ ๋งคํธ๋ก์ด๋ |R| โค ฮบ์๋๋ฆฌ์ค : 2D ๊ณต๊ฐ์ ฮบ๊ฐ์ ๋ฐ์ดํฐ ์์ง ์ฅ์น ๋ฐฐํฌ๊ฑฐ๋ฆฌ ํจ์ : ์ ํด๋ฆฌ๋ ๊ฑฐ๋ฆฌ dist(b,d) = ||b-d||๋ค์ค ์์ด์ ํธ ๋ณํ : ๋ถํ ๋งคํธ๋ก์ด๋ ์ ์ฝ๋คํธ์ํฌ : ๊ตํต ๋คํธ์ํฌ ๊ทธ๋ํ G = (V,L)๋ชฉํ : ํธ๋ํฝ ์๋ณ์ฑ ์ต๋ํ max rank(A)์ฆ๋ช
: rank(A)๋ ๋จ์กฐ ์ฆ๊ฐ ๋ถ๋ถ๋ชจ๋ ํจ์์
๋๋ค์ค์ : N๊ฐ์ ์ด๋ ์์ด์ ํธ๊ฐ |V|๊ฐ์ ์ง๋ฆฌ์ ๋
ธ๋ ๋ชจ๋ํฐ๋ง๋ณด์ ํจ์ : Rv(t) = ฯv(t - tฬv)์ ์ฝ : ๋ถํ ๋งคํธ๋ก์ด๋, ๊ฐ ์์ด์ ํธ๋ ์ต๋ ํ๋์ ์ ๋ต ์ ํ๋จ์กฐ์ฑ ํ์ฉ : f(S*) โค f(S* โช Si)๋ง์๊ธ ํฉ : f(S*) = f(Si) + ฮฃ ฮf(sj|Si โช {s 1,...,s*j-1})๋ถ๋ถ๋ชจ๋์ฑ ์ ์ฉ : ฮf(sj|Si โช {s 1,...,sj-1}) โค ฮf(s j|Si)ํ์ ์ ํ : ฮf(s*j|Si) โค f(Si+1) - f(Si)ํ์ค ๋ณด์ฅ : 1 - 1/e โ 0.632๊ณก๋ฅ ์ ๋ฐํ : (1/c)(1 - 1/e^c)๋ชจ๋ ํจ์์ ๊ฒฝ์ฐ : c = 0์ผ ๋ ์ต์ ํด ๋ฌ์ฑํ์ค ๋ณด์ฅ : 1/2๊ณก๋ฅ ์ ๋ฐํ : 1/(1+c)์์ ๋ฌด๊ด์ฑ : ๊ทผ์ฌ๋น๋ ์ฒ๋ฆฌ ์์์ ๋ฌด๊ดํฉ๋๋ค์ด๋ก ์ ์ํ : 1 - 1/e (๊ท ๋ฑ ๋งคํธ๋ก์ด๋์ ๋์ผ)์ค์ ์ฑ๋ฅ : 1 - 1/e - O(1/T), ํ๋ฅ 1 - 2Tne^(-1/8TยฒK)ํด๋ฐํด ๊ฒฝ๋ก ์กด์ฌ : ์ต์ ํต์ ํจ์จ๋นํด๋ฐํด ๊ฒฝ์ฐ : ์ผ๋ถ ์์ด์ ํธ์ ๋ฐ๋ณต ๋ฐฉ๋ฌธ ํ์์ ๋ณด ๊ณต์ ๊ทธ๋ํ : ๊ทผ์ฌ๋น 1/(2+n-W(GI)), ์ฌ๊ธฐ์ W(GI)๋ ํด๋ฆฌํฌ ์ํต์ ์คํจ ํ๋ฅ ๊ณ ๋ ค ํ๋ฅ ์ ๊ทผ์ฌ๋น ๋ณด์ฅ ์ ๊ณต ์์ ์ ์ฝ ํ๊ฒฝ์์์ ํต์ ์ ๋ต ์ง๋ 1970๋
๋ : Nemhauser, Wolsey ๋ฐ Fisher์ ๊ฐ์ฒ ์ฐ๊ตฌ๊ณ ์ ์ ๊ฒฐ๊ณผ : ๋ถ๋ถ๋ชจ๋ ์ต๋ํ์ 1-1/e ๊ทผ์ฌ๋น๋งคํธ๋ก์ด๋ ์ด๋ก : ๋
๋ฆฝ์ฑ ์์คํ
๋ฐ ์ฆ๊ฐ ์ฑ์ง๊ณ์ฐ ํจ์จ์ฑ : ๊ฒ์ผ๋ฅธ ํ๊ฐ ์ ๋ต๋ถ์ฐ ์๊ณ ๋ฆฌ์ฆ : MapReduce ํ๋ ์์ํฌ ์ ์ฉ๊ฐ์ธ์ ๋ณด ๋ณดํธ : ์ฐจ๋ถ ๊ฐ์ธ์ ๋ณด ๋ณดํธ ๋ฐ ๋ฌด์์ ๋ฐ์ฌ๋ฆผ์จ๋ผ์ธ ์ต์ ํ : ์คํธ๋ฆฌ๋ฐ ๋ฐ ์ ์ํ ์๊ณ ๋ฆฌ์ฆ์ฝํ ๋ถ๋ถ๋ชจ๋์ฑ : ๋น๋ก ๋ถ๋ถ๋ชจ๋์ฑk-๋ถ๋ถ๋ชจ๋์ฑ : ๋ค์ค ์ํ ์์ฌ๊ฒฐ์ ์ฌ์ธต ๋ถ๋ถ๋ชจ๋ ํจ์ : ์ ๊ฒฝ๋ง ๊ฒฐํฉ๊ณต์ ์ฑ : ์ต์ ํ์ ๊ณต์ ์ฑ ๊ณ ๋ ค์ด๋ก ์ ์์ ์ฑ : ๊ท ๋ฑ ๋ฐ ๋ถํ ๋งคํธ๋ก์ด๋ ์ ์ฝ ํ์ ๋ถ๋ถ๋ชจ๋ ์ต๋ํ์ ๋ํ ์์ ํ ์ด๋ก ์ ํ๋ ์์ํฌ ์ ๊ณต์๊ณ ๋ฆฌ์ฆ ํจ์จ์ฑ : ์์ฐจ ํ์ ๋ฐ ์ฐ์ ํ์ ์๊ณ ๋ฆฌ์ฆ์ ๋ค์ํ ์๋๋ฆฌ์ค์์์ ์ ์ฉ์ฑ๋ถ์ฐ ๊ฐ๋ฅ์ฑ : ์ ์ ํ ํต์ ํ๋กํ ์ฝ์ ํตํด ํจ์จ์ ์ธ ๋ถ์ฐ ์๋ฃจ์
๊ตฌํ ๊ฐ๋ฅ๊ด๋ฒ์ํ ์ค์ ์์ฉ : ์ผ์ ๋คํธ์ํฌ์์ ๋ก๋ด ์กฐ์จ๊น์ง ์ฌ๋ฌ ๋ถ์ผ์ ์ฑ๊ณต์ ์์ฉNP-hard ๋ณธ์ง : 1-1/e์ ์ด๋ก ์ ์ํ์ ๋ํํ ์ ์์ํต์ ์ค๋ฒํค๋ : ๋ถ์ฐ ๊ตฌํ์ ํต์ ๋ณต์ก์ฑ๊ณก๋ฅ ์ถ์ : ์ค์ ์์ฉ์์ ์ด ๊ณก๋ฅ ์ ์ ํํ ๊ณ์ฐ ์ด๋ ค์ํ์ฅ์ฑ : ๋๊ท๋ชจ ๋ฌธ์ ์ ๊ณ์ฐ ํจ์จ์ฑ ๊ฐ์ ํ์์ฌ์ธต ๋ถ๋ถ๋ชจ๋ ํจ์ : ์ฌ์ธต ํ์ต๊ณผ ๊ฒฐํฉํ ๋ถ๋ถ๋ชจ๋ ์ต์ ํ์จ๋ผ์ธ ๋ฐ ์คํธ๋ฆฌ๋ฐ ์๊ณ ๋ฆฌ์ฆ : ๋์ ํ๊ฒฝ์์์ ์ค์๊ฐ ์ต์ ํ๊ณต์ ์ฑ ์ต์ ํ : ๋ถ๋ถ๋ชจ๋ ์ต๋ํ์ ๊ณต์ ์ฑ ์ ์ฝ ๋์
์ ์ํ ์๊ณ ๋ฆฌ์ฆ : ํผ๋๋ฐฑ์ ๋ฐ๋ผ ์กฐ์ ํ๋ ์ ์ํ ์ต์ ํ ์ ๋ต์ฒด๊ณ์ฑ : ๋ถ๋ถ๋ชจ๋ ์ต๋ํ์ ์ด๋ก ์ ๊ธฐ์ด, ์๊ณ ๋ฆฌ์ฆ ์ค๊ณ ๋ฐ ์ค์ ์์ฉ์ ํฌ๊ด์ ์ผ๋ก ๋ค๋ฃธ์ด๋ก ์ ๊น์ด : ์๊ฒฉํ ์ํ์ ๋ถ์ ๋ฐ ์ฑ๋ฅ ๋ณด์ฅ ์ ๊ณต์ค์ฉ์ ๊ฐ์น : ํ๋ถํ ์์ฉ ์ฌ๋ก๋ฅผ ํตํด ์ด๋ก ์ ์ค์ ์๋ฏธ ์์ฐ์ ๋ง์ฑ : ๋ถ์ฐ ๋ฐ ๊ฐ์ธ์ ๋ณด ๋ณดํธ ๋ฑ ํ๋์ ๋์ ๊ณผ์ ๋
ผ์๋ช
ํํ ์์ฑ : ๋
ผ๋ฆฌ ๊ตฌ์กฐ๊ฐ ๋ช
ํํ๊ณ ์ํ์ ํํ์ด ์ ํํจ์๋ก์ด ์๊ณ ๋ฆฌ์ฆ ๋ถ์ฌ : ์ฃผ๋ก ์ข
ํฉ์ ์ฑ๊ฒฉ์ด๋ฉฐ ์์ ํ ์๋ก์ด ์๊ณ ๋ฆฌ์ฆ ์ ์ ์์์ ํ๋ ์คํ ๊ฒ์ฆ : ์ด๋ก ์ ๊ฒฐ๊ณผ๋ฅผ ๊ฒ์ฆํ๋ ๋๊ท๋ชจ ์์น ์คํ ๋ถ์กฑ๋ถ์ถฉ๋ถํ ๋น๊ต ๋ถ์ : ์๋ก ๋ค๋ฅธ ์๊ณ ๋ฆฌ์ฆ ๊ฐ์ ์์ธํ ์ฑ๋ฅ ๋น๊ต ๋ถ์กฑ๊ตฌํ ์ธ๋ถ์ฌํญ : ๋ถ์ฐ ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌ์ฒด์ ๊ตฌํ ์ธ๋ถ์ฌํญ ์ค๋ช
๋ถ์กฑ๊ต์ก์ ๊ฐ์น : ํด๋น ๋ถ์ผ ์ฐ๊ตฌ์์๊ฒ ์ฐ์ํ ์
๋ฌธ ๋ฐ ์ฐธ๊ณ ์๋ฃ ์ ๊ณต์ฐ๊ตฌ ์ง๋ : ํฅํ ์ฐ๊ตฌ์ ์ค์ํ ๋ฐฉํฅ ๋ช
ํํ ์ ์์์ฉ ํ๋ : ๋ ๋ง์ ๋ถ์ผ์์ ๋ถ๋ถ๋ชจ๋ ์ต์ ํ ๋ฐฉ๋ฒ ํ๋ ์ ์ฉ์ ๊ธฐ์ฌ์ด๋ก ์ ํต์ผ : ์ฐ์ฌ๋ ์ด๋ก ์ ๊ฒฐ๊ณผ๋ฅผ ํตํฉํ์ฌ ํต์ผ๋ ํ๋ ์์ํฌ ํ์ฑ์ผ์ ๋คํธ์ํฌ : ์ผ์ ๋ฐ ์ก์ถ์์ดํฐ์ ์ต์ ๋ฐฐ์น๋ฐ์ดํฐ ๊ณผํ : ๋๊ท๋ชจ ๋ฐ์ดํฐ์ ์์ฝ ๋ฐ ํน์ฑ ์ ํ๋ก๋ด ์์คํ
: ๋ค์ค ๋ก๋ด ์กฐ์จ ๋ฐ ์์
ํ ๋น๋คํธ์ํฌ ์ต์ ํ : ํต์ ๋คํธ์ํฌ์ ์์ ํ ๋น ๋ฐ ๋ผ์ฐํ
์ต์ ํ์ถ์ฒ ์์คํ
: ๋ค์ํ๋ ์ถ์ฒ ๋ฐ ์ฝํ
์ธ ์ ํ๋
ผ๋ฌธ์ ๊ณ ์ ์ ์ธ Nemhauser-Wolsey ์ด๋ก ์์ ์ต์ ์ฌ์ธต ๋ถ๋ถ๋ชจ๋ ํจ์ ์ฐ๊ตฌ์ ์ด๋ฅด๊ธฐ๊น์ง ๋ถ๋ถ๋ชจ๋ ์ต์ ํ์ ๊ธฐ์ด ์ฐ๊ตฌ, ๋งคํธ๋ก์ด๋ ์ด๋ก , ๋ถ์ฐ ์๊ณ ๋ฆฌ์ฆ ์ค๊ณ ๋ฑ ์ฌ๋ฌ ์ธก๋ฉด์ ํฌํจํ๋ 71๊ฐ์ ๊ณ ํ์ง ์ฐธ๊ณ ๋ฌธํ์ ํฌํจํ๊ณ ์์ผ๋ฉฐ, ๋
์์๊ฒ ํฌ๊ด์ ์ธ ๋ฌธํ ์ง๋๋ฅผ ์ ๊ณตํฉ๋๋ค.
์ข
ํฉ ํ๊ฐ : ๋ณธ ๋
ผ๋ฌธ์ ๋ถ๋ถ๋ชจ๋ ์ต๋ํ ๋ถ์ผ์ ์ค์ํ ์ด๋ก ๊ณผ ๋ฐฉ๋ฒ์ ์ฒด๊ณ์ ์ผ๋ก ์ ๋ฆฌํ ์ฐ์ํ ์ข
ํฉ ๋
ผ๋ฌธ์ด๋ฉฐ, ํนํ ๋งคํธ๋ก์ด๋ ์ ์ฝ ๋ฐ ๋ถ์ฐ ๊ตฌํ ์ธก๋ฉด์์ ์ฌ์ธต์ ๋ถ์์ ์ ๊ณตํฉ๋๋ค. ๋
ผ๋ฌธ์ ์ด๋ก ์ ์ผ๋ก ์๋ฐํ๊ณ ์์ฉ์ด ํ๋ถํ์ฌ ํด๋น ๋ถ์ผ์ ์ฐ๊ตฌ์์ ์ค๋ฌด์ ๋ชจ๋์๊ฒ ๋์ ์ฐธ๊ณ ๊ฐ์น๋ฅผ ๊ฐ์ต๋๋ค.