Is improving a simple algorithm without beating the state of the art still publishable?
Sure this is publishable, but the real question is where? 

The applied mathematical community, especially the one in which the state of the art methods are developed will probably not see the improvement of the simple algorithm as worth publishing in their venues. Why should they? They know that there is something better which they understand well. In fact, I know of at least one journal which states explicitly that algorithms published there need to beat the state of the art to be suited for them. But the community of practitioners who may be struggling with the nuts and bolts of the state of the art method and often fall back to use the simple method may be impressed. 

So, choose you publication venue right and things should go well.