31

Suppose I came across a problem, say in graph theory, that I need to solve for my application, or a problem that I just created out of the blue. I find that it is not a standard problem by any means. Also, it may not have many applications. I then solve this problem with some algorithm. The algorithm is non-trivial. My questions are:

  1. Is it possible to publish such algorithms?
  2. Does it even make sense to publish it? Since it may not even have any applications. And if it did, it is likely that other people have solved the same problem for their respective applications without ever publishing it.

I am sorry if such speculative questions should not be asked here, but I was curious. Thanks!

  • 8
    It sounds like it has one application. – Dave Clarke Oct 29 '12 at 16:48
  • If you're not aware, look into the Association of Computing Machines (ACM). – New Alexandria Oct 29 '12 at 19:36
29

Is it possible to publish such algorithms?

It's not only possible, it's far more common than the alternative. Most algorithms papers do not have real applications. The vast majority are motivated by applications, but there are usually several layers of abstraction and/or simplification between the problem actually solved and the motivating application. But even this "motivation" is often post-hoc rationalization, added by the authors to help draw the reader into their paper. Most people who study algorithms do it primarily because algorithms are cool, not primarily because they're useful.

Or maybe that's just me.

Does it even make sense to publish it?

In principle, sure! Of course, to be publishable, your algorithm needs to be both novel and interesting, not just to you, but to the algorithms community as a whole. You need to be sure that your problem hasn't been solved before, and in particular that your algorithm wasn't already discovered and published by someone else. You also need to sell the problem, the algorithm, or both; it's not enough for your algorithm to be "non-trivial".

I strongly recommend running your algorithm past a local algorithms expert, if possible. They may recognize your problem or your technique under a different guise. At a minimum, they should be able to help you start the necessary literature search.

Good luck!

  • I see. Thank you! You mention some good points. As for your point about applications being post-hoc rationalizations, I have done the same once when in university, but believed it was just me, even though they turned out to be genuine applications. – Paresh Oct 29 '12 at 17:54
  • 1
    Yeah, it's amazing how often those "applications" turn out to be real applications after all! – JeffE Oct 29 '12 at 21:28
  • 1
    If you needed to have a direct application to get published, most scientists would never acheive tenure! :) – Paul Dec 16 '12 at 19:00
26

I can't answer (1), but regarding (2), I definitely recommend publish.

I would venture that any individual academic is a moderate-to-poor judge of how useful their own research is in practice. While your situation may seem very specific, there may be more general applications that are not immediately apparent to you. Additionally, there's a non-trivial likelihood that someone else will encounter the same problem that you're currently trying to solve, in which case your work will be more useful. Just because you don't think someone will need it doesn't mean no one will :)

6

You should definitely consider publishing the algorithm, but not before you could say something more than merely a pseudocode.

You should start with a proper literature survey of relevant journals to check if the problem has really not been tackled elsewhere, even under a different avatar. If that is done, you could try building value to your algorithm by checking its complexity or by considering variants that could speed it up at the cost of some efficiency, maybe. You could then think about extensive simulations which could test and validate your algorithm. Finally you could conclude by thinking up some practical applications where it could be relevant.

The applications part sometimes may not be present, but it is perfectly acceptable for a paper to extend the theory alone, leaving it for future researchers to develop it appropriately.

  • Thank you! Yes, I realize just a pseudocode is not enough. And you bring up some good suggestions. – Paresh Oct 29 '12 at 17:58
4

You should publish it. History has shown that articles that have no real-life application at the time of their publication can have a real-world application identified in the indeterminate future. A good example is the prefix/postfix arithmetic operation format. When this was created, computers did not even exist (1920s), but 30 years later it was used by Djikstra and others for efficient in-memory representation of arithmetic operations in computers.

So, I repeat, do publish. Maybe someone uses it after you and I are dead, but it will still be useful.

4

I would say that it depends on the computational complexity you get out of it.

A naive implementation can always be made for any algorithm, but an algorithm with an efficient (or at least better-than-naive) complexity is always interesting, no matter if the problem it solves is very specific or not: a lot of algorithms are very specific, and generally the most efficient are very VERY specific, sometimes working for degenerate cases that nearly never happens in real life. Later on, somebody else can always enhance your algorithm, generalize it to other cases or build up on it to solve other related problems.

So my rule of thumb based on what I have read from algorithmics litterature:

  • if you can make an algorithm that solves a problem,
  • and the complexity is better than naive implementation (and, if you're not the first to solve this problem, possibly better than any other algorithm for the same problem under the same conditions),
  • and you can prove it (see Computational complexity theory),

Then go ahead and publish it, for example on arxiv.org or vixra.org which are free scientific papers pre-publishing services.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.