구사과

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분 이상 길게 정차한다. 창밖으로 미시시피 강이 쏟아지는 멋진 풍경의 역이었다. 밖에 나가서 더 좋은 사진을 찍고 싶었으나, 기차 밖으로 나가면 기차가 강을 가리고 있어서 (..

Day 2 Western Montana - Near Glacier National Park 6시 반 좀 넘어서 일어났다. 잠은 그런대로 잤지만, 썩 개운치는 못하게 일어났다. 창문을 열어보니.. 어제 오후와는 완전히 다른, 그림같은 설원 속에 있었다. (사진은 그림같이 않음에 양해를 부탁한다. 동영상으로 찍은 경우가 많아 그렇다) 아직 진짜는 시작도 안 했으니, 바로 아침을 먹으러 간다. 아침도 몇 가지 옵션을 선택할 수 있다. 나는 스크램블 에그로 골랐다. 아침을 같이 먹었던 대학생은 캐나다에 있는 집으로 가기 위해 기차를 탔다고 했다. 보통은 집에 갈때 6~7시간 정도 운전해서 가는데, 지금은 고속도로가 빙판이 되어 있을 것 같아서 기차로 간 후 역에서 부모님이 픽업해주시기로 했다고. 기차가 미국의 ..