---
tags: labnote_cover
---

# Decision Problems

## Set system

- $(U, \mathcal{G})$
- finite set $U$
- collection $\mathcal{G}$ of subsets of $U$

## Set-Cover

- Given a set system $(U, \mathcal{G})$ and a number $k$, can we cover $U$ with $k$ sets from $\mathcal{G}$?
- $l$-set cover means any $G\in\mathcal{G}$ satisfies $|G|\leq l$

## Maximum coverage

- Given a set system $(U,\mathcal{G})$, numbers $k$ and $t$, are there $k$ sets from $\mathcal{G}$ that together cover at least $t$ elements in $U$
- note: any set cover instance can be solved by the maximum coverage instance with $t=|U|$.

## メモ

- Decision ver. of Set Cover $(\mathcal{G}, [\![N]\!], k)$
- $k$個選んで$[\![N]\!]$をカバーできるか?
- Decision ver. of Maximum coverage $(\mathcal{G},[\![N]\!], k, t)$
- $k$個選んで$[\![N]\!]$のうち$t$個以上をカバーできるか?
- Decision ver. of PWC $(S, k, \tau)$
- $k$個選んでコスト$\tau$の輸送を達成できるか?

## 修正案

- 今までの$\mathtt{kSetCover}$ と読んでいたやつを $\mathtt{SetCover}$ に直す


- 今までの議論で，$k$以下を選んで (i.e., $|S|\leq k$) コスト$0$になる輸送をつくれたら，Set Coverが解けるとする