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분 이상 길게 정차한다. 창밖으로 미시시피 강이 쏟아지는 멋진 풍경의 역이었다. 밖에 나가서 더 좋은 사진을 찍고 싶었으나, 기차 밖으로 나가면 기차가 강을 가리고 있어서 (..
Day 2 Western Montana - Near Glacier National Park 6시 반 좀 넘어서 일어났다. 잠은 그런대로 잤지만, 썩 개운치는 못하게 일어났다. 창문을 열어보니.. 어제 오후와는 완전히 다른, 그림같은 설원 속에 있었다. (사진은 그림같이 않음에 양해를 부탁한다. 동영상으로 찍은 경우가 많아 그렇다) 아직 진짜는 시작도 안 했으니, 바로 아침을 먹으러 간다. 아침도 몇 가지 옵션을 선택할 수 있다. 나는 스크램블 에그로 골랐다. 아침을 같이 먹었던 대학생은 캐나다에 있는 집으로 가기 위해 기차를 탔다고 했다. 보통은 집에 갈때 6~7시간 정도 운전해서 가는데, 지금은 고속도로가 빙판이 되어 있을 것 같아서 기차로 간 후 역에서 부모님이 픽업해주시기로 했다고. 기차가 미국의 ..
정말 갑작스럽지만, 저번 주 3주 전 6주 전 (...) 암트랙의 Empire Builder를 타본 후기를 써 보려고 한다. 3월 6일 ~ 3월 8일은 공휴일이 끼어 있는 주도 아니고 아무 일도 없는 시기지만, 과제가 없길래 2주 전쯤에 충동적으로 티켓을 구매했다. 보스턴 → 시애틀 비행기, Empire Builder, 시카고 호텔 1박, 시카고 → 보스턴 비행기 표를 끊고, 평소처럼 살다가 전날 최소한의 준비물만 챙겨 출발했다. Day 1 Seattle 4시 반 기상 후 Boston Logan에서 6시 50분 비행기를 타고 시애틀로 갔다. 비행 시간은 약 6시간 정도로, 시차 때문에 3시간이 당겨져서 도착 시간은 10시였다. 몇천 km를 넘어서 Pacific에 왔다는 실감은 그다지 들지 않았다. 날씨가..
Undirected graph $G = (V, E)$ 에 대해, $G$의 $t$-spanner $H = Spanner(G,t) = (V, E^\prime)$ 는 다음 성질을 만족한다: $E^\prime \subseteq E$ 모든 $u, v \in V$ 에 대해, $dist(H, u, v) \le dist(G, u, v) \times t$ $E^\prime$ 의 크기가 작음 즉, 최단 경로를 Approximate하게 보존하는 Sparsification이다. Equivalent하게, 다음과 같이 표현할 수도 있다. $E^\prime \subseteq E$ 모든 $(u, v) \in E$ 에 대해, $dist(H, u, v) \le dist(G, u, v) \times t$ $E^\prime$ 의 크기가 작..
Even-Shiloach Algorithm은 Unweighted directed graph $G = (V, E)$ 에 대해서 incremental / decremental SSSP를 빠르게 해결하는 알고리즘이다. Naive하게는 매번 BFS를 해서 $O(m^2)$ 시간에 해결할 수 있는데, 이 알고리즘을 사용하면 이를 $O(nm)$ 으로 최적화할 수 있다. $O(m^2)$ 에 비해서 엄청나게 효율적이진 않지만 분명히 nontrivial한 bound이고, 내가 아는 state-of-the-art method는 전부 다 Near-linear가 아니라 $O(nm)$ 에 훨씬 가까운 바운드이다. 그것도 복잡한 알고리즘들이 대다수. 이 글에서는 원래 Even-Shiloach Algorithm보다 강한 statem..
알고리즘 하시던 분들을 현실에서 만나게 되면 자주 듣는 질문이 "왜 ID가 구사과인가" 라는 질문이다. PS를 시작한 것은 고등학교 때지만 "컴덕후" 로 살던 초등학생 시절이 있었다. 2008년 집에서 새로 산 (보급형) 컴퓨터에 윈도우 비스타가 깔려 있었는데, 잘 알려졌다시피 비스타는 새 컴퓨터에서 돌리기에도 조금 많이 느렸다. 이 문제를 해결하기 위해 유출된 윈도우 7 비공개 베타를 주워서 설치했고, 신세계가 열렸다. 컴덕후 생활의 시작이었다. 시간이 지났고 그때 활동하던 커뮤니티에서 윈도우 8에 대한 이야기가 돌기 시작했다. "플랫 UI" 라는 미명하에 등장한 추태는 초등학생인 나에게 큰 상처를 남겼다. 이것이 미래라면 나는 도망치겠다고, 2달 동안 밥만 먹고 컴퓨터를 붙잡은 끝에 OS X Snow..
Example 1 (https://koosaga.com/319 마지막 단락) 그래프가 주어질 때 이 그래프의 maximal independent set 을 구하는 문제를 생각해 보자. maximal independent set은 maximum independent set을 approximate할 수 없다. 하지만 maximal matching과 $\Delta+1$ edge coloring을 구하는 데 사용할 수 있고 이들은 각각 그들의 optimal variant의 constant approximation이다. 다음 과정을 정점이 1개 이상일 때까지 반복하면 된다: 각 노드에 $[0, 1]$ 사이의 random real을 배정한다. 이를 $r(v)$ 라고 하자. 만약 어떠한 노드에 대해 $\max_{w ..
PA 2016. Shuffle 문제에서 주어진 셔플 연산은 카드 덱을 뒤집는 연산과 동일합니다. 이 사실은 수학적 귀납법으로 증명 가능합니다. $2$ 개의 카드에 대해서는 자명히 뒤집는 연산과 동일합니다. $2^k$ 개의 카드에 대해서는, 덱을 절반으로 나눈 후 각각을 뒤집고 둘의 순서를 바꾸는 것이니, 이 역시 뒤집는 연산과 동일합니다. 카드 덱을 두번 뒤집는 건 아무것도 안하는 것과 동일하니, $t$ 가 홀수일 때 배열을 뒤집은 후 출력해 주면 됩니다. ROI 2022 P5. Максимизация выигрыша 입력으로 주어진 문자열의 길이가 $19$ 이하일때만 문제를 해결할 수 있어도 됩니다. 만약 맨 앞 문자가 전체 문자열의 최댓값이 아닐 경우, 가장 가까운 최댓값을 맨 앞 문자로 옮깁니다. ..
- Total
- Today
- Yesterday