This conjecture states that there is an algorithm for solving the k-server problem in an arbitrary metric space and for any number k of servers that has competitive ratio exactly k. Manasse et al. were able to prove their conjecture when k = 2, and for more general values of k for some metric spaces restricted to have exactly k+1 points.
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[update].
In our example problem there are two technicians, Mary and Noah, serving three customers, in San Francisco, California; Washington, DC; and Baltimore, Maryland.
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: 3,000 to send Mary to the East Coast, and 17,500 for the trips between Washington and Baltimore.
The k-server conjecture states that similar solutions exist for problems with any larger number of technicians.