Home > Search Results: keywords:"obecné cachování"
Search:
Search Tips :: Advanced Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 2 records found  Search took 0.00 seconds. 
On the Hardness of General Caching
 Folwarczný, Lukáš ; Sgall, Jiří (advisor) ; Koutecký, Martin (referee)
Caching (also known as paging) is a classical problem concerning page re- placement policies in two-level memory systems. General caching is its vari- ant with pages of different sizes and fault costs. We aim at a better charac- terization of the computational complexity of general caching in the offline version. General caching in the offline version was recently shown to be strongly NP- hard, but the proof needed instances of caching with pages larger than half of the cache size. The primary result of this work addresses this problem as we prove: General caching is strongly NP-hard even when page sizes are limited to {1, 2, 3}. In the structural part of this work, a new simpler proof for the full characterization of work functions by layers for classical caching is given and then extended to caching with variable cache size. We invent two algorithms for restricted instances of general caching building on results around caching with variable cache size.
Detailed record
On the Hardness of General Caching
 Folwarczný, Lukáš ; Sgall, Jiří (advisor) ; Koutecký, Martin (referee)
Caching (also known as paging) is a classical problem concerning page re- placement policies in two-level memory systems. General caching is its vari- ant with pages of different sizes and fault costs. We aim at a better charac- terization of the computational complexity of general caching in the offline version. General caching in the offline version was recently shown to be strongly NP- hard, but the proof needed instances of caching with pages larger than half of the cache size. The primary result of this work addresses this problem as we prove: General caching is strongly NP-hard even when page sizes are limited to {1, 2, 3}. In the structural part of this work, a new simpler proof for the full characterization of work functions by layers for classical caching is given and then extended to caching with variable cache size. We invent two algorithms for restricted instances of general caching building on results around caching with variable cache size.
Detailed record

Interested in being notified about new results for this query?
Subscribe to the RSS feed.
Digital Repository :: Search :: Submit :: Personalize :: Help
Powered by Invenio v1.1.2
Maintained by admin.invenio@techlib.cz
This site is also available in the following languages:
Česky  English