I was trying to do a little background reading on a problem in complexity theory (this problem, to be precise), and I was dismayed to find myself thwarted by the unavailability of papers. Not being an academic type, I don’t have ready access to a research library. (I can, in theory, get papers from my local public library via inter-library loan, but it takes a couple of weeks. I can also drive to the nearest university that has a CS graduate program, but I’m not going to count that as “ready access”.) So I depend upon papers being available online, and a lot of researchers are very obliging in this regard. However, there are still a lot of exceptions.
For example, Richard Karp’s 1972 paper “Reducibility among combinatorial problems”  does not seem to be online. (By the way, it is of course possible that this or any the subsequent papers I mention are in fact online but I wasn’t thorough enough in my searches. Please let me know if this is the case.) This paper is mainly of historical interest at this point, but it was such an important paper that I’m really surprised by its absence.
Moving forward in time 16 years to 1988, we have another highly cited paper, “How easy is local search?” by Johnson, Papadimitriou and Yannakakis . Again, given how many citations this paper has, I’m surprised no one has been moved to scan it and put it online. (Well, actually, someone has, and I’ll get to that in a moment.)
Going forward another 4 years to 1992 takes us to Woeginger and Yu’s paper “On the equal-subset-sum problem” . Here we’re starting to get recent enough that the authors might still have the source versions of the paper in electronic form. Not to pick on anyone (especially since I’m a fan of his P vs. NP page), but why doesn’t Woeginger include this paper on his publications page?
Finally, for a recent example, we jump forward 11 years to 2003 for a paper by Kellerer, Mansini, Pferschy and Speranza . Given the recent date of this paper I would have thought that it would be a matter of routine for the authors to upload a preprint of it to their web pages.
Out of a total of 9 papers I tried to locate online, I was unable to access 4 of them. The good news is that more than half of the papers were in fact freely available on the web. The bad news is the following: with the exception of the Karp paper, the others are in fact online and they’re for sale at Elsevier’s ScienceDirect. Now, I have nothing against capitalism, and I actually think it’s great that these articles are available for sale on an individual basis. But Elsevier charges $30 per article, and that is a bit steep for something that I might skim through once and then discard. Unfortunately, even after reading the abstracts it can be hard to tell which papers will turn out to be worth the expense and which ones won’t.
So, my simple request is that researchers take the time to upload papers to their web pages. I’m not sure what kinds of legal issues might be involved, but some of the articles that I did find online were also published in Elsevier journals, so I don’t think that copyright concerns are the main impediment. It may be more just a matter of developing the right mindset. So get those papers out there, and students and hobbyists everywhere will be grateful. (If copyright issues are the main problem, I’d like to hear more about that, too.)
1. D.S. Johnson, C.H. Papadimitriou and M. Yannakakis, How easy is local search?, J. Comput. System Sci. 37 (1988) 79-100.
2. R.M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, R.E. Miller and J.W. Thatcher (eds.), Plenum Press, New York (1972), 85-104.
3. H. Kellerer, R. Mansini, U. Pferschy and M.G. Speranza, An efficient fully polynomial approximation scheme for the Subset-Sum Problem, J. Comput. System Sci. 66 (2003) 349-370.
4. G.J. Woeginger and Z.L. Yu, On the equal-subset-sum problem, Inform. Proc. Letters 42 (1992) 299-302.
Evidently Shiva Kintali would also like to see more papers uploaded to their authors’ web pages, and he would like to see it done really, really quickly!
Commenter BarrosH pointed out to me that Karp’s paper can in fact be found online, at Papadimitriou’s Reading the Classics course.