Hi there 👋

Introduction An st-ordering (or bipolar odering) of a simple undirected graph is $G = (V, E)$ is a specific permutation $l$ of vertices, where any permutation $l$ induces a natural partial order on vertices $u < v \iff l(u) < l(v) \text{ and } uv \in E$. $l$ is called to be an st-ordering if and only if for a given pair of vertices $(s, t)$, $s$ (resp. $t$) is the unique minimal (resp....

Intro Definition. Given $n$ items labeled by $[n]$, and item $i$ has value $v_{i}$ and cost $c_{i}$, we define minimum knapsack problem as following optimization problem - integer programming in fact. $$ \begin{aligned} \text{minimize}\quad& \sum_{i} c_{i}x_{i} \\ \text{s.t.}\quad& \sum_{i} v_{i}x_{i} \ge D \\ & x_{i} \in \set{0, 1} \end{aligned} $$ where $D$ is given desire on value. We can devise a naive LP relaxation for this: $$ \begin{aligned} \text{minimize}\quad& \sum_{i} c_{i}x_{i}\\ \text{s....

크기가 $n \times n$인 실대칭행렬 $A = (a_{ij})$에 대해 $i \neq j \implies a_{ij} \le 0$을 만족하고, $A$의 모든 고윳값이 음이 아닌 실수이다. (positive-semidefinite) $n \ge 2$라고 할 때, 다음 물음에 답하여라. $\ker A = \set{v \in \mathbb{R}^{n} : v^{t}Av = 0}$ $[n] = \set{1, \cdots, n}$의 nonempty partition $I, J$에 대해, 항상 $a_{ij} < 0$인 $i \in I$, $j \in J$가 존재한다고 하자. 이 때, $\dim \ker A \le 1$임을 보여라....

Simplicial Complex에서 Alexander Duality는 다음과 같다. $ \tilde{H_{i}}(A) \simeq \tilde{H}^{n-i-1}(S^{n} \setminus A) $ 이 글에서는 그 Combinatorial Variant와 Björner & Tancer (2007)의 증명을 다룬다. 모든 set은 finite set이라고 가정한다. 또한, Alexnader Duality의 응용 등에 대해서는 다루지 않는다. 기본적으로 공부 도중에 기록을 위해 만든 post이기 때문에 내용이 추후 가감될 수 있다. Alexander Dual Vertex set $V$ 위에 정의된 Simplicial Complex $\Delta$ 에 대해, Alexander Dual $\Delta^{\ast}$는 같은 Vertex Set 위에서 다음과 같이 정의된다....

수직선상에 깃발 $N$개를 놓되, $i$번째 깃발은 $x_i$ 또는 $y_i$에 놓아야 한다. 이 때 깃발들 사이의 최소 거리의 최댓값을 구하는 문제이다. 문제 링크 Solution sketch 일단 파라메트릭 + 2-SAT을 해야 한다는 것 까지는 자명한 관찰이다. 즉, “가장 가까이 있는 깃발이 $d$ 이상 떨어져 있게 할 수 있는가?”에 관한 문제를 풀자. 그런데 2-SAT에 사용할 그래프 에지를 단순하게 만들면 $O(N^2)$개가 된다. Idea 1. 2-SAT Segment Tree 편의상 $x$좌표들을 정렬된 순서대로 $p_{1}, p_{2}, \cdots, $라 두자....