computer science - Is improving a simple algorithm without beating the state of the art still publishable?

In a particular field there are two algorithms being used:

• Algorithm Simple: you understand it in five minutes, you can implement it in fifteen.


• Algorithm State of the Art (SOA): requires very specific mathematical knowledge to understand and is hard to code. Beats Simple by a big margin, both in terms of speed and results.

However Simple is more popular because of its simplicity and not-so-bad results. Simple has 130 citations, SOA has 80. In 2016 Simple had 20 citations, SOA 17.

While trying to use the Simple paper, our results were so bad we spent more than a week looking for a bug in our implementation. Finally, we discovered a one line change that makes it work much better, improving a mathematical approximation in the Simple paper that is easily overlooked. After reviewing recent literature, it seems this is not known (we can reproduce recent papers).

We can prove that the one line change is statistically better and equally fast as Simple but statistically worse and slower than SOA. We also have a 5-line-change improvement which makes it both better and faster than Simple, worse results than SOA but slightly (10–20%) faster than SOA.

What should we do? Since we are not beating SOA's results and it is a one line change it may be hard to publish, but it is clearly something people in the field would profit from.

Edit: some have noted it's similar to this question. There are two differences:

1. We are not coming up with a different algorithm, just making a small modification.


2. On the other hand we are a simpler algorithm than SOA, and there's value in it. In particular the 1-line change is as simple as the Simple algorithm and the 5-line change is still much simpler than the SOA algorithm.

Answer

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.