Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/K-server_problem> ?p ?o }
Showing triples 1 to 41 of
41
with 100 triples 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 least 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 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.".
- K-server_problem wikiPageID "7767038".
- K-server_problem wikiPageLength "7098".
- K-server_problem wikiPageOutDegree "22".
- K-server_problem wikiPageRevisionID "691340955".
- K-server_problem wikiPageWikiLink Category:Online_algorithms.
- K-server_problem wikiPageWikiLink Category:Unsolved_problems_in_computer_science.
- K-server_problem wikiPageWikiLink Christos_Papadimitriou.
- K-server_problem wikiPageWikiLink Competitive_analysis_(online_algorithm).
- K-server_problem wikiPageWikiLink Daniel_Sleator.
- K-server_problem wikiPageWikiLink Lawrence_L._Larmore.
- K-server_problem wikiPageWikiLink Marek_Chrobak.
- K-server_problem wikiPageWikiLink Mark_Manasse.
- K-server_problem wikiPageWikiLink Metric_space.
- K-server_problem wikiPageWikiLink Metrical_task_system.
- K-server_problem wikiPageWikiLink Online_algorithm.
- K-server_problem wikiPageWikiLink Page_replacement_algorithm.
- K-server_problem wikiPageWikiLink Robert_Tarjan.
- K-server_problem wikiPageWikiLink Theoretical_computer_science.
- K-server_problem wikiPageWikiLinkText "''k''-server problem".
- K-server_problem wikiPageWikiLinkText "K-server problem".
- K-server_problem wikiPageWikiLinkText "k-server problem".
- K-server_problem wikiPageWikiLinkText "moving-server".
- K-server_problem wikiPageUsesTemplate Template:As_of.
- K-server_problem wikiPageUsesTemplate Template:Cite_conference.
- K-server_problem wikiPageUsesTemplate Template:Cite_journal.
- K-server_problem wikiPageUsesTemplate Template:Convert.
- K-server_problem wikiPageUsesTemplate Template:Unsolved.
- K-server_problem subject Category:Online_algorithms.
- K-server_problem subject Category:Unsolved_problems_in_computer_science.
- K-server_problem hypernym Problem.
- K-server_problem type Disease.
- K-server_problem type Algorithm.
- 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 Q6322866.
- K-server_problem sameAs Problema_k-server.
- K-server_problem sameAs m.026cc98.
- K-server_problem sameAs Q6322866.
- K-server_problem wasDerivedFrom K-server_problem?oldid=691340955.
- K-server_problem isPrimaryTopicOf K-server_problem.