커버 설정 문제

세트 커버 문제는 조합론, 컴퓨터 과학, 연산 연구 및 복잡성 이론의 고전적인 질문입니다.1972년에 NP-완전한 것으로 판명된 Karp의 21개의 NP-완전한 문제 중 하나입니다.

${1,$ 2 $, \dots,$ $n}($ 우주라고 함)의 집합과 결합이 우주와 같은 m개의 $집합$ S가 주어진다면, 집합 커버 문제는 결합이 우주와 같은 S의 $최소$ 부분 집합을 식별하는 것이다.예를 들어, $우주$ U = {1 $, 2,$ 3, 4 $, 5}$ 및 $집합$ S $= {$ 1, 2 $, 3}, {2,$ 4 $},$ {3 $, 4},$ {4 $,$ $5$ }을 $($ 를) 생각해 보십시오.분명히 $S$ 의 합계는 $U$ 입니다. 그러나 다음과 같은 더 적은 수의 집합으로 모든 요소를 커버할 수 있습니다. { $1, 2,$ $3}, {4$ , 5 $}$ }.

좀 더 형식적으로 말하면, 우주 ${\mathcal {U}}$ ( $style)$ 와 U ${\mathcal {U}}$ $(style)$ 의 ${\mathcal {U}}$ 서브셋의 ${\mathcal {S}}$ S $(style)$ 가 ${\mathcal {S}}$ 주어졌을 때, 커버는 서브 ${\mathcal {C}}\subseteq {\mathcal {S}}$ C ${\mathcal {C}}\subseteq {\mathcal {S}}$ style $)$ 의 서브셋이며, U(style)의 $서브셋$ 은 U $($ style)의 서브셋 C( $style)$ 이다 ${\mathcal {C}}\subseteq {\mathcal {S}}$ $.$ $hcal {U$ 집합 커버링 결정 문제에서 입력은 \ $displaystyle($ $)$ {\ $mathcal$ {U $}}, {\mathcal$ {S $({\mathcal {U}},{\mathcal {S}})$ 과정수 k(\ $displaystyle$ k $k$ 입니다. $k$ 는 크기k{ $displaystyle$ k $}$ 이하의 $k$ 커버링이 있는지 여부입니다.세트 커버 최적화 문제에서 입력은 쌍 $({\mathcal {U}},{\mathcal {S}})$ , $({\mathcal {U}},{\mathcal {S}})$ ) { $displaystyle {\mathcal {U}},$ {\ $mathcal {S$ 이며, 작업은 가장 적은 세트를 사용하는 세트 커버를 찾는 것입니다.

세트 커버의 결정 버전은 NP-complete이고 세트 커버의 최적화/검색 버전은 NP-hard입니다.^[1]이는 근사 알고리즘의 "^[2]전체 분야에 대한 기본 기술의 개발을 누구의 연구로 이끌었는가" 문제이다.각 세트에 비용이 할당되면 가중치 세트 커버 문제가 됩니다.

정수 선형 프로그램 공식화

최소 세트 커버 문제는 다음과 같은 정수 선형 프로그램(ILP)^[3]으로 공식화할 수 있습니다.

최소화하다	$\displaystyle \sum _{s\in\mathcal {S}}x_{s}$		(세트 수 증가)
의 영향을 받는.	$\displaystyle \sum _{s\in s}x_{s}\geqslant 1$	$e\in {\mathcal {U}}$ e ${\$ U \ $display style$ e \ $in$ \ $mathcal$ { $U$ } } 。	(우주의 모든 요소를 덮는다)
	$x_{s}\in\{0,1\}$	모든 $(\$ s $\in\mathcal {S$ 에 적용됩니다.	(모든 세트가 세트커버에 있는지 여부에 관계없이)

이 ILP는 문제를 커버하기 위한 보다 일반적인 ILP 클래스에 속합니다.이 ILP의 통합성 격차는 최대 $(\$ $\scriptstyle \log$ $\scriptstyle \log n$ n $)$ 이므로 이 완화는 최소 세트 커버 문제에 대한 근사 알고리즘 $\scriptstyle \log n$ $nn($ $\scriptstyle n$ 서 $\scriptstyle n$ n\ $displaystyle \scriptstyle$ \ $log$ n은 $\scriptstyle n$ 우주의 ^[4]크기)을 제공합니다.

가중치 세트 커버에서는 세트에 가중치가 할당됩니다. $s\in {\mathcal {S}}$ S ( \ $displaystyle$ s \ $in$ \ $mathcal$ { $S$ } )의 $s\in {\mathcal {S}}$ 무게를 $w_{s}$ s $w_{s}$ ( \ $displaystyle w$ _ { $s$ } )로 나타냅니다.다음으로 가중치 세트커버를 설명하는 정수 선형 프로그램은 위의 프로그램과 동일합니다.단, 최소화하는 목적 함수는 s $\sum _{s\in {\mathcal {S}}}w_{s}x_{s}$ $\sum _{s\in {\mathcal {S}}}w_{s}x_{s}$ \ $sum _{$ s\ $in$ \ $mathcal {S} w_{s}x_{s$ 입니다.

히트 세트 공식

세트 커버는 히트 세트 문제와 동일합니다.이는 집합 피복의 인스턴스가 왼쪽의 정점으로 표현되고 오른쪽의 정점으로 표현되며, 가장자리가 집합에 포함된 요소를 나타내는 임의의 초당 그래프로 볼 수 있다는 것을 관찰함으로써 알 수 있다.다음으로 작업은 모든 왼쪽 수직을 커버하는 오른쪽 수직의 최소 카디널리티 서브셋을 찾는 것입니다.이것은 정확히 히트 세트 문제입니다.

탐욕 알고리즘

하나의 규칙에 따라 집합을 선택하는 집합 커버의 다항식 시간 근사 알고리즘이 있습니다. 각 단계에서 가장 많은 수의 비포장 요소를 포함하는 집합을 선택하십시오.이 방법은 버킷 큐를 사용하여 세트의 우선순위를 ^[5]지정하여 입력 세트의 크기 합계에 시간 선형으로 구현할 수 있습니다.이 값은 H $H(s)$ ( $H(s)$ ) \ $displaystyle$ H ( $H(s)$ s $H(s)$ 의 $H(s)$ 비율을 달성합니다. $s$ 서s \ $displaystyle$ s는 $s$ ^[6]커버할 세트의 크기입니다.즉, 최소값보다 H $)\displaystyle$ H $($ $n$ $H(n)$ $H(n)$ 큰 커버가 $H(n)$ 됩니다 $.$ 서 H(n)\ $displaystyle$ H(n $)$ 는 $H(n)$ n\ $displaystyle$ n}번째 고조파수입니다.

H(n)=\sum _{k=1}^{n}{\frac {1}{k}\leq \ln {n}+1

이 그리디 알고리즘은 실제로 $H(s^{\prime })$ H ( $H(s^{\prime })$ $H(s^{\prime })$ ) ( \ $displaystyle H$ ( $s$ $H(s^{\prime })$ ^ { \ prime $H(s^{\prime })$ } )의 $H(s^{\prime })$ 근사비를 실현합니다. $s^{\prime }$ 서 s ${\$ \ $displaystyle$ s ^ { \ prime $s^{\prime }$ }는 S ${$ \ $displaystyle$ S $S$ }의 $s^{\prime }$ 최대 카디널리티 세트입니다. $\delta -$ \ $displaystyle$ \ $delta$ - { \ delta - $\delta -$ $c\ln {m}$ 의 $\delta -$ 경우 cln $\$ $displaystyle$ $c\ln {m}$ \ $ln$ \ln\ln\ $displaystyle$ c $.$ { $m}:$ $c>0$ c $c>0$ > $c>0$ { $displaystyle$ c > $0$ ^[7]의 근사 $c\ln {m}$ 알고리즘 $.$

k=3인 탐욕 알고리즘에 대한 엄격한 예

탐욕 알고리즘이 $\log _{2}(n)/2$ 2 $\log _{2}(n)/2$ ( $\log _{2}(n)/2$ n ) / $\log _{2}(n)/2$ ( \ $displaystyle$ \ $log _$ {2 $}$ ( n ) / $2$ )의 근사 비율을 달성하는 표준적인 예가 있습니다. 우주는 $n=2^{(k+1)}-2$ $n=2^{(k+1)}-2$ $n=2^{(k+1)}-2$ ( k $n=2^{(k+1)}-2$ + 1) $n=2^{(k+1)}-2$ - $n=2^{(k+1)}-2$ ( \ $display$ n $n=2^{(k+1)}-2$ = 2 ^ { ( k + 1) }-2 $}$ 의 $n=2^{(k+1)}-2$ 요소로 $구성$ 됩니다.세트 시스템은 각각 $2,4,8,\ldots ,2^{k}$ 2, $2,4,8,\ldots ,2^{k}$ , $2,4,8,\ldots ,2^{k}$ , $($ $2$ , $4, 8$ , \ $ldots,$ 2k( $디스플레이 스타일$ 2, 4, 8, \ $ldots, 2^{k})$ 의 $2,4,8,\ldots ,2^{k}$ 쌍으로 $k$ 된 분리 $S_{1},\ldots ,S_{k}$ S1 $S_{1},\ldots ,S_{k}$ $2,4,8,\ldots ,2^{k}$ $S_{$ k $S_{1},\ldots ,S_{k}$ } 및 2개의 추가 $T_{0},T_{1}$ $T_{0},T_{1}$ $T_style,$ …로 $T_{0},T_{1}$ 됩니다.각 $(\$ 의 요소의 절반을 포함합니다. $S_{k},\ldots ,S_{1}$ 입력에서는 Gready 알고리즘은 $S_{k},\ldots ,S_{1}$ $S_{k},\ldots ,S_{1}$ k $S_{k},\ldots ,S_{1}$ …, $S_{k},\ldots ,S_{1}$ (\ $displaystyle S_{k},\ldots, S_{1$ $})$ 을 $T_{0}$ 순서대로 취합니다.최적의 솔루션은 $T_{0}$ 0(\ $displaystyle T_0$ $T_{1}$ $T_1$ 로 구성되어 $있습니다$ .오른쪽에는 k $k=3$ $(\style$ k= $3)$ 에 $k=3$ $k=3$ 입력이 나와 있습니다.

비근접성 결과는 그리디 알고리즘이 본질적으로 가능한 가장 좋은 다항식 시간 근사 알고리즘이라는 것을 보여줍니다(아래의 비근접성 결과 참조).탐욕 알고리즘의 상세한 분석 결과 근사비는 정확히 $\ln {n}-\ln {\ln {n}}+\Theta (1)$ - $\ln {n}-\ln {\ln {n}}+\Theta (1)$ n $\ln {n}-\ln {\ln {n}}+\Theta (1)$ ( $\ln {n}-\ln {\ln {n}}+\Theta (1)$ $displaystyle \ln {n}-\ln {n}+\$ 입니다. $Theta (1$ ^[8] 입니다.

저주파 시스템

각 요소가 최대로 발생하는 경우f집합, 그러면 해답은 다항식 시간에 발견될 수 있으며, 이는 다음의 요인 내에서 최적에 근접한다.fLP 릴렉스 사용.

$x_{S}\in \{0,1\}$ $x_{S}\in \{0,1\}$ S $x_{S}\in \{0,1\}$ { $x_{S}\in \{0,1\}$ , $}$ { $displaystyle$ x $_$ $x_{S}\geq 0$ { $S$ $x_{S}\geq 0$ } \ $in$ \ { $x_{S}\in \{0,1\}$ $0$ , $1$ \ }이 $x_{S}\in \{0,1\}$ (가) $x_{S}\geq 0$ $S$ 0 $x_{S}\geq 0$ ( $x_{S}\geq 0$ )으로 $x_{S}\geq 0$ 대체된 경우S위의 정수 선형 프로그램에서 S $(\displaystyle\mathcal$ {S $})$ 를 ${\mathcal {S}}$ ${\mathcal {S}}$ 하면 (비정수) 선형 프로그램이 됩니다.L알고리즘은 다음과 같이 설명할 수 있습니다.

최적의 솔루션 찾기O프로그램용L선형 프로그램을 푸는 다항식 시간 방법을 사용합니다.
모든 세트 선택S대응하는 변수가x_S 최소 1/의 값을 가져야 합니다.f해결 중에O를 클릭합니다.^[9]

프록시머빌리티 결과

n $({$ $displaystyle$ n $n$ })이 우주의 ${\tfrac {1}{2}}\log _{2}{n}\approx 0.72\ln {n}$ 를 ${\tfrac {1}{2}}\log _{2}{n}\approx 0.72\ln {n}$ 경우, Lund & Yannakakis(1994)는 { $n},$ {n}, {n}, {n $},$ { $n},$ {n}, {n $},$ { $n},$ {n}, {n}, {n ${\tfrac {1}{2}}\log _{2}{n}\approx 0.72\ln {n}$ {n $},$ { $n},$ n, n $,$ {n}, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n ${\tfrac {1}{2}}\log _{2}{n}\approx 0.72\ln {n}$ n, n, n, n, n, ${\tfrac {1}{2}}\log _{2}{n}\approx 0.72\ln {n}$ , ${\tfrac {1}{2}}\log _{2}{n}\approx 0.72\ln {n}$ , n, n,Feige(1998)는 이 하한을 ( ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ - ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ ( ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ 1) ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ l ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ n { $displaystyle ($ ) 1 - o ( 1 ) { \ $bigr$ } \ $cdot \ ln$ { $n$ 으로 ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ 개선하였으며, 이는 기본적으로 탐욕 알고리즘에 의해 달성된 근사 비율과 일치한다.Raz & Safra(1997)는 P ${\$ ${\displaystyle$ \n $\not =$ $\not =$ $c\cdot \ln {n}$ NP라는 보다 약한 가정 $c$ 에c {\ $displaystyle$ c $}$ 의 $c$ 하한을 설정했다.최근 Alon, Moshkovitz 및 Safra(2006)에 의해 더 높은c(\ $displaystyle$ c $)$ 의 유사한 결과가 입증되었다.Dinur & Steurer(2013)는 P $=$ {\ $displaystyle$ ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ =} NP가 $=$ 아닌 ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ $1$ - ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ (1) ${\bigr}\cdot \n}$ 에 ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ 근사할 수 없음을 입증하여 최적의 비직접성을 보였다.

무게 세트 커버

위에 언급된 가중치 세트 커버에 대한 정수 선형 프로그램을 완화하면 랜덤 반올림을 사용하여 O $O(\log n)$ n $)\displaystyle$ O $(\log$ n $)}$ - 계수 $O(\log n)$ 근사치를 $O(\log n)$ 수 있습니다.비중량 세트 커버는 가중치 ^[10]적용 사례에 적합할 수 있다.

메모들

^ Korte & Vygen 2012, 페이지 414
^ Vazirani (2001, 페이지 15)
^ Vazirani (2001, 페이지 108)
^ Vazirani (2001, 페이지 110–112)
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990], "Exercise 35.3-3", Introduction to Algorithms (3rd ed.), MIT Press and McGraw-Hill, p. 1122, ISBN 0-262-03384-4
^ Chvatal, V. 세트커버링 문제에 대한 탐욕적 휴리스틱.연산수학연구 제4권 제3호(1979년 8월), 233-235페이지
^ 카르핀스키 & 젤리코프스키 1998
^ 슬라빅 페트르 세트 커버에 대한 탐욕스러운 알고리즘의 정밀 분석.STOC'96, 435-441, doi:10.114/237814.237991
^ 바지라니 (2001, 페이지 118–119)
^ Vazirani (2001년, 제14장)
^ Information., Sandia National Laboratories. United States. Department of Energy. United States. Department of Energy. Office of Scientific and Technical (1999). On the Red-Blue Set Cover Problem. United States. Dept. of Energy. OCLC 68396743.

레퍼런스

를 클릭합니다Alon, Noga; Moshkovitz, Dana; Safra, Shmuel (2006), "Algorithmic construction of sets for k-restrictions", ACM Trans. Algorithms, 2 (2): 153–177, CiteSeerX 10.1.1.138.8682, doi:10.1145/1150334.1150336, ISSN 1549-6325, S2CID 11922650.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms, Cambridge, Mass.: MIT Press and McGraw-Hill, pp. 1033–1038, ISBN 978-0-262-03293-3
를 클릭합니다Feige, Uriel (1998), "A threshold of ln n for approximating set cover", Journal of the ACM, 45 (4): 634–652, CiteSeerX 10.1.1.70.5014, doi:10.1145/285055.285059, ISSN 0004-5411, S2CID 52827488.
Karpinski, Marek; Zelikovsky, Alexander (1998), "Approximating dense cases of covering problems", Proceedings of the DIMACS Workshop on Network Design: Connectivity and Facilities Location, vol. 40, pp. 169–178, ISBN 9780821870846
를 클릭합니다Lund, Carsten; Yannakakis, Mihalis (1994), "On the hardness of approximating minimization problems", Journal of the ACM, 41 (5): 960–981, doi:10.1145/185675.306789, ISSN 0004-5411, S2CID 9021065.
를 클릭합니다Raz, Ran; Safra, Shmuel (1997), "A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP", STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, ACM, pp. 475–484, ISBN 978-0-89791-888-6.
를 클릭합니다Dinur, Irit; Steurer, David (2013), "Analytical approach to parallel repetition", STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing, ACM, pp. 624–633.
Vazirani, Vijay V. (2001), Approximation Algorithms (PDF), Springer-Verlag, ISBN 978-3-540-65367-7
Korte, Bernhard; Vygen, Jens (2012), Combinatorial Optimization: Theory and Algorithms (5 ed.), Springer, ISBN 978-3-642-24487-2
Cardoso, Nuno; Abreu, Rui (2014), "An Efficient Distributed Algorithm for Computing Minimal Hitting Sets" (PDF), Proceedings of the 25th International Workshop on Principles of Diagnosis, Graz, Austria, doi:10.5281/zenodo.10037

외부 링크

[FOOTNOTEKorteVygen2012414-1] Korte & Vygen 2012, 페이지 414

[2] Vazirani (2001, 페이지 15)

[3] Vazirani (2001, 페이지 108)

[4] Vazirani (2001, 페이지 110–112)

[5] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990], "Exercise 35.3-3", Introduction to Algorithms (3rd ed.), MIT Press and McGraw-Hill, p. 1122, ISBN 0-262-03384-4

[6] Chvatal, V. 세트커버링 문제에 대한 탐욕적 휴리스틱.연산수학연구 제4권 제3호(1979년 8월), 233-235페이지

[7] 카르핀스키 & 젤리코프스키 1998

[8] 슬라빅 페트르 세트 커버에 대한 탐욕스러운 알고리즘의 정밀 분석.STOC'96, 435-441, doi:10.114/237814.237991

[9] 바지라니 (2001, 페이지 118–119)

[10] Vazirani (2001년, 제14장)

[11] Information., Sandia National Laboratories. United States. Department of Energy. United States. Department of Energy. Office of Scientific and Technical (1999). On the Red-Blue Set Cover Problem. United States. Dept. of Energy. OCLC 68396743.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Search