<p>When you refer to the Crescenzi-Kann compendium, I'm not sure if you're referring to the book or the <a href="http://www.csc.kth.se/~viggo/wwwcompendium/">website</a>.  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.</p>

CC BY-SA 3.0
2011-04-11T14:16:07.740Z
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
CC BY-SA 3.0
2011-06-02T15:41:50.793Z
@Babak : In case you are still interested, you can find Prof. Crescenzi's email [here](http://www.unifi.it/dpsinf/CMpro-v-p-17.html)
Gianluca Della Vedova
CC BY-SA 2.5
2011-02-09T19:34:48.800Z
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
CC BY-SA 2.5
2011-02-09T20:54:01.663Z
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.
randomizer
CC BY-SA 2.5
2011-02-28T21:34:09.873Z
@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?
randomizer
CC BY-SA 2.5
2011-02-09T19:04:01.040Z
2011-02-09T19:04:01.040Z
Timothy Chow
<p><a href="https://complexityzoo.net/Complexity_Garden" rel="nofollow noreferrer">Complexity Garden</a> is a wiki devoted to <em>computational problems</em> 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.</p>
<p>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 week (i.e. around 1 hour per week), we can add 60 problems in a month and have a total of 100 problems in the Complexity Garden.</p>

CC BY-SA 3.0
2011-11-02T15:41:27.253Z
What is the status of your initiative?
Florent Foucaud
CC BY-SA 3.0
2011-11-09T14:26:24.580Z
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
CC BY-SA 4.0
2011-08-25T16:14:22.267Z
2023-09-12T16:23:20.843Z
2023-09-12T16:23:20.843Z
randomizer
<blockquote>
  <p>Are you interested in a wiki devoted
  to the above subject and are you going
  to contribute something?</p>
</blockquote>

<p>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 <a href="http://www.sprg.uniroma2.it/home/cesati/research/compendium/" rel="nofollow">Compendium of Parameterized Problems</a> devoted to Fixed-parameter algorithms.</p>

<p>Also, the last portion of G&amp;J can be seen as a NP-hardness compendium.</p>

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

<blockquote>
  <p>What is your preferred format for this
  wiki (see my preferred format in
  comments)?</p>
</blockquote>

<p>I fully agree with the format proposed in Anthony Labarre's reply.</p>

<blockquote>
  <p>Should we use a wiki farm or a wiki
  engine?</p>
</blockquote>

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

<p>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.</p>

<blockquote>
  <p>In the latter case, what is your suggestion for a wiki engine? MediaWiki?</p>
</blockquote>

<p>IMHO a requirement is to choose an engine supporting LaTeX format.
Mediawiki and <a href="http://Dokuwiki.org" rel="nofollow" title="Dokuwiki">Dokuwiki</a> are the most widespread and are both excellent choices.</p>

<p>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.</p>

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

CC BY-SA 2.5
2011-02-14T14:14:15.450Z
2011-02-14T14:14:15.450Z
Gianluca Della Vedova
<blockquote>
  <p>Are you interested in a wiki devoted to the above subject </p>
</blockquote>

<p>Yes, and I will definitely advertise for it!</p>

<blockquote>
  <p>and are you going to contribute something? </p>
</blockquote>

<p>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).</p>

<p>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.</p>

<blockquote>
  <p>What is your preferred format for this wiki (see my preferred format in comments)?</p>
</blockquote>

<p>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:</p>

<p><strong>Problem $i$</strong></p>

<ul>
<li><em>Instance:</em> ...</li>
<li><em>Question:</em> ...</li>
<li><em>References:</em> For hardness, see [i1], for inapproximability, see [i2], ...</li>
</ul>

<p>Which is what Garey &amp; Johnson's and Kann &amp; 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).</p>

<p>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, ...</p>

<p>You can also, as G&amp;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 ;-)</p>

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

CC BY-SA 2.5
2011-02-09T20:10:43.353Z
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.
randomizer
CC BY-SA 2.5
2011-02-09T22:56:45.643Z
@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
CC BY-SA 2.5
2011-02-10T05:34:32.280Z
@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.
randomizer
CC BY-SA 2.5
2011-02-10T10:40:13.823Z
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
CC BY-SA 2.5
2011-02-10T21:21:06.747Z
I sent an email to professor Kann yesterday regarding the status of their compendium. Actually, one of my questions was that if they want to change their compendium to a wiki.
randomizer
CC BY-SA 2.5
2011-02-14T14:38:54.093Z
@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
CC BY-SA 2.5
2011-02-09T15:50:39.000Z
2011-02-09T15:50:39.000Z
Anthony Labarre
<p><strong>Do you know any up-to-date wiki dedicated to NP optimization problems with their best approximation and hardness result?</strong></p>
<p>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.</p>
<p>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.</p>
<p>I have been suggested to start a new wiki. I like the idea, but I need some feedback before starting:<br />
<strong>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?</strong></p>
<p>The two closest options that I am aware of, are:<br />
1- &quot;A compendium of NP optimization problems,&quot; 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.<br />
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.</p>

CC BY-SA 2.5
2011-02-07T23:07:53.187Z
I believe we can safely conclude that there is no such resource.
Jukka Suomela
CC BY-SA 2.5
2011-02-08T00:01:31.810Z
Not sure why the results can't be folded into wikipedia
Suresh Venkat
CC BY-SA 2.5
2011-02-08T03:19:13.820Z
@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.
randomizer
CC BY-SA 2.5
2011-02-08T05:42:49.250Z
you need something like the complexity zoo then. maybe you should start one and solicit volunteers from here to help populate it.
Suresh Venkat
CC BY-SA 2.5
2011-02-08T08:40:20.757Z
Great idea, Suresh. I hope to see that happen.
Anthony Labarre
CC BY-SA 2.5
2011-02-08T17:05:26.853Z
Made this post community wiki, as seems fit.
Dave Clarke
CC BY-SA 2.5
2011-02-08T20:20:20.413Z
I would be interested in such a wiki too. What about this wiki to also contain NP _decision_ problems (or does such a wiki already exist)?
Florent Foucaud
CC BY-SA 2.5
2011-02-08T21:02:59.240Z
Perhaps this post can be the wiki, like the question "algorithms from the book" http://cstheory.stackexchange.com/questions/189/algorithms-from-the-book?  You'll have to rephrase the question, but I don't see any big difficulty.  Would that be appropriate?
Lev Reyzin
CC BY-SA 2.5
2011-02-08T23:55:21.980Z
I am interested in _using_ the wiki like the one you proposed if it is good enough.  But to be honest, I am not much interested in _contributing_ to it because it will be a time-consuming task.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-09T04:21:46.277Z
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
CC BY-SA 2.5
2011-02-09T15:53:17.170Z
@Lev Reyzin: I think the list will quickly grow to the point where the content will be unmanageable on a page of this kind. And even if the data is here, it will not be sorted in any way -- except using votes, but why would we vote answers up or down in this particular case?
Anthony Labarre
CC BY-SA 2.5
2011-02-09T16:19:02.713Z
I'm not sure if this kind of resource can be created without significant initial effort from a *small* set of core contributors. I guess the simplest way to bootstrap the project would be: (1) A small group of people writes a survey/handbook and sets up a wiki site that supports it. (2) After that, the community can update the wiki.
Jukka Suomela
CC BY-SA 2.5
2011-02-09T17:00:08.483Z
@Jukka: I do not agree that starting a wiki as a support content of another resource is the simplest way.  But I agree that significant initial effort from a small set of core contributors is probably needed for this kind of resource to succeed.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-09T17:05:15.510Z
@Tsuyoshi: The problem is that merely setting up a wiki does not add much to your CV. Who has time and energy for something like that? There are no deadlines and no incentives; is it ever going to be finished? On the other hand, writing a survey or handbook looks *very* good on your CV, and if you can use it as an excuse to set up the wiki site, even better. CV optimisation shouldn't matter, but unfortunately we happen to live in the real world, and people will worry about tenures, etc.
Jukka Suomela
CC BY-SA 2.5
2011-02-09T17:28:06.850Z
@Jukka: I see the point, and now I agree.  Thank you for the explanation.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-09T19:48:37.687Z
@Chandra I can see your point, but the main idea behind short pages is to help theory people find the most recent results easy and can contribute easily (e.g. add a page on a problem with a few (incomplete) sentences in a few minutes). To consider your point, we can enforce a short mandatory format and then, we can have a optional additional info section providing the kind of information that practitioners are interested in. Whoever wants to add more info can add to this optional section. @Jukka Regarding amount of effort, see my comment on Anthony's answer below.
randomizer
CC BY-SA 2.5
2011-02-14T19:42:48.523Z
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
CC BY-SA 3.0
2011-09-06T06:01:12.793Z
Babak you can accept your own answer if you want, that will make it to be shown on top of the other answers.
Kaveh
<ds.algorithms><reference-request><approximation-algorithms><approximation-hardness>
Compendium of the Best Approximation and Hardness Results for NP optimization problems
randomizer
# Compendium of the Best Approximation and Hardness Results for NP optimization problems

(Asked by: username_0 on 2011-02-07)

**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.

**Tags:** ds.algorithms, reference-request, approximation-algorithms, approximation-hardness
> **Comments:**
> **username_1**: I believe we can safely conclude that there is no such resource.  
> **username_2**: Not sure why the results can't be folded into wikipedia  
> **username_0**: @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.  
> **username_2**: you need something like the complexity zoo then. maybe you should start one and solicit volunteers from here to help populate it.  
> **username_3**: Great idea, Suresh. I hope to see that happen.  
> **username_4**: Made this post community wiki, as seems fit.  
> **username_5**: I would be interested in such a wiki too. What about this wiki to also contain NP _decision_ problems (or does such a wiki already exist)?  
> **username_6**: Perhaps this post can be the wiki, like the question "algorithms from the book" http://cstheory.stackexchange.com/questions/189/algorithms-from-the-book?  You'll have to rephrase the question, but I don't see any big difficulty.  Would that be appropriate?  
> **username_7**: I am interested in _using_ the wiki like the one you proposed if it is good enough.  But to be honest, I am not much interested in _contributing_ to it because it will be a time-consuming task.  
> **username_8**: 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?  
> **username_3**: @Lev Reyzin: I think the list will quickly grow to the point where the content will be unmanageable on a page of this kind. And even if the data is here, it will not be sorted in any way -- except using votes, but why would we vote answers up or down in this particular case?  
> **username_1**: I'm not sure if this kind of resource can be created without significant initial effort from a *small* set of core contributors. I guess the simplest way to bootstrap the project would be: (1) A small group of people writes a survey/handbook and sets up a wiki site that supports it. (2) After that, the community can update the wiki.  
> **username_7**: @Jukka: I do not agree that starting a wiki as a support content of another resource is the simplest way.  But I agree that significant initial effort from a small set of core contributors is probably needed for this kind of resource to succeed.  
> **username_1**: @Tsuyoshi: The problem is that merely setting up a wiki does not add much to your CV. Who has time and energy for something like that? There are no deadlines and no incentives; is it ever going to be finished? On the other hand, writing a survey or handbook looks *very* good on your CV, and if you can use it as an excuse to set up the wiki site, even better. CV optimisation shouldn't matter, but unfortunately we happen to live in the real world, and people will worry about tenures, etc.  
> **username_7**: @Jukka: I see the point, and now I agree.  Thank you for the explanation.  
> **username_0**: @Chandra I can see your point, but the main idea behind short pages is to help theory people find the most recent results easy and can contribute easily (e.g. add a page on a problem with a few (incomplete) sentences in a few minutes). To consider your point, we can enforce a short mandatory format and then, we can have a optional additional info section providing the kind of information that practitioners are interested in. Whoever wants to add more info can add to this optional section. @Jukka Regarding amount of effort, see my comment on Anthony's answer below.  
> **username_2**: 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.  
> **username_9**: Babak you can accept your own answer if you want, that will make it to be shown on top of the other answers.  

---

## 4 answers

### Answer by username_10 on 2011-02-09. Score: 9

When you refer to the Crescenzi-Kann compendium, I'm not sure if you're referring to the book or the [website](http://www.csc.kth.se/~viggo/wwwcompendium/). 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.

> **Comments:**
> **username_7**: 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.  
> **username_0**: 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.  
> **username_0**: @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?  
> **username_5**: 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)  
> **username_11**: @Babak : In case you are still interested, you can find Prof. Crescenzi's email [here](http://www.unifi.it/dpsinf/CMpro-v-p-17.html)  

---

### Answer by username_0 on 2011-08-25. Score: 8

[Complexity Garden](https://complexityzoo.net/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 week (i.e. around 1 hour per week), we can add 60 problems in a month and have a total of 100 problems in the Complexity Garden.

> **Comments:**
> **username_5**: What is the status of your initiative?  
> **username_3**: 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.  

---

### Answer by username_11 on 2011-02-14. Score: 1

> 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](http://www.sprg.uniroma2.it/home/cesati/research/compendium/) 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](http://Dokuwiki.org "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.


---

### Answer by username_3 on 2011-02-09. Score: 1

> 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.

> **Comments:**
> **username_0**: 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.  
> **username_7**: @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.  
> **username_0**: @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.  
> **username_5**: 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?  
> **username_0**: I sent an email to professor Kann yesterday regarding the status of their compendium. Actually, one of my questions was that if they want to change their compendium to a wiki.  
> **username_7**: @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.  

---

