연구원들은 온라인 알고리즘에 대한 널리 퍼진 믿음을 반박합니다 | 콴타 매거진

인생에서 우리는 때때로 원하는 정보 없이 결정을 내려야 할 때가 있습니다. 그것은 컴퓨터 과학에서도 마찬가지입니다. 이것은 이름에도 불구하고 반드시 인터넷을 포함하지는 않는 온라인 알고리즘의 영역입니다. 대신, 이는 다음에 무슨 일이 일어날지 전혀 알지 못한 채 데이터가 도착하는 대로 응답하는 문제 해결 전략입니다. 불확실성에 대처하는 능력 덕분에 이러한 알고리즘은 노트북의 메모리 관리나 웹을 탐색하는 사람들에게 표시할 광고 선택과 같은 실제 난제에 유용합니다.

연구자들은 이러한 문제를 해결하기 위한 새로운 방법을 조사하기 위해 이러한 문제의 일반화된 버전을 연구합니다. 그 중 가장 유명한 것은 "k-서버 문제”는 하나씩 들어오는 요청을 처리하기 위해 에이전트 함대를 파견하는 까다로운 작업을 설명합니다. 그들은 수리 기술자나 소방관일 수도 있고 심지어 순회 아이스크림 판매원일 수도 있습니다.

"이 문제를 정의하는 것은 정말 간단합니다."라고 말했습니다. 마르신 빈코프스키, 폴란드 브로츠와프 대학의 알고리즘 연구원. 그러나 그것은 “이상할 정도로 어려운 것으로 밝혀졌습니다.” 연구자들이 공격을 시작한 이후로 k- 1980년대 후반 서버 문제로 인해 그들은 온라인 알고리즘이 작업을 얼마나 잘 처리할 수 있는지 궁금해했습니다.

수십 년에 걸쳐 연구자들은 항상 달성할 수 있는 특정 수준의 알고리즘 성능이 있다고 믿기 시작했습니다. k-서버 문제. 따라서 다루고 있는 문제의 버전이 무엇이든 이 목표를 달성하는 알고리즘이 있을 것입니다. 하지만 지난 XNUMX월 온라인에 처음 발표된 논문에서 세 명의 컴퓨터 과학자가 보여 이것이 항상 달성 가능한 것은 아니라는 것입니다. 어떤 경우에는 모든 알고리즘이 부족합니다.

“나에게 큰 놀라움이었다고 말하게 되어 기쁘다”고 말했다. 아누팜 굽타, Carnegie Mellon University에서 알고리즘을 연구하고 있으며 논문에는 참여하지 않았습니다. 이 연구는 “이 분야의 핵심 문제에 대한 더 깊은 통찰력”을 제공합니다.

컴퓨터 과학자가 먼저 이 문제를 설명했습니다 이해를 돕기 위해 배관공을 고용하는 회사를 상상해 봅시다. 전화가 오면 회사는 어느 배관공이 어느 위치로 갈지 결정해야 합니다. 회사의 목표 — 그리고 알고리즘의 목표 k-서버 문제 - 모든 배관공이 이동하는 총 거리를 최소화하는 것입니다.

까다로운 부분은 회사에서 전화가 어디서 올지 미리 알 수 없다는 것입니다. 그렇다면 미래를 아는 '오프라인 알고리즘'에 의존할 수 있을 것입니다. 특히 일련의 통화에 대해 총 이동이 가장 적은 솔루션을 찾는 이상적인 파견 전략을 사용할 수 있습니다. 어떤 온라인 알고리즘도 이를 능가할 수 없으며 심지어 안정적으로 일치할 수도 없습니다.

그러나 연구자들은 가능한 한 가까이 다가가기를 원합니다. 그들은 각 전략의 이동 거리를 비교하고 경쟁 비율을 계산하여 온라인 알고리즘의 성능을 측정합니다. 알고리즘 설계자는 오프라인 이상에 접근하는 온라인 전략을 만들어 이 비율을 1로 낮추려고 노력합니다.

우리 배관 회사에 배관공이 두 명뿐이고 긴 거리 하나에만 서비스를 제공한다고 가정해 보겠습니다. 전화는 한 번에 하나씩 옵니다. 욕심 많은 알고리즘으로 알려진 합리적인 첫 번째 접근 방식은 모든 수신 전화 위치에 가장 가까운 배관공을 파견하는 것입니다. 하지만 이 알고리즘이 어려움을 겪는 시나리오는 다음과 같습니다. 한 배관공이 거리의 서쪽 끝에서 시작하고 다른 배관공은 동쪽 끝에서 시작하고 모든 전화가 서쪽 끝에 있는 두 이웃 집에서 온다고 상상해 보세요. 이 경우 한 배관공은 절대 움직이지 않고 다른 배관공은 그 두 집에서 수 마일을 쌓습니다. 돌이켜보면 가장 좋은 전략은 두 배관공을 문제가 발생하기 쉬운 지역으로 옮기는 것이었지만 안타깝게도 그것이 어디로 갈지 알 수 없었습니다.

그럼에도 불구하고 Bieńkowski는 그리디 알고리즘보다 더 나은 결과를 얻을 수 있다고 말했습니다. “이중 적용 범위”알고리즘은 두 배관공 중 한 사람이 도달할 때까지 두 배관공 사이에 있는 호출을 향해 동일한 속도로 이동합니다. 이 방법은 그리디 알고리즘보다 낮은 경쟁률을 달성합니다.

이 추상적인 문제는 실제 배관 회사와는 관련이 없지만 " k-서버 문제 자체는 실제로 온라인 컴퓨팅에서 결정적인 질문입니다. 유발 라바니, 최근 논문을 공동 집필한 예루살렘 히브리 대학교의 컴퓨터 과학자입니다. 부분적으로는 작업 중에 개발된 도구와 기술 때문입니다. k-서버 문제는 종종 온라인 알고리즘 연구의 다른 곳, 심지어는 그 외부에서도 응용 프로그램을 찾습니다.

“이것은 알고리즘 작업의 마법 중 일부입니다.”라고 그는 말했습니다.

과학자들은 이러한 문제를 연구할 때 이를 적과의 게임으로 상상하기를 좋아합니다. 공격자는 온라인 알고리즘이 오프라인 알고리즘에 비해 최대한 나쁜 성능을 발휘하도록 하기 위해 사악한 일련의 요청을 선택합니다. 적의 힘 중 일부를 빼앗기 위해 연구자들은 다음을 포함하는 알고리즘을 사용합니다. 무작위 결정.

이 전략은 매우 효과적이며 연구자들은 1990년대 초반부터 특정 성능 목표(로그에 비례하는 경쟁 비율)에 도달하는 무작위 알고리즘을 항상 찾을 수 있다고 의심해 왔습니다. k어디로 k 상담원 수입니다. 이것을 무작위라고 부른다. k-서버 추측 및 연구자들은 이것이 일부 공간 또는 특정 지점 모음(배관공을 요구할 수 있는 주택과 동일)에 대해 사실임을 보여주었습니다. 그러나 모든 경우에 대해 입증된 것은 아닙니다.

대부분의 연구자와 마찬가지로 Rabani와 그의 공동 저자는 — 세바스티앙 부벡 Microsoft Research 및 크리스티안 코스터 옥스포드 대학의 교수는 그 추측이 사실이라고 생각했습니다. Coester는 “나는 그것을 의심할 이유가 없었습니다.”라고 말했습니다.

그러나 다른 온라인 문제를 해결하면서 상황이 바뀌기 시작했습니다. 그것은 다음과 관련이 있었습니다. k- 서버 문제로 알려진 경쟁률 하한이 예상외로 높았습니다. 아마도 로그만큼 낮은 목표를 생각하게 만들었을 것입니다. k 위한 k-서버 문제가 지나치게 낙관적이었습니다.

Rabani는 무작위 배정을 처음으로 제안한 사람이 Coester라고 말했습니다. k-서버 추측이 거짓일 수 있습니다. “그가 말하자마자 모든 것이 이해가 되었습니다.”

추측을 반박하기 위해 저자는 온라인 알고리즘이 로그의 경쟁 비율에 도달하지 못하게 하는 완벽한 폭풍을 만들어내는 대적 역할을 했습니다. k. 그들의 전략은 두 부분으로 구성됩니다. 그들은 복잡하고 프랙탈과 같은 공간의 계열을 구성하고 가능한 알고리즘으로는 어려울 수 있는 요청 시퀀스의 분포를 설계했습니다. 알고리즘의 첫 번째 이동에서 공간의 구조는 두 개의 동일한 경로 중에서 선택해야 함을 의미했으며, 그 중 하나는 결국 요청에 따라 추가 이동이 필요했습니다. 그런 다음 저자는 재귀라는 방법을 사용하여 이러한 결정 지점을 곱하는 공간을 구축하여 알고리즘을 잘못된 옵션의 늪에 빠뜨리고 비용을 높였습니다.

그 선택은 라바니에게 로버트 프로스트(Robert Frost)의 시를 떠올리게 했습니다.가지 않은 길,” 여행자는 노란 숲을 통해 두 가지 잠재적인 경로를 고려합니다. “우리는 시를 재귀적으로 적용할 뿐입니다.”라고 그는 농담했습니다. "그리고 상황이 정말 나빠지죠."

저자는 자신이 구성한 공간에서 무작위 알고리즘이 결코 (로그)보다 더 나은 경쟁률을 달성할 수 없음을 보여주었습니다. k)², 로그의 보편적 목표를 추진 k 영원히 닿을 수 없는 곳. 그들은 그 추측을 반박했습니다.

상을 받은 이 작품은 최고의 논문상 에 2023년 컴퓨팅 이론 심포지엄굽타는 "확실한 이론적" 이정표를 세웠다고 말했다. 이러한 종류의 결과는 우리가 알고리즘에서 어떤 종류의 성능을 기대할 수 있는지를 나타내는 데 도움이 됩니다. 그러나 실제로 알고리즘 설계자는 전능한 적이 존재하고 미래에 대한 완전한 무지가 있는 최악의 시나리오를 계획하지 않는 경우가 많습니다. 알고리즘이 실제 문제에 적용되면 이론적인 기대치를 초과하는 경우가 많습니다.

다른 문제에 사용되는 무작위 알고리즘의 한계점을 입증한 이 논문은 해당 분야의 향후 작업에도 영향을 미칠 수 있습니다. 굽타는 이번 결과가 저자가 사용한 기술의 "강력함"을 분명히 보여준다고 말했습니다.

아마도 미래의 발견은 이번 연구처럼 연구자들의 기대를 거스르게 될 것이라고 Rabani는 말했습니다. "이것은 틀렸다는 것이 정말 기분 좋은 사례 중 하나입니다."

콴타 에서는 청중에게 더 나은 서비스를 제공하기 위해 일련의 설문조사를 실시하고 있습니다. 우리의 컴퓨터 과학 독자 설문조사 그러면 당신은 무료로 승리할 수 있는 자격을 얻게 될 것입니다 콴타 상품.