k-server 문제

k-server problem
컴퓨터 과학의 미해결 문제:

의 메트릭 공간에서 -서버 문제를 해결하기 위한 k k -경쟁 알고리즘이 있는가?

(컴퓨터 과학에서 더 풀리지 않은 문제)

-서버 문제는 온라인 알고리즘의 범주에 있는 이론 컴퓨터 과학의 문제로서, 경쟁 분석 이론(다른 하나는 계량적 작업 시스템)의 중심인 미터법 공간의 두 가지 추상적 문제 중 하나이다. 이 문제에서 온라인 알고리즘은 미터법 공간의 점으로 표현되는 k 서버 집합의 이동을 제어해야 하며, 공간 내 점의 형태에 있는 요청도 처리해야 한다. 각 요청이 도착하면 알고리즘은 요청된 지점으로 이동할 서버를 결정해야 한다. 알고리즘의 목표는 요청의 전체 순서를 미리 알고 있는 최적의 상대방에 의해 서버가 이동할 수 있는 총 거리에 비해 모든 서버가 이동하는 총 거리를 작게 유지하는 것이다.

이 문제는 처음에 Mark Manasse, Lyle A에 의해 제기되었다. 맥거치와 다니엘 슬레이터(1990). k-server 문제와 관련하여 가장 눈에 띄는 공개 질문은 므낫세 외 연구원이 제기한 소위 k-server 추측이다. 이 추측에 따르면 임의의 미터법 공간에서 k-server 문제를 해결하기 위한 알고리즘이 있고, 경쟁률이 정확히 k인 서버 수가 어느 정도인지 알 수 있다. 므낫세 외 연구진은 k = 2일 때, 그리고 미터법 공간이 정확히 k+1 포인트를 가지도록 제한되었을 때 더 일반적인 k 값에 대해 그들의 추측을 증명할 수 있었다. 크로박과 라모어(1991)는 나무 지표에 대한 추측을 증명했다. 모든 거리가 동일한 특별한 지표를 페이징 문제라 부르는 것은 메모리 캐시에 페이지 교체 알고리즘의 문제를 모델링하고 있으며, 이미 이 문제를 가지고 있는 것으로 알려져 있었다. k-competitive algorithm (Sleator and Tarjan 1985). Fiat et al. (1990) first proved that there exists an algorithm with finite competitive ratio for any constant k and any metric space, and finally Koutsoupias and Papadimitriou (1995) proved that Work Function Algorithm (WFA) has competitive ratio 2k - 1. However, despite the efforts of many other researchers, reducing the competitive ratio to k or providing an improved lower bound remains open as of 2014. The most common believed scenario is that the Work Function Algorithm is k-competitive. To this direction, in 2000 Bartal and Koutsoupias showed that this is true for some special cases (if the metric space is a line, a weighted star or any metric of k+2 points).

In 2011, a randomized algorithm with competitive bound Õ(log2k log3n) was found.[1][2] In 2017, a randomized algorithm with competitive bound O(log6 k) was announced,[3] but was later retracted.[4]

Example

To make the problem more concrete, imagine sending customer support technicians to customers when they have trouble with their equipment. In our example problem there are two technicians, Mary and Noah, serving three customers, in San Francisco, California; Washington, DC; and Baltimore, Maryland. As a k-server problem, the servers are the technicians, so k = 2 and this is a 2-server problem. Washington and Baltimore are 35 miles (56 km) apart, while San Francisco is 3,000 miles (4,800 km) away from both, and initially Mary and Noah are both in San Francisco.

Consider an algorithm for assigning servers to requests that always assigns the closest server to the request, and suppose that each weekday morning the customer in Washington needs assistance while each weekday afternoon the customer in Baltimore needs assistance, and that the customer in San Francisco never needs assistance. Then, our algorithm will assign one of the servers (say Mary) to the Washington area, after which she will always be the closest server and always be assigned to all customer requests. Thus, every day our algorithm incurs the cost of traveling between Washington and Baltimore and back, 70 miles (110 km). After a year of this request pattern, the algorithm will have incurred 20,500 miles (33,000 km) travel: 3000 to send Mary to the East Coast, and 17,500 for the trips between Washington and Baltimore. On the other hand, an optimal adversary who knows the future request schedule could have sent both Mary and Noah to Washington and Baltimore respectively, paying 6,000 miles (9,700 km) of travel once but then avoiding any future travel costs. The competitive ratio of our algorithm on this input is 20,500/6000 or approximately 3.4, and by adjusting the parameters of this example the competitive ratio of this algorithm can be made arbitrarily large.

따라서 우리는 항상 가장 가까운 서버를 할당하는 것이 최적과는 거리가 멀 수 있다고 본다. 반면에, 다음 요청은 그 도시에 있을 수 있고 그것은 즉시 누군가를 돌려보내야 할 것이기 때문에, 샌프란시스코로부터 그것의 기술자 두 명을 보내달라는 미래의 요청을 모르는 알고리즘은 어리석은 것처럼 보인다. 그래서 k-server 알고리즘이 상대방에 비해 잘 수행되기는 어렵거나 불가능해 보인다. 그러나, 2-서버 문제의 경우, 항상 총 이동 거리가 상대편 거리의 최대 두 배인 알고리즘이 존재한다. k-server 추측에 따르면, 더 많은 수의 기술자에 대한 문제에 대해서도 유사한 해결책이 존재한다고 한다.

참조

  1. ^ http://people.csail.mit.edu/madry/docs/kserver.pdf
  2. ^ "Another Annoying Open Problem". 19 November 2011.
  3. ^ [2]에 밀접하게 구축된 [1]
  4. ^ "Erratum: Fusible HSTS and the randomized k-server conjecture".
  • Fiat, A.; Rabani, Y.; Ravid, Y. (1990). "Competitive k-server algorithms". Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science. pp. 454–463.