# Compendium of the Best Approximation and Hardness Results for NP optimization problems

Do you know any up-to-date wiki dedicated to NP optimization problems with their best approximation and hardness result?

Based on the feedback, it seems that it is safe to assume there is not such a resource (see the end of this question for two close options). -- added on Feb 8.

Since there is a huge body of results and problems introduced in the past two decades, existence of a dedicated wiki could be a great help for students and professionals working on subject of approximation algorithms and hardness of approximation.

I have been suggested to start a new wiki. I like the idea, but I need some feedback before starting:
Are you interested in a wiki devoted to the above subject and are you going to contribute something? What is your preferred format for this wiki (see my preferred format in comments)? Should we use a wiki farm or a wiki engine? In the latter case, what is your suggestion for a wiki engine? MediaWiki?

The two closest options that I am aware of, are:
1- "A compendium of NP optimization problems," edited by Pierluigi Crescenzi and Viggo Kann: This compendium seems to be out-of-date. I think the volume of current results cannot be managed by a few people and if we want an up-to-date list, we should have a wiki.
2- Wikipedia: This wiki is for general audience and you cannot have a short page just including problem description, and the best approximation and hardness result.

• I believe we can safely conclude that there is no such resource. – Jukka Suomela Feb 7 '11 at 23:07
• @Suresh I was thinking of a short page only containing problem description (i.e. instances, solutions, and the objective function) and the best approximation and hardness results with their respective assumptions and not containing history, motivation, algorithm description, etc. A page with this format is easier to create and you can find the most recent results faster than a wikipedia page. The compendium edited by Crescenzi and Kann fits this profile, but it is not a wiki and so, it's out-of-date. – Babak Behsaz Feb 8 '11 at 3:19
• you need something like the complexity zoo then. maybe you should start one and solicit volunteers from here to help populate it. – Suresh Venkat Feb 8 '11 at 5:42
• A wiki would be useful. However, I would think that it should be more than simply the problem and the best known result. The problem with this approach is that it will be mostly useful to theory people while a page with more information is likely to be useful to practitioners; one can talk about known special cases and related results etc. Why not make full use of links, comments, refs etc? – Chandra Chekuri Feb 9 '11 at 4:21
• No matter what you end up doing, I strongly recommend trying to establish links among results like the complexity zoo. It's useful to know that an improvement in approximation for problem X implies something for Y, and so on.. Also, David Johnson's hierarchy of hardness assumptions (in a recent column) is something that should be there too. – Suresh Venkat Feb 14 '11 at 19:42

When you refer to the Crescenzi-Kann compendium, I'm not sure if you're referring to the book or the website. The book is out of date but the authors try to keep the website continuously updated. It would seem that the logical starting point is to approach Crescenzi and Kann with your proposal.

• It is good to know that the authors are willing to keep the website continuously updated. I had an impression that they stopped updating in March 2000 because most pages say that they were last updated on 2000-03-20. – Tsuyoshi Ito Feb 9 '11 at 19:34
• I'm referring to the website. I am not sure if they are editing it actively anymore. I myself remember reporting an improvement on approximation ratio of a problem, but they didn't update it. Anyways, I agree it's logical to contact Crescenzi and Kann regarding the status of their compendium and possibility of changing it to a wiki. – Babak Behsaz Feb 9 '11 at 20:54
• @Suresh @Anthony @Florent @Tsuyoshi @Jukka @Gianluca: I couldn't find contact information of (Dr.?) Pierluigi Crescenzi. So, I sent an email to professor Kann on Feb 9 and didn't receive an answer. On Feb 16, I forwarded my previous email to subeditors of compendium Professors Karpinski and Woeginger, but again I didn't receive an answer. I sent both emails with my academic email address, so I guess they haven't ended up in their spam folders. What's your suggestion now? – Babak Behsaz Feb 28 '11 at 21:34
• I guess then a new wiki could be started. If at some point the authors of the original compendium complain about it, a solution will be found easily (e.g. merging the two existing resources) – Florent Foucaud Apr 11 '11 at 14:16
• @Babak : In case you are still interested, you can find Prof. Crescenzi's email here – Gianluca Della Vedova Jun 2 '11 at 15:41

Complexity Garden is a wiki devoted to computational problems and their relations to complexity classes. As suggested here, I was planning to a start a new wiki for the algorithmic results, but I thought when there is one wiki for computational problems, we can have all the information in one place. So, I contacted the Zoo people and with their permission, changed the scope of the Garden to include algorithmic results as well.

Now, I need a small group of people to help me populate the wiki to a size that we can publicly announce it and attract more contributors. As this wiki uses the same system as wikipedia, it takes 15-25 minutes on average to add a problem. So, even with a group of 5 people contributing just 3 problems a weak (i.e. around 1 hour per weak), we can add 60 problems in a month and have a total of 100 problems in the Complexity Garden.

• What is the status of your initiative? – Florent Foucaud Nov 2 '11 at 15:41
• I don't see any addition on that page after Aug 25, so I assume Babak got discouraged due to a lack of participants. I missed this announcement, and will try to contribute ASAP. – Anthony Labarre Nov 9 '11 at 14:26

Are you interested in a wiki devoted to the above subject

Yes, and I will definitely advertise for it!

and are you going to contribute something?

I'll contribute as much as possible, but don't expect me to be among the main content-providers. As Tsuyoshi Ito points out, this can get time-consuming, and I don't quite see myself as the most knowledgeable person in the area either (on this website or elsewhere).

But content will certainly eventually grow with the user base, so I don't think you should worry too much about having people committed to contributing e.g. 10 pages a day each.

What is your preferred format for this wiki (see my preferred format in comments)?

There's the question of how much content you want to provide and which audience(s) you target. If I want to find out whether my problem is hard, as I wrote above, it's good to have a quick overview of what looks like it as a list where the $i^{th}$ item would be:

Problem $i$

• Instance: ...
• Question: ...
• References: For hardness, see [i1], for inapproximability, see [i2], ...

Which is what Garey & Johnson's and Kann & Crescenzi use. Problems could also be tagged using categories as we see fit, so that a list of problems by category could be easily generated (kind of like on delicious: click the "graph-theory" tag, and see the list of every hard problem in graph theory on the website).

More detailed information could then be provided by clicking the name of the problem in the list, which would contain for instance a list of "easy" cases, open problems (e.g. "best approximation is 3/2, can we do better?") links to Wikipedia or others for a broader audience, specialised software, ...

You can also, as G&J did, provide information on how the results were obtained ("transformation from X3C"). And then you could probably generate a graph showing reductions among different problems, which would lead people to wonder if more direct proofs exist, but well... you have to stop somewhere ;-)

I'll skip the last sub-question because I have no idea how to answer it.

• I think starting a wiki doesn't need too much effort. You only need to configure a wiki engine (shouldn't be that difficult), write a main page, write a page about the mandatory format of pages and compose an example page (e.g. for the set cover problem). The rest can be done in the course of time. It may seem a little simplistic, but I think if there is enough interest from theory community, the problems will be solved in the course of time and the wiki will grow. – Babak Behsaz Feb 9 '11 at 20:10
• @Babak: I think that you definitely need real content to start off. This real content can be copy-and-paste of the compendium if the authors are happy about it. It is difficult to imagine that an empty box just with a system will attract users. – Tsuyoshi Ito Feb 9 '11 at 22:56
• @Ito I think at first the majority of users will be the ones that want to contribute to the wiki, not necessarily use it. I am not sure how many members of community like to contribute in this way, but I myself would have done this if there were an almost empty wiki. The point is that between two choices of not having a wiki or having an empty working system, which one is better. I think the latter is harmless. If we can find some people that want to put more effort on the wiki (e.g. copy compendium materials with permission), then that's great. – Babak Behsaz Feb 10 '11 at 5:34
• Copying (with permission) the content of the compendium should not be too much effort, and will be enough for a starting point. In fact why not propose the authors to transform the existing compendium into a wiki? – Florent Foucaud Feb 10 '11 at 10:40
• @Babak: I agree that an empty working system is harmless. I just want to maximize the probability of success. To do so, I believe that the real content is a key factor. I hope that the authors of the current compendium are willing to change it to a wiki. – Tsuyoshi Ito Feb 14 '11 at 14:38

Are you interested in a wiki devoted to the above subject and are you going to contribute something?

I am interested and I am willing to contribute, at least a little bit in my small domain of expertise. I don't really understand why you want to restrict your attention to approximation. For instance there is also an outdated Compendium of Parameterized Problems devoted to Fixed-parameter algorithms.

Also, the last portion of G&J can be seen as a NP-hardness compendium.

IMHO, you should think about a Computational Problems Compendium where, for each problem, you state the most relevant (good or bad) results.

What is your preferred format for this wiki (see my preferred format in comments)?

I fully agree with the format proposed in Anthony Labarre's reply.

Should we use a wiki farm or a wiki engine?

I have a slight preference for a self-hosted wiki, but a hosted wiki would be fine.

My only suggestion is that, in case you choose a wiki farm, be sure to be able to export all data. You cannot be sure that the farm will be shut down some day.

In the latter case, what is your suggestion for a wiki engine? MediaWiki?

IMHO a requirement is to choose an engine supporting LaTeX format. Mediawiki and Dokuwiki are the most widespread and are both excellent choices.

Mediawiki is a bit more complex to install and manage (I would say moderately complex) but its syntax is likely to be familiar to most would-be contributors.

Dokuwiki is more lightweight (in both resources needed and management effort) but the syntax is partly different from Mediawiki's.