I spotted a serious inefficiency in our algorithm, which was already published. Basically, we have an algorithm to encode a problem A into a formula X. But we later found that we can encode into a formula X', which is equisatisfiable, but with much less (up to thousand) of variables.
This change is very trivial in logic, if we need to correct the algorithm, we only need to change 1 line with one subscript. But it improve the performance drastically, up to 10 times in some instances.
If somebody build on our work, I don't want them to make the same mistake. If somebody want to compare with our work, I want them to compare with the improved algorithm, not the result we reported in the paper.
But the change is so trivial, how could I let everybody know?
Most journals have errata for published papers. Contact the journal and ask them how you can amend your paper with the updated algorithm. They will likely simply post the erratum you provide to the online version and put a note in the next issue of the print version with the revision.