Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/List_update_problem> ?p ?o }
Showing triples 1 to 39 of
39
with 100 triples per page.
- List_update_problem abstract "The List Update or the List Access problem is a simple model used in the study of competitive analysis of online algorithms. Given a set of items in a list where the cost of accessing an item is proportional to its distance from the head of the list, e.g. a Linked List, and a request sequence of accesses, the problem is to come up with a strategy of reordering the list so that the total cost of accesses is minimized. The reordering can be done at any time but incurs a cost. The standard model includes two reordering actions: A free transposition of the item being accessed anywhere ahead of its current position; A paid transposition of a unit cost for exchanging any two items in the list. Performance of algorithms depend on the construction of request sequences by adversaries under various Adversary modelsAn online algorithm for this problem has to reorder the elements and serve requests based only on the knowledge of previously requested items and hence its strategy may not have the optimum cost as compared to an offline algorithm that gets to see the entire request sequence and devise a complete strategy before serving the first request.".
- List_update_problem wikiPageExternalLink book.html.
- List_update_problem wikiPageID "31616744".
- List_update_problem wikiPageLength "7609".
- List_update_problem wikiPageOutDegree "12".
- List_update_problem wikiPageRevisionID "681771355".
- List_update_problem wikiPageWikiLink Adversary_model.
- List_update_problem wikiPageWikiLink Cache_algorithms.
- List_update_problem wikiPageWikiLink Category:Analysis_of_algorithms.
- List_update_problem wikiPageWikiLink Category:Online_algorithms.
- List_update_problem wikiPageWikiLink Category:Randomized_algorithms.
- List_update_problem wikiPageWikiLink Competitive_analysis_(online_algorithm).
- List_update_problem wikiPageWikiLink Linked_List.
- List_update_problem wikiPageWikiLink Linked_list.
- List_update_problem wikiPageWikiLink NP-hard.
- List_update_problem wikiPageWikiLink NP-hardness.
- List_update_problem wikiPageWikiLink Online_algorithm.
- List_update_problem wikiPageWikiLink Online_algorithms.
- List_update_problem wikiPageWikiLink Potential_method.
- List_update_problem wikiPageWikiLinkText "List update problem".
- List_update_problem wikiPageWikiLinkText "list update problem".
- List_update_problem hasPhotoCollection List_update_problem.
- List_update_problem wikiPageUsesTemplate Template:Citation.
- List_update_problem wikiPageUsesTemplate Template:Cite_book.
- List_update_problem wikiPageUsesTemplate Template:Harv.
- List_update_problem wikiPageUsesTemplate Template:Reflist.
- List_update_problem subject Category:Analysis_of_algorithms.
- List_update_problem subject Category:Online_algorithms.
- List_update_problem subject Category:Randomized_algorithms.
- List_update_problem hypernym Model.
- List_update_problem type Person.
- List_update_problem type Algorithm.
- List_update_problem comment "The List Update or the List Access problem is a simple model used in the study of competitive analysis of online algorithms. Given a set of items in a list where the cost of accessing an item is proportional to its distance from the head of the list, e.g. a Linked List, and a request sequence of accesses, the problem is to come up with a strategy of reordering the list so that the total cost of accesses is minimized. The reordering can be done at any time but incurs a cost.".
- List_update_problem label "List update problem".
- List_update_problem sameAs m.0gmf5vl.
- List_update_problem sameAs Q6646020.
- List_update_problem sameAs Q6646020.
- List_update_problem wasDerivedFrom List_update_problem?oldid=681771355.
- List_update_problem isPrimaryTopicOf List_update_problem.