ETH 취리히 연구진, 최속 흐름 알고리듬 개발

 (ethz.ch)
1P by GN⁺ | ★ favorite | 댓글 1개
  • ETH Zurich의 Rasmus Kyng 연구팀은 네트워크에서 최대 흐름을 찾고 운송 비용을 최소화하는 문제를 거의 수학적 한계 속도로 계산하는 알고리듬을 개발함
  • 새 알고리듬은 네트워크 데이터를 읽는 시간과 거의 같은 규모로 답을 내는 거의 선형 시간 접근이며, 철도·도로·수로·인터넷 같은 네트워크 계산에 적용될 수 있음
  • 과거에는 연결 수를 m이라 할 때 2000년 전까지 m^1.5, 2004년 m^1.33 수준이었지만, Kyng의 접근은 데이터 읽기 이후의 추가 계산 시간을 무시할 수 있는 수준으로 낮춤
  • 연구팀은 정적·방향성 네트워크를 넘어 연결이 추가되는 증분 그래프와 삭제되는 감소 그래프에서도 최단 경로와 최소비용 최대흐름을 거의 선형 시간에 계산함
  • Gotthard Base Tunnel 폐쇄·부분 재개통, A13 고속도로 산사태처럼 실제 네트워크가 바뀌는 상황에서 최적 경로를 빠르게 다시 계산하는 기반이 됨

네트워크 흐름 문제를 거의 한계 속도로 계산

  • Rasmus Kyng 연구팀의 네트워크 흐름 알고리듬은 네트워크에서 가능한 최대 흐름을 찾으면서 운송 비용을 최소화하는 문제를 다룸
  • Copenhagen에서 Milan까지 가능한 한 많은 물자를 가장 빠르고 저렴하게 옮기는 경로를 찾는 상황이 대표 예시임
  • 철도, 도로, 수로, 인터넷처럼 연결과 용량이 있는 네트워크에서 최적의 저비용 흐름을 계산할 수 있음
  • 계산 속도는 컴퓨터가 네트워크 데이터를 읽는 시간과 거의 같은 수준까지 줄어듦

왜 “가장 빠른” 알고리듬인가

  • 이전에는 최적 흐름을 계산하는 시간이 네트워크 데이터를 처리하는 시간보다 훨씬 길었음
  • 네트워크가 커지고 복잡해질수록 필요한 계산 시간은 문제 크기보다 더 빠르게 늘어났음
  • Kyng의 접근은 계산 시간과 네트워크 크기가 같은 비율로 증가하도록 만듦
    • 네트워크 연결 수를 m이라 하면 데이터를 한 번 읽는 데만 m 시간이 걸림
    • 2000년 전까지는 m^1.5보다 빠르게 계산하는 알고리듬이 없었음
    • 2004년에는 문제 풀이에 필요한 계산량이 m^1.33까지 줄어듦
    • Kyng 알고리듬은 데이터를 읽은 뒤 해답에 도달하기 위한 추가 계산 시간을 무시할 수 있는 수준으로 낮춤

거의 선형 시간 알고리듬의 평가와 확장

  • Kyng 연구팀은 2년 전 이 개념의 수학적 증명을 담은 논문을 발표함
  • 이처럼 거의 최적으로 빠른 알고리듬은 거의 선형 시간 알고리듬으로 불림
  • Daniel A. Spielman은 이 알고리듬을 마차를 추월하는 Porsche에 비유함
  • 해당 논문은 2022년 IEEE Annual Symposium on Foundations of Computer Science, FOCS에서 Best Paper Award를 받음
  • Communications of the ACM도 이 연구를 조명했고, Quanta 편집진은 Kyng 알고리듬을 2022년 컴퓨터 과학의 10대 발견 중 하나로 선정함

정적 네트워크에서 변화하는 네트워크로

  • 초기 알고리듬은 연결 방향이 정해진 고정·정적 네트워크에 초점을 맞췄음
    • 방향성 연결은 도시 도로망의 일방통행과 같은 구조임
  • 이후 연구팀은 시간이 지나며 점진적으로 변하는 네트워크에서도 최적 흐름을 계산하는 알고리듬을 개발함
  • Simon Meierhans는 Vancouver에서 열린 Annual ACM Symposium on Theory of Computing, STOC에서 새 거의 선형 시간 알고리듬을 발표함
    • 이 알고리듬은 새 연결이 추가되는 네트워크의 최소비용 최대흐름 문제를 풂
  • 10월 IEEE Symposium on Foundations of Computer Science, FOCS에 채택된 두 번째 논문에서는 연결 삭제도 처리하는 알고리듬을 개발함
  • 두 알고리듬은 연결이 추가되거나 삭제되는 네트워크에서 최단 경로를 식별함

실제 네트워크 변화의 예

  • Switzerland의 Gotthard Base Tunnel은 2023년 여름 이후 완전 폐쇄됐다가 부분 재개통됨
  • Gotthard Road Tunnel의 주요 대체 경로인 A13 고속도로 일부는 최근 산사태로 파괴됨
  • 이런 변화가 생기면 컴퓨터, 온라인 지도 서비스, 경로 계획기는 Milan과 Copenhagen 사이의 최저 비용·최단 연결을 다시 계산해야 함
  • Kyng의 새 알고리듬은 연결 추가나 삭제가 있는 네트워크에서도 거의 선형 시간으로 최적 경로를 계산함
  • 우회로나 새 경로가 생겨 연결이 추가될 때도 추가 계산 시간은 무시할 수 있는 수준임

기존 두 전략과 새 결합 방식

  • 네트워크 흐름 계산은 최적 흐름과 최소 비용 경로를 찾기 위해 여러 번 네트워크를 분석해야 함
  • 각 반복에서는 어떤 연결이 열려 있는지, 닫혀 있는지, 용량 한계에 도달해 혼잡한지 같은 변형을 검토함
  • Kyng 이전의 컴퓨터 과학자들은 주로 두 전략 중 하나를 사용함
    • 철도망 모델: 각 반복에서 트래픽 흐름이 바뀐 네트워크의 한 구간 전체를 계산함
    • 전력망 모델: 각 반복에서 네트워크 전체를 계산하되, 각 구간의 변경된 흐름에 통계적 평균값을 사용해 계산을 빠르게 함
  • Kyng 연구팀은 두 전략의 장점을 묶어 새로운 결합 접근을 만들었음
  • Maximilian Probst Gutenberg는 많은 작고 효율적이며 저비용인 계산 단계를 합치면 몇 개의 큰 단계보다 훨씬 빠르다고 봄

흐름 알고리듬의 역사적 맥락

  • 네트워크 흐름 문제는 1950년대에 알고리듬으로 체계적으로 풀린 초기 문제 중 하나였음
  • 흐름 알고리듬은 이론 컴퓨터 과학이 독립 연구 분야로 자리 잡는 데 중요한 역할을 함
  • Lester R. Ford Jr.와 Delbert R. Fulkerson의 잘 알려진 알고리듬도 이 시기에 나옴
  • Ford-Fulkerson 알고리듬은 각 경로의 용량을 넘지 않으면서 가능한 한 많은 물자를 네트워크로 운송하는 최대 흐름 문제를 효율적으로 풂
  • 이후 연구는 최대 흐름 문제, 최소 비용 문제, 여러 네트워크 흐름 문제가 일반적인 최소비용 흐름 문제의 특수 사례임을 보여줌

이전 알고리듬의 한계와 2004년 전환

  • Kyng 연구 이전의 많은 알고리듬은 특정 문제 하나를 효율적으로 풀 수 있었지만, 충분히 빠르지 않았고 더 넓은 최소비용 흐름 문제로 확장되기 어려웠음
  • 1970년대의 선구적 흐름 알고리듬을 만든 John Edward Hopcroft, Richard Manning Karp, Robert Endre Tarjan은 각각 Turing Award를 받음
    • Karp는 1985년에 수상함
    • Hopcroft와 Tarjan은 1986년에 수상함
  • 2004년에 Daniel Spielman, Shang-Hua Teng, 이후 Samuel Daitch는 최소비용 흐름 문제에도 빠르고 효율적인 해법을 제공하는 알고리듬을 작성함
  • 이 그룹은 관점을 철도에서 전력망의 전력 흐름으로 옮김
  • 전력망에서는 전류 흐름을 이미 다른 전류가 흐르는 연결로 부분적으로 우회시킬 수 있음
  • Kyng은 Spielman의 전체 네트워크용 강력한 알고리듬 접근을 그대로 따르지 않고, 부분 경로 계산 아이디어를 Hopcroft와 Karp의 이전 접근에 적용함
  • 각 반복에서 부분 경로를 계산한 점이 전체 흐름 계산을 빠르게 만드는 데 큰 역할을 함

새 수학 도구와 데이터 구조

  • ETH Zurich 연구팀의 진전은 새 알고리듬뿐 아니라 계산을 더 빠르게 하는 수학 도구 설계에도 기반함
  • 연구팀은 네트워크 데이터를 조직하는 새 데이터 구조를 개발함
  • 이 데이터 구조는 네트워크 연결의 변화를 매우 빠르게 식별할 수 있게 함
  • 빠른 변화 식별은 알고리듬 해법의 속도를 높이는 요소로 작동함
  • 거의 선형 시간 알고리듬과 새 데이터 구조는 이전에는 효율적으로 계산할 수 없던 매우 큰 문제를 풀기 위한 기반을 마련함

관련 논문과 자료

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 이 알고리즘은 n -> inf 한계에서 점근적으로 거의 선형임
    영상 끝에서는 이 알고리즘의 어떤 구현도 현실 세계에서 기존 알고리즘을 이기기 어렵다고 말함
    https://cacm.acm.org/research/almost-linear-time-algorithms-...

    • 그럼 또 하나의 은하 알고리즘인가?
      https://en.wikipedia.org/wiki/Galactic_algorithm
    • 앞부분에서 잔뜩 기대감을 키운 뒤라 꽤 김빠짐
    • 제목을 보자마자 매우 회의적이었음
      가장 빠른 가능 속도라는 표현은 정말 대담한 주장임
    • 이런 경우 또 다른 단서는 거의 절대 최적해가 필요하다는 점임
      시간의 1%만 써서 99% 품질을 내는 쪽이 훨씬 실용적인 경우가 많음

  • 흥미롭게도 같은 사람이 이론 전용 알고리즘을 실제로 잘 작동하게 만드는 연구도 함 [1]
    다만 그 과정에는 또 20년쯤 걸리는 듯함. [1]은 2004년의 이론적 돌파구 [2] 위에 쌓은 것이고, 내가 이해한 바로는 이런 알고리즘들이 2024년에야 실전에서 작동하기 시작했음. 그렇다면 실용적인 최소 비용 흐름 알고리즘은 2044년에 기대해볼 수 있겠음
    [1] https://arxiv.org/pdf/2303.00709
    [2] https://arxiv.org/abs/cs/0310051

  • Almost-Linear-Time Algorithm
    O(mn)에서 O(m)으로 간다는 건 계산에서 N, 즉 정점 수를 제외한다는 뜻인데, 너무 좋아서 믿기 어려운 수준 아닌가?

    • 상수 계수가 너무 커서, 실용적인 입력에서는 점근적으로 더 나쁜 기존 알고리즘보다 느릴 것임
      그래도 이론적으로는 멋진 결과임

  • 원시 수치만 봐도 우리가 얼마나 멀리 왔는지 알 수 있다. 2000년대 전까지는 어떤 알고리즘도 m1.5보다 빠르게 계산하지 못했다. 여기서 m은 컴퓨터가 계산해야 하는 네트워크 연결 수를 뜻하고, 네트워크 데이터를 한 번 읽는 데만 m 시간이 든다. 2004년에는 이 문제를 푸는 데 필요한 계산 속도가 m1.33으로 줄었다. Kyng의 알고리즘을 쓰면 네트워크 데이터를 읽은 뒤 해에 도달하는 데 필요한 “추가” 계산 시간이 이제 무시할 만하다.
    원문은 그렇게 중요하게 다루는 m 지표 관점에서 Kyng의 돌파구를 설명하지 않았는데, 왜 그런지 궁금함

  • 복잡도를 지표로 삼는 데서 완전히 길을 잃은 것 같을 때가 있음
    점점 복잡도 지표를 미친 수준으로 최적화했지만 실제로는 유용하지 않은 알고리즘이 늘고 있음

    • 그런 현상은 수십 년 전부터 있었음
      쉬운 성과가 다 사라진 뒤 알고리즘 연구는 또 하나의 고도로 전문화된 분야가 됐고, 아주 가까운 분야의 연구자가 아니라면 대부분의 논문은 시간을 들일 가치가 크지 않음

  • 관련 글: https://news.ycombinator.com/item?id=31149038 (댓글 40개)
    https://news.ycombinator.com/item?id=31675015 (댓글 72개)

  • 논문이나 코드는 어디에 있나?

  • 여기서 헷갈리는 부분이 있는데, o(n)이 O(n)보다 더 강한 명제처럼 보임
    모든 o(n) 알고리즘은 O(n)이지만 그 역은 참이 아니기 때문임. 또 o(n)은 아무리 작은 n에도 적용되고, O(n)은 n -> inf일 때만 적용된다면, 이 알고리즘은 작은 n에도 적용 가능해야 하는 것 아닌가? 그렇다면 위에서 말한 은하 알고리즘의 반대가 되어야 하지 않나? 뭔가 놓치고 있는 건가?

    • 작은 o 표기법도 여전히 점근적 명제라서 작은 n에 적용될 필요는 없음
      f(n) = o(g(n))의 정의는 대략 lim (n -> infinity) f(n)/g(n) = 0임. 다시 말해 충분히 큰 n에 대해 g가 f보다 더 빨리 자란다는 뜻임
      예를 들어 f(n) = 10n if n < 1000 else 1e1000 같은 함수는 o(n)임. n이 커지면 1e1000/n이 0으로 가기 때문임. 이는 n = 1000까지 101000으로 지수적으로 증가한 뒤 그 이후에는 상수로 남는 구간별 함수의 의사 Python 표현임
    • 알고리즘 복잡도가 3↑↑64*n^0.999라면 그 알고리즘은 o(n)이지만, 안심하고 은하 알고리즘이라고 불러도 됨

  • 기억이 맞다면 3↑↑64가 Graham의 수임

  • 젠장할 상수 계수들아, 주먹을 하늘에 흔들게 되네

  • 초록에는 시간이 m^(1+o(1))이라고만 되어 있음
    더 구체적인 상한이 어딘가에 나와 있는지 아는 사람?

    • 여기서 o는 작은 o라서, m이 무한대로 갈 때 “1로 나눈 값”이 0으로 가는 항을 포착함
      https://de.m.wikipedia.org/wiki/Landau-Symbole
    • 원하는 만큼 O(m)에 가깝게 만들 수 있도록 상수를 고를 수 있다는 뜻임
      다른 말로 하면 임의의 ɛ>1에 대해 시간 O(m^ɛ)로 실행되는 알고리즘을 얻을 수 있는 알고리즘 도식임
    • 그게 바로 구체적인 상한임
      작은 o는 n이 무한대로 갈 때 0에 가까워지는 함수이고, 점근적으로 무시 가능하다고 부름
답변달기