To solve an NP-hard optimization problem optimally, we can use mathematical programming or brute force techniques. I would like to know if it is possible to solve the problem in an online fashion optimally? Is there any mathematical tool that can perform this task? I can design an online algorithm to solve the problem but I cannot say it gives the best possible online solution. However, with brute force methods, I can guarantee for sure that the solution produced is the best possible offline solution.

This question comes to my head when trying to compare my online algorithm to something; an online optimal algorithm, to see how well my online algorithm is performing. In the offline case, it is easy for me to compare. Once I have my offline algorithm, I implement a brute force or a mathematical program and I do the comparison. How to do the comparison for the online case?

EDIT: An online algorithm should make decisions in an irrevocable way.

  • $\begingroup$ What do you mean by "online"? If you mean that you compute solution incrementally for each input update, then you can always throw away your previous solution and compute the result from skretch. $\endgroup$ – Dmitry Aug 31 '20 at 18:20
  • $\begingroup$ Yes, it is an incremental solution. If I throw away my previous solution, at the end I will end up with the offline optimal solution. $\endgroup$ – zdm Aug 31 '20 at 18:48
  • $\begingroup$ ... which is also an online optimal solution. If you have something else in mind, please clarify the question. $\endgroup$ – Dmitry Aug 31 '20 at 19:34

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.