-
매트로이드에서의 Submodular Maximization에 대한 Deterministic algorithms
이 글에서는 매트로이드 상에서의 submodular maximization과 관련한 여러 연구의 결과들을 소개합니다. 보다 구체적으로는, 매트로이드와 submodular function 등 여러 개념의 정의를 소개하고, 매트로이드 상에서 submodular function을 최적화 하는 것이 실생활의 어떤 문제에 관련이 있는지 먼저 살펴봅니다. 그 후, 이 문제와 관련한 여러 연구 결과들을 살펴봅니다. 특히, 그 중에서도 (이 글에서는) 결정론적인 알고리즘들을 다룹니다. 1. 여러 개념 및 정의 먼저, submodular function 및 그에 대한 marginal gain을 정의합니다. 정의 1. 유한집합 $\mathcal{N}$에 대해 함수 $f : 2^\mathcal{N}...
-
Introduction to Matroid Union
Matroid Matroid에 대한 기본 지식은 다른 글을 참고하는 것이 좋다. 여기서는 Matroid의 정의만 짚고 넘어가자. 정의 1. 유한집합 $S$와 $S$의 부분집합족 $\mathcal{I}$에 대해 $M=(S, \mathcal{I})$가 아래 조건을 만족할 경우 $M$을 Matroid라고 한다. ${}\in\mathcal{I}$ (Empty set is Independent set) $B\subset A\in\mathcal{I}\Rightarrow B\in\mathcal{I}$ (hereditary property) $A, B\in\mathcal{I}, \mid A\mid>\mid B\mid\Rightarrow\exists x\in A\setminus B$ $s.t.$ $B+x\in\mathcal{I}$ (augmentation property) $S$의 부분집합이 $\mathcal{I}$에 포함될 경우 독립집합(Independent set)이라고 부른다. Matroid Union Matroid Union은 Matroid의 합집합으로, 다음과 같이 정의된다. 정의 2. Matroid...
-
Matroid Intersection
Matroid Intersection Recall matroid $\mathcal{M} = (S, \mathcal{I})$ 에서 $S$는 유한집합, $ \mathcal{I} \subset 2^S$ 는 독립집합(independent set)들의 collection이다. 이 때, $I$는 다음 세 가지 조건을 만족하여야 한다. $\phi \in \mathcal{I}$ $Y \subset X, X \in \mathcal{I} \Rightarrow Y \in \mathcal{I}$ $X, Y \in \mathcal{I}, \lvert X \rvert < \lvert Y \rvert$ 이면 $X + y \in \mathcal{I}$ 를 만족하는 $y \in Y \setminus X$가 존재 매트로이드는 다양한 집합에서 정의될 수 있다. 그 중 대표적인...
-
Introduction to matroid
Matroid 정의 1. matroid $\mathcal{M} = (S, \mathcal{I})$ 에서 $S$는 유한집합, $ \mathcal{I} \subset 2^S$ 는 독립집합(independent set)들의 collection이다. 이 때, $I$는 다음 세 가지 조건을 만족하여야 한다. $\phi \in \mathcal{I}$ $Y \subset X, X \in \mathcal{I} \Rightarrow Y \in \mathcal{I}$ $X, Y \in \mathcal{I}, \lvert X \rvert < \lvert Y \rvert$ 이면 $X + y \in \mathcal{I}$ 를 만족하는 $y \in Y \setminus X$가 존재 매트로이드는 다양한 집합에서 정의될 수 있다. 그 중 대표적인...