구사과

Part 1. Uniform SamplingGiven an undirected unweighted graph $G = (V, E)$, A $(1 \pm \epsilon)$ cut sparsifier $H = (V, F, w)$ satisfies the following:$F \subseteq E$For all $\emptyset \subsetneq S \subsetneq V$ it holds that $\delta_w(H, S) \in [(1 - \epsilon)\delta_{\mathbf{1}}(G, S),(1 + \epsilon)\delta_{\mathbf{1}}(G, S)]$This is a sparsification that preserves the cuts. Compare this to the ..

Given an undirected unweighted graph $G = (V, E)$, A $(1 \pm \epsilon)$ cut sparsifier $H = (V, F, w)$ satisfies the following:$F \subseteq E$For all $\emptyset \subsetneq S \subsetneq V$ it holds that $\delta_w(H, S) \in [(1 - \epsilon)\delta_{\mathbf{1}}(G, S),(1 + \epsilon)\delta_{\mathbf{1}}(G, S)]$This is a sparsification that preserves the cuts. Compare this to the distance spanner, which ..

Day 3 Mississippi River 미네아폴리스 근처에서 일어났다. 전날과는 달리 잘 잤고, 상쾌하게 일어났다. 시애틀을 떠난 후 처음 보는 대도시였고, 여행이 끝나간다는 실감이 나게 했다. 아침은 전날 점심 식사를 같이 한 미네소타 할머니와 LA에서 오신 노부부 분들과 함께했다. 노부부 분들은 LA에서 시애틀, 시애틀에서 시카고, 시카고에서 뉴올리언즈로 가는 기차를 연달아 타시는 것 같았다. 태평양 연안과 미시시피 강을 종주하는 코스로, 기차로만 해도 일주일 정도가 걸리는 코스이다. 기차는 세인트 폴 - 미네아폴리스에서 30분 이상 길게 정차한다. 창밖으로 미시시피 강이 쏟아지는 멋진 풍경의 역이었다. 밖에 나가서 더 좋은 사진을 찍고 싶었으나, 기차 밖으로 나가면 기차가 강을 가리고 있어서 (..