Similar to the theory of hardness of approximation for (offline) approximation algorithms, has there been any work done on proving hardness guarantees for online algorithms? Theoretical lower bounds on competitive ratio conditioned on hardness of some other problem?

  • $\begingroup$ In other words, you are looking for problems in which the competitive ratio is $x$, but you can only guarantee competitive ratio $y$ using an efficient algorithm. Please correct me if I misunderstood. $\endgroup$ – Yuval Filmus Apr 4 '18 at 15:51
  • $\begingroup$ @YuvalFilmus Yes. To clarify, I wanted to know if there are any formal techniques to proving that the competitive ratio of the problem in question is in fact some $x$, when the best known algorithmic guarantee is only some $y > x$. $\endgroup$ – Television Apr 4 '18 at 17:18
  • 1
    $\begingroup$ There are certainly techniques for proving lower bounds on the competitive ratio. You can find some of them in any lecture notes on online algorithms. $\endgroup$ – Yuval Filmus Apr 4 '18 at 17:20
  • $\begingroup$ @YuvalFilmus Oh, I was not aware of this. Would you have any recommendations for a good place to start? $\endgroup$ – Television Apr 4 '18 at 19:01
  • $\begingroup$ Pick up any lecture notes on the subject. There is also a textbook. $\endgroup$ – Yuval Filmus Apr 4 '18 at 19:06

Your Answer

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

Browse other questions tagged or ask your own question.