Paper Info
Title
Offline List Update is NP-Hard
Abstract
In the offline list update problem, we maintain an unsorted linear list used as a dictionary. Accessing the item at position i in the list costs i units. In order to reduce access cost, we are allowed to update the list at any time by transposing consecutive items at a cost of one unit. Given a sequence σ of requests one has to serve in turn, we are interested in the minimal cost needed to serve all requests. Little is known about this problem. The best algorithm so far needs exponential time in the number of items in the list. We show that there is no polynomial algorithm unless P = NP.
Year
Venue
Keywords
2000
ESA
offline list,consecutive item,best algorithm,position i,exponential time,unsorted linear list,i unit,minimal cost,polynomial algorithm,offline list update problem,access cost,competitive analysis
Field
DocType
ISBN
Association list,Combinatorics,NP-complete,List update problem,Computer science,Upper and lower bounds,Polynomial algorithm,Self-organizing list,Linear search,Competitive analysis
Conference
3-540-41004-X
Citations 
PageRank 
References 
11
0.61
14
Authors
1
Name
Order
Citations
PageRank
Christoph Ambühl135718.50