Hiring an academic researcher to implement an algorithm in a paper they wrote
It is definitely appropriate to ask.  University policies on outside work for employees vary.  But typically it is allowed.  There are at least three possible approaches to this.


You hire the academic directly, and it is a side job for them.
You provide the university with research funding, which is then used to pay to make the implementation.  This might have tax benefits, it will make the academic look good, and will allow the university to take a cut of the money.
You partner with the university to obtain funding from a third party (probably a government program).  Your company pays for the commercial part of the project and the third party provides pure research funds the academics want.  This makes everyone look good but can be slow.


The key thing here is that you need to convince the academics that there is a benefit for them to participating.  This is a matter of their personal preferences.