On the continuous CNN problem

DOI10.1007/978-3-642-17514-5_22MaRDI QIDQ3060779zbMATH OpenOpenAlexFDO

Authors John Augustine, N. V. Gravin

Publication date 9 December 2010

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.2393

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27)

Abstract: In the (discrete) CNN problem, online requests appear as points in $mathbb{R}^2$. Each request must be served before the next one is revealed. We have a server that can serve a request simply by aligning either its $x$ or $y$ coordinate with the request. The goal of the online algorithm is to minimize the total $L_1$ distance traveled by the server to serve all the requests. The best known competitive ratio for the discrete version is 879 (due to Sitters and Stougie). We study the continuous version, in which, the request can move continuously in $mathbb{R}^2$ and the server must continuously serve the request. A simple adversarial argument shows that the lower bound on the competitive ratio of any online algorithm for the continuous CNN problem is 3. Our main contribution is an online algorithm with competitive ratio $3+2sqrt3approx6.464$. Our analysis is tight. The continuous version generalizes the discrete orthogonal CNN problem, in which every request must be $x$ or $y$ aligned with the previous request. Therefore, Our result improves upon the previous best competitive ratio of 9 (due to Iwama and Yonezawa).

Recommendations

• scientific article; zbMATH DE number 1500545
• A competitive 2-server algorithm
• The CNN problem and other k-server variants
• scientific article; zbMATH DE number 2038743
• The generalized two-server problem

Cited in

(4)

• The orthogonal CNN problem
• CVPR 2020 continual learning in computer vision competition: approaches, results, current challenges and future directions
• scientific article; zbMATH DE number 1500545 (Why is no real title available?)
• Competitive Algorithms for Generalized k -Server in Uniform Metrics

This page was built for publication: On the continuous CNN problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3060779)