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

Question

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 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

Expanding on the issue of where to publish, you should also consider in what format. For example, IEEE has several "Letters" (I seem to recall an "Information Processing Letters") that tend to be short (4-page) papers that could welcome something like what you describe.

Also, some conferences (and journals) welcome also position papers that, among other things, can challenge commonly accepted paradigms (what you describe could fit into this --- you're challenging the perception of not-so-good performance of the simple algorithm).

Lastly --- some conferences and journals welcome short papers, where there is novelty but not necessarily substantial amounts of new ideas or analysis or experimental results.