Can you publish a paper Simply Implementing another Paper's Algorithm?
This is a judgement call and will be for editors and reviewers. But the main question they will want answered is what is new/novel in your paper? If you can give them that, then they will be more likely to accept it. 

The other question is, whether exactness is worth the effort. If the approximation methods give good enough answers then the expense of an exact solution may not be worth it in practice. Can you address that issue in your paper? 

You don't describe anything here about scaling if that is an issue with the algorithm. A few minutes on a modern system may be good or bad, depending. If the algorithm needs to be executed once for each Google query, then it is pretty bad. If it has to be executed once per "noticed supernova" then probably fine. 

There are a lot of questions your paper could address that might push the editor toward acceptance if you can handle them well.