About: List update problem

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: List update problem Goto Sponge NotDistinct Permalink

An Entity of Type : yago:WikicatRandomizedAlgorithms, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon

http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FList_update_problem&invfp=IFP_OFF&sas=SAME_AS_OFF

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:

Attributes	Values
rdf:type	person yago:WikicatOnlineAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatRandomizedAlgorithms
rdfs:label	List update problem (en)
rdfs: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. The standard model includes two reordering actions: (en)
dcterms:subject	Randomized algorithms Analysis of algorithms Online algorithms
Wikipage page ID	31616744 (xsd:integer)
Wikipage revision ID	1084599508 (xsd:integer)
Link from a Wikipage to another Wikipage	Randomized algorithms Online algorithm NP-hard Linked List Competitive analysis (online algorithm) Potential method Analysis of algorithms Adversary model Online algorithms Cache algorithms Online algorithms dbr:Burrows–Wheeler_Transform
Link from a Wikipage to an external page	https://www.cs.technion.ac.il/~rani/book.html
sameAs	List update problem List update problem List update problem List update problem
dbp:wikiPageUsesTemplate	dbt:Citation dbt:Cite_book dbt:Harv dbt:Reflist
has 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 adjacent items in the list. Performance of algorithms depend on the construction of request sequences by adversaries under various Adversary models An 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. Along with its original uses, this problem has been suggested to have a strong similarity to problems of improving global context and compressibility following a . Following this transform, files tend to have large regions with locally high frequencies, and compression efficiency is greatly improved by techniques that tend to move frequently-occurring characters toward zero, or the front of the "list". Due to this, methods and variants of Move-to-Front and frequency counts often follow the BWT algorithm to improve compressibility. (en)
gold:hypernym	Model
prov:wasDerivedFrom	wikipedia-en:List_update_problem?oldid=1084599508&ns=0
page length (characters) of wiki page	8502 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:List_update_problem
is Link from a Wikipage to another Wikipage of	Online optimization Online algorithm Competitive analysis (online algorithm)
is foaf:primaryTopic of	wikipedia-en:List_update_problem

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 60 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software