Publishing an algorithm that may not have many applications?
Is it possible to publish such algorithms?


It's not only possible, it's far more common than the alternative.  Most algorithms papers do not have real applications.  The vast majority are motivated by applications, but there are usually several layers of abstraction and/or simplification between the problem actually solved and the motivating application.  But even this "motivation" is often post-hoc rationalization, added by the authors to help draw the reader into their paper.  Most people who study algorithms do it primarily because algorithms are cool, not primarily because they're useful.

Or maybe that's just me.


  Does it even make sense to publish it?


In principle, sure!  Of course, to be publishable, your algorithm needs to be both novel and interesting, not just to you, but to the algorithms community as a whole.  You need to be sure that your problem hasn't been solved before, and in particular that your algorithm wasn't already discovered and published by someone else.  You also need to sell the problem, the algorithm, or both; it's not enough for your algorithm to be "non-trivial".

I strongly recommend running your algorithm past a local algorithms expert, if possible.  They may recognize your problem or your technique under a different guise.  At a minimum, they should be able to help you start the necessary literature search. 

Good luck!