After my recent paper submission to a journal, I received a comment which I am unable to understand. The comment goes like

You need to elaborate more about the insight/intuition behind the algorithm design and how the proposed algorithms are related to the previous analysis. It is better if you can show that the algorithm is (asymptotically) optimal, or characterize the optimality gap, at least for some special cases.

What does optimality gap or asymptotic optimality mean here?

Just for reference: In my paper, I proposed two algorithms that heuristically solved a problem and then compared them agains brute-force and randomized algorithms.

  • $\begingroup$ It probably means you should discuss how good the solutions produced by your algorithm are compared to the optimal solutions. $\endgroup$ – Michal Adamaszek Nov 9 '18 at 11:56

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.