Is there some book or other reference that I can cite as a catalog of NP-complete problems, more up-to-date than the appendix of Garey&Johnson's book? I don't want to cite web sites, even though I know there are some excellent compendiums om the web.
$\begingroup$
$\endgroup$
3
-
3$\begingroup$ For individual results, it is better to cite the original article than to cite a book or a webpage which gathers many related results. $\endgroup$– Tsuyoshi ItoCommented Apr 3, 2011 at 20:19
-
2$\begingroup$ Or you can cite a survey paper (if it exists) on a particular subject, for example "A survey of NP-complete puzzles" (cs.wmich.edu/~elise/courses/cs431/icga2008.pdf) $\endgroup$– Marzio De BiasiCommented Apr 3, 2011 at 21:11
-
$\begingroup$ I'd like to point the reader to "more NP-complex problems", not being specific -- so I think the book by Ausiello and others seems like a good option. I'll also cite the survey papers, of course! $\endgroup$– JayCommented Apr 3, 2011 at 22:17
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
5
The book http://www.csc.kth.se/~viggo/approxbook/ on which the site http://www.csc.kth.se/~viggo/wwwcompendium/ is based.
answered Apr 3, 2011 at 20:15
-
1$\begingroup$ I took a look at the site and the G&J's book still rules; for example "games and puzzles": G&J 15 problems, csc.kth.se 2 problems; "Automata and language theory": G&J 21 problems, csc.kth.se 5 problems. $\endgroup$ Commented Apr 3, 2011 at 20:54
-
3$\begingroup$ because not all decision problems have natural approximation variants. $\endgroup$ Commented Apr 3, 2011 at 21:49
-
$\begingroup$ @Suresh: you're right, I completely missed the "about the approximate solution of NP-hard combinatorial optimization problems" of the book (I only gave a fast look at the list). $\endgroup$ Commented Apr 3, 2011 at 22:58
-
$\begingroup$ Thanks a lot -- now I can cite both G&J and this book (I knew their online compendium, but I didn't know it had become a book). $\endgroup$– JayCommented Apr 4, 2011 at 10:55
-
$\begingroup$ At least web compendium is not update and I think it's age is around G&J book age, for example sparsest cut problem, I think in 1986 proved that it is NP-Hard, but this compendium doesn't mentioned it. $\endgroup$– SaeedCommented Dec 7, 2011 at 19:48
$\begingroup$
$\endgroup$
There is "Encyclopedia of Algorithms" from 2008, which surveys a lot of different problems (1160 pages of it)
http://www.springer.com/computer/theoretical+computer+science/book/978-0-387-30770-1
$\begingroup$
$\endgroup$
2
I know you want book, but I think in this case Wiki is good, You can download it with depth 2 to have list of problems and their definition, Also I think Gary and Johnson book is good enough to be familiar with problems, after that you just should find your interest and work on it, there is no need to know all problems and their solution. Also reading first papers of your interest problem is good, you can find what was the first idea, after that may be solutions become better, and in books you will find best solution not philosophy of solution.
Also there are some new problems like matroid secretary See this, and I think this new problems (and newer) just available on web and papers not books.
-
$\begingroup$ It looks like that list has less than 100 problems, so much less than the Viggo Compendium mentioned in other answers... $\endgroup$ Commented Dec 4, 2013 at 20:14
-
$\begingroup$ @einpoklum, I count the number of general problems in wiki link, it's slightly bigger than 100, also many of them have many varitions and because of this I suggested to download in depth two. And more important than this two is wiki is open and can be edited and updated by new generation of problems, the main reason that I mention it is this. Finally I doubt that in usual compendiom anyone write about hardness of some interesting games like tetris, mario, ... which are mentioned in wiki. (I mean quantity does not mean domination). $\endgroup$– SaeedCommented Dec 4, 2013 at 23:41