2
$\begingroup$

We know that for some online problems, algorithms can decrease their competitive ratio greatly if they are allowed to change some of their past decisions (see http://epubs.siam.org/doi/pdf/10.1137/1.9781611973402.35).

I wonder if there are instances of online problems such that the competitive ratio does not decrease even if the algorithm is allowed to change its decisions ?

$\endgroup$
  • 2
    $\begingroup$ Your title reads, roughly, like: "Staying dry and take a shower." $\endgroup$ – Raphael Apr 28 '17 at 17:45
  • $\begingroup$ We prefer references that fulfill the minimal scholarly requirements (e.g., includes title and authors and where published). This helps ensure others who search for the paper title find this, and helps ensure the reference will be as robust over time as possible. I encourage you to improve your post in this regard. We have collected some advice here. Thank you! $\endgroup$ – D.W. Apr 29 '17 at 0:45
1
$\begingroup$

Every problem where the online algorithm is optimal, i.e. has competitive ratio 1, is a (trivial) example. Such algorithms exist, for example for some scheduling problems.

$\endgroup$
  • $\begingroup$ You're of course right. But what about the problems where online algorithm is not optimal ? $\endgroup$ – SpiderRico Dec 29 '16 at 14:31
  • $\begingroup$ It must depend on how many changes are allowed. If unlimited changes are allowed after each new input, you just calculate the optimal offline answer each time and give that as an answer each time step, hitting ratio 1. If 0 changes are allowed after each new input, you have your traditional online competitive ratio. The question is, for any given algorithm, what does the ratio look like as a function of how many decisions you are allowed to change. In all cases, it will approach 1, but how quickly? $\endgroup$ – Algorithms with Attitude Dec 30 '16 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.