On the Continuous CNN Problem

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

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+2 \sqrt{3} \approx 6.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).

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

On the Continuous CNN Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Continuous CNN Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Continuous CNN Problem will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-527681

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.