11 citations · 23 across the 11 of their papers we have counts for
Showing 2013 · cs.DSShow all
2 papers · 2 filters
cs.DS2013★ 11 cited
On Advice Complexity of the k-server Problem under Sparse Metrics
Sushmita Gupta, Shahin Kamali, Alejandro López-Ortiz
We consider the k-server problem under the advice model of computation when the underlying metric space is sparse. On one side, we show that an advice of size Ω(n) is required to o…
cs.DS2013
Relative Interval Analysis of Paging Algorithms on Access Graphs
Joan Boyar, Sushmita Gupta, Kim S. Larsen
Access graphs, which have been used previously in connection with competitive analysis and relative worst order analysis to model locality of reference in paging, are considered in…