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.

Adding to @Dirk's fine answer:

• If you publish free-license code rather than just an algorithm/pseudo-code - that's a publishable novelty.
• If your analysis of Simple is not merely an application of the analysis used to obtain SOA, then this in itself is publishable unless entirely trivial; I would also look into whether the same 'trick' can be applied in other settings, which would allow for a paper on "Improving X, Y and Z by frobincating the bar" and the Simple imporvement would only be a part of it.
• Simple-to-implement algorithms can sometimes beat asymptotically-better-but-heavy algorithms under various constraints of various kinds, such as limited asymptotic space complexity, no randomness, switching from average case to worst case, or even not having enough memory to store the program code, requiring very compact implementations (e.g. in hardware) and no dependence on large libraries. Perhaps you could explore that.

As a civil engineer who develops mathematical models, I publish this sort of result fairly regularly. In my field, we focus on models that are 'good enough' and can be adopted and adapted quickly easily. Quickly means we can make more profit on future jobs, and easily means less chance of mistakes / easier for reviewers to check the working.

We would tend to take this sort of thing to conferences rather than scientific journals.

Journals tend to need the greatest, newest and best. At conferences (specifically, those I'm familiar with that are attended by civil engineers), people are often interested in what is practical that they can use tomorrow.

So, I'd recommend submitting a paper to a relevant conference describing the usual problem and how you've improved a common method for solving it. The people who use the simple method will be pleased to attend your talk. You won't be lauded as the next Einstein, but your work will still be referencable in the conference proceedings, and you'll be able to put it in your CV.