Name
Abstract | ||
|---|---|---|
The list update problem is a well studied online problem in the area of self-adjusting data structures. Understanding the o?ine version of this problem is crucial because of the role it plays in the competitive analysis of online list update algorithms. In this paper we settle a long-standing open problem by showing that the o?ine list update problem is NP-hard.
|
Year | Venue | Field |
|---|---|---|
2017 | SIGACT News | Online algorithm,Data structure,Open problem,List update problem,Computer science,Theoretical computer science,Competitive analysis |
DocType | Volume | Issue |
Journal | 48 | 3 |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christoph Ambühl | 1 | 357 | 18.50 |