Is an improved algorithm for a non-hot problem publishable?
Journals often publish articles that show something that is "interesting" or "elegant" or "unexpected", even if the topic may not necessarily be "hot". (Of course, it is easier to publish something that combines any of these attributes with "hot", but not all articles are on "hot" topics.) So, I think there is hope in your case and I would give it a try.

I would, however, suggest that you do a careful literature review. You compare your algorithm with a "naive" one, but that may not mean that the "naive" algorithm is what people would use or what is considered state of the art. For example, the traveling salesman problem is known to be an exponentially complicated problem if you are looking for an exact solution, but that doesn't mean that that is what people use when they actually want to solve such problems -- very good approximate solutions can be found quite efficiently.

In other words, in your paper you will not only have to explain your new method, but you should point out that people have actually been using the "ridiculously bad" method. Otherwise, you will hear from the reviewers that you make your approach sound artificially good by comparing it with something no reasonable person would use.