Matches in DBpedia 2014 for { <http://dbpedia.org/resource/K-server_problem> ?p ?o. }
Showing items 1 to 30 of
30
with 100 items per page.
- K-server_problem abstract "The k-server problem is a problem of theoretical computer science in the category of online algorithms, one of two abstract problems on metric spaces that are central to the theory of competitive analysis (the other being metrical task systems). In this problem, an online algorithm must control the movement of a set of k servers, represented as points in a metric space, and handle requests that are also in the form of points in the space. As each request arrives, the algorithm must determine which server to move to the requested point. The goal of the algorithm is to keep the total distance all servers move small, relative to the total distance the servers could have moved by an optimal adversary who knows in advance the entire sequence of requests.The problem was first posed by Mark Manasse, Lyle A. McGeoch and Daniel Sleator (1990). The most prominent open question concerning the k-server problem is the so-called k-server conjecture, also posed by Manasse et al. 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 at most k. Manasse et al. were able to prove their conjecture when k = 2, and for more general values of k when the metric space is restricted to have exactly k+1 points. Chrobak and Larmore (1991) proved the conjecture for tree metrics. The special case of metrics in which all distances are equal is called the paging problem because it models the problem of page replacement algorithms in memory caches, and was also already known to have a 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 a competitive ratio of 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 2006.In 2011, an algorithm with competitive bound Õ(log2k log3n) was found.".
- K-server_problem wikiPageID "7767038".
- K-server_problem wikiPageRevisionID "582699617".
- K-server_problem hasPhotoCollection K-server_problem.
- K-server_problem subject Category:Online_algorithms.
- K-server_problem subject Category:Unsolved_problems_in_computer_science.
- K-server_problem type Abstraction100002137.
- K-server_problem type Act100030358.
- K-server_problem type Activity100407535.
- K-server_problem type Algorithm105847438.
- K-server_problem type Attribute100024264.
- K-server_problem type Condition113920835.
- K-server_problem type Difficulty114408086.
- K-server_problem type Event100029378.
- K-server_problem type OnlineAlgorithms.
- K-server_problem type Problem114410605.
- K-server_problem type Procedure101023820.
- K-server_problem type PsychologicalFeature100023100.
- K-server_problem type Rule105846932.
- K-server_problem type State100024720.
- K-server_problem type UnsolvedProblemsInComputerScience.
- K-server_problem type YagoPermanentlyLocatedEntity.
- K-server_problem comment "The k-server problem is a problem of theoretical computer science in the category of online algorithms, one of two abstract problems on metric spaces that are central to the theory of competitive analysis (the other being metrical task systems). In this problem, an online algorithm must control the movement of a set of k servers, represented as points in a metric space, and handle requests that are also in the form of points in the space.".
- K-server_problem label "K-server problem".
- K-server_problem sameAs m.026cc98.
- K-server_problem sameAs Q6322866.
- K-server_problem sameAs Q6322866.
- K-server_problem sameAs K-server_problem.
- K-server_problem wasDerivedFrom K-server_problem?oldid=582699617.
- K-server_problem isPrimaryTopicOf K-server_problem.