커버 문제

조합학이나 컴퓨터 과학에서 문제를 다루는 것은 어떤 조합 구조가 다른 것을 '커버'하는지, 아니면 그 구조가 그것을 하기 위해 얼마나 커야 하는지를 묻는 계산상의 문제들이다.문제를 다루는 것은 최소화하는 문제와 대개 선형 프로그램인데 이중 문제를 패킹 문제라고 한다.

커버 문제의 가장 두드러진 예는 타격 세트 문제와 동등한 세트 커버 문제와 그 특수한 경우, 꼭지점 커버 문제, 엣지 커버 문제 등이다.

덮개/포장-문제 쌍
커버 문제 포장문제 최소 세트 커버 최대세트패킹 최소 에지 커버 최대 일치 최소 꼭지점 커버 최대 독립 집합 빈 커버 빈패킹 폴리곤 피복 직사각형 패킹
v t

일반 선형 프로그래밍 공식

선형 프로그래밍의 맥락에서 어떤 선형 프로그램도 제약 행렬, 객관적 함수, 우측의 계수가 음이 아닌 경우 커버링 문제로 생각할 수 있다.^[1]보다 정확하게는 다음과 같은 일반 정수 선형 프로그램을 고려하십시오.

최소화하다	${\displaystyle \sum _{i=1}^{n}c_{i}x_{i}}}}}$
의 대상이 되다	${\displaystyle \sum _{i=1}^{n}a_{ji}x_{i}\geq b_{j}{\text{{}{}{}}}{}}}}{}j=1,\m}$
	${\displaystyle {}_{}\mathrm{x}}$ ${\displaystyle i_{}}$= ${\displaystyle 1}$,${\displaystyle \dots ,}$ ${\displaystyle n}$ ${\displaystyle x_{i}\geq 0}{{\text{{{}}, }$의 경우 x${\displaystyle {}_{}}$i$=1,\properties,n}$.

이러한 $정수{\displaystyle }$ ${\displaystyle {\mathrm{선형}}_{}}$ ${\displaystyle \mathrm{프로그램}}$은 ${\displaystyle {모든}_{}}$ i${\displaystyle }$= 1${\displaystyle }$, , ${\displaystyle n}$ , n , ${\displaystyle m}$ , ${\displaystyle i$$=1,\$$dots ,n}$에 ${\displaystyle \mathrm{대해}}$j${\displaystyle ,}$ ${\displaystyle {bj}_{}{}_{}}$ $c_{i}\geq$ 0$}$이(가) $1$이면 커버링 문제라 불린다$.$

직감:$n{\displaystyle }$ ${\displaystyle n}$개의$$ 개체 유형과 $i{\displaystyle }$ ${\displaystyle i}$ 유형의 각 개체에는 c ${\displaystyle i_{}}$ ${\$의 관련 비용이 있다고$$ 가정해 보십시오$.$$x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$라는 숫자는 우리가$$ $구입$한 i ${\displaystyle i}$ 유형의 개체 수를 나타낸다$$.제한조건 $A{\displaystyle }$ ${\displaystyle x\mathbf{}}$ ${\displaystyle \ge }$ ${\displaystyle b\mathbf{}}$ ${\$이(가) 충족되면$$ $x{\displaystyle \mathbf{}}$ ${\$가) 커버(결합 컨텍스트에 따라 적용되는 구조)라고 한다.마지막으로, 위의 정수 선형 프로그램에 대한 최적의 해결책은 최소 비용을 커버하는 것이다.

커버 문제의 종류

그래프 이론, 계산 기하학 등에는 다양한 종류의 커버 문제가 있다.범주:커버링 문제.

예를 들어, 페트리 네트의 경우, 커버링 문제는 주어진 표시에 대해 더 큰(또는 같은) 표시에 도달할 수 있는 네트의 실행이 존재하는 경우 질문으로 정의된다.더 큰 것은 여기서 모든 구성요소가 적어도 주어진 표시의 구성요소만큼 크고 적어도 하나는 적절하게 크다는 것을 의미한다.

무지개 커버 및 충돌 없는 커버

일부 커버링 문제에서 커버는 일부 추가 요건을 충족해야 한다.특히 무지개 덮개 문제에서 원래 물체는 각각 '색'을 가지며, 덮개에는 각 색깔의 물체가 정확히 하나(또는 많아야 하나) 들어 있어야 한다.무지개 덮개는 예를 들어 간격별로 점을 덮기 위해 연구되었다.^[2]

• 실선에는 n개 색상의 간격의 J 집합이 있고 실선에는 점의 P 집합이 있다.
• J의 부분집합 Q는 각 색상의 최대 한 구간을 포함하면 무지개 집합이라고 불린다.
• P의 각 지점이 Q의 한 구간 이상에 포함되는 경우 구간 J의 집합을 P의 커버라고 한다.
• 레인보우 커버 문제는 P의 커버인 레인보우 세트 Q를 찾는 문제다.

문제는 (선형 SAT로부터의 축소에 의한) NP-hard이다.

좀 더 일반적인 개념은 무분쟁 커버다.^[3]이 문제의 경우:

• m 물체의 집합 O가 있고, O에는 충돌그래프 G가_O 있다.
• O의 부분집합 Q는_O G에 독립적으로 설정된 경우, 즉 Q에 있는 두 개 물체가 G에_O 있는 가장자리로 연결되지 않는 경우 충돌 없는 Q라고 한다.
• 무지개 세트는 G가_O 불연속 파벌로 만들어지는 특수한 경우 각각의 파벌이 색깔을 나타내는 분쟁 없는 세트다.

분쟁 없는 세트 커버는 P. 바닉, 파놀란, 라만, 사흘로트, 사우라베의^[4] 커버인 O의 일부분을 찾는 문제로서 분쟁-그래프가 수목성을 제한한 특별한 경우에 대해 다음을 증명한다.

• 기하학적 커버 문제가 고정 매개변수 추적 가능(FPT)인 경우, 충돌 없는 기하학적 커버 문제는 FPT이다.
• 기하학적 덮개 문제가 r 근사치 알고리즘을 허용하는 경우, 충돌 없는 기하학적 덮개 문제는 FPT 시간에 유사한 근사치 알고리즘을 허용한다.

참조