# 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.
• Not having done so myself, but I hope that's publishable (i.e., it sounds like people should have that available). Commented Dec 17, 2016 at 15:36
• Commented Dec 17, 2016 at 17:02
• There are certainly examples in the "standard" numerical algorithms for optimization, where the difference between a "good" and "bad" version of the algorithm is no more than a re-arrangement of the same mathematical equation, to reduce the effect of rounding errors accumulating over several iterations in a rather non-obvious way. Publishing the reason why your version is better may be a valuable contribution to the subject, however trivial the change to the code might look. Commented Dec 17, 2016 at 20:23
• Also, there is the following philosophical argument as to why this should be publishable: suppose that Simple+ImprovementA+ImprovementB beats SOA. If the person who discovers ImprovementA buries it in a drawer instead of publishing it, we will never know until someone randomly rediscovers both ImprovementA and ImprovementB at the same time, which is much less lilkely. Commented Dec 18, 2016 at 13:00
• You spent a week debugging the SIMPLE algorithm and you found a 5-line change that makes it work MUCH BETTER. Why are you so confident that your algorithm is correct? Commented Dec 18, 2016 at 23:57

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.

• One problem the referees of the publications the “community of practitioners” read, are likely to be the experts that can understand the state of the art….
– Ian
Commented Dec 17, 2016 at 22:09
• I'm not familiar with the mathematical community, but in other communities a possibility would be that of submitting a short communication, or equivalent. Commented Dec 17, 2016 at 23:30
• Computer science is the one area where anything less than an order if magnitude improvement is often considered uninteresting... Commented Dec 18, 2016 at 4:05
• I would check out a "letters" track of a conference (e.g., "Operations Research Letters". Usually these are shorter papers for this type of thing. Commented Dec 19, 2016 at 19:31

• 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.
• frobincate (sic.) was a new word to me. In case it is so to others as well, here's a reference. Commented Dec 18, 2016 at 13:14

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.

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.

• Some journals call them "short communications" as well. Commented Dec 19, 2016 at 8:02