Output details
11 - Computer Science and Informatics
University of Warwick
Output title
An O(log k)-competitive algorithm for generalized caching
Type
E - Conference contribution
Name of conference/published proceedings
Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA '12)
Volume number
-
Issue number
-
First page of article
1681
ISSN of proceedings
-
Year of publication
2012
Number of additional authors
3
Additional information
<12> This research, presented at one of the strongest conferences in theoretical CS, solves a fundamental scheduling problem, identified by Sleator (CMU) and Tarjan (Princeton) in 1985. The novelty of this result enabled Epstein, Imreh, Levin and Nagy-Gyorgy (Haifa, Szeged, Technion) to vastly simplify a proof of a related problem. The techniques were also instrumental in the author’s recent paper demonstrating optimal bounds for a different scheduling problem. This in turn assisted Avigdor-Elgrabli and Rabani (Hebrew U.) in solving a related fundamental scheduling problem, which itself had been an open problem for over a decade.
Interdisciplinary
-
Cross-referral requested
-
Research group
T - Theory and Foundations
Citation count
3
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
