---
# System prepended metadata

title: Decision Problems
tags: [labnote_cover]

---

---
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}$ に直す

![](https://i.imgur.com/VBoCSJh.png)

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