Next: Two peculiar statistics Up: How to find the Previous: How is the compendium

How is the compendium used today?

The web version of the compendium on URL http://www.nada.kth.se/~viggo/problemlist/ was between June 1997 and May 1998 used about 30 times each day, and in each session about 8 web pages were accessed. During the year more than 4 000 users from 70 different countries around the world accessed the web compendium. This means that the compendium is used not only by researchers in the field, and probably it is used by non-researchers. 600 persons used it more that 10 times during the year.

Figure 1 shows how much the compendium has been used from different countries.

**Figure 1:** Use of the compendium by country.
$\begin{figure} \begin{center} \begin{picture} (275,185)(-32,-22) \put(0,-13){\ve... ...,1){4}}\put(200,-22){\makebox(0,0){20\%}} \end{picture}\end{center} \end{figure}$

There are links to the compendium from 400 domains. The most used links (50%) were from web indexes such as Altavista, InfoSeek, Yahoo, and Lycos. Except for the web indexes most used links were from www.nada.kth.se (domain of the compendium), www.ing.unlp.edu.ar (TSPBIB), and www.cs.pitt.edu (algorithm web page by Kirk Pruhs).

Table 1 shows the problems in the compendium that are most popular, that is, have been looked up most times. This might give an indication of which problems are hot. In the list we find several of the most basic NP-hard problems, but interestingly also MINIMUM LINEAR ARRANGEMENT and MINIMUM TRAVEL ROBOT LOCALIZATION. The least popular problems are shown in table 2.

**Table 1:** Most popular problems and the number of times they were looked up in a year.
GT1	MIN VERTEX COVER	891	SS1	MAX CONSTRAINED SEQUENCING...	370
ND1	MIN K-SPANNING TREE	514	GT23	MAX INDEPENDENT SET	365
GT5	MIN GRAPH COLORING	511	GP2	MIN TRAVEL ROBOT LOCALIZATION	347
ND32	MIN TRAVELING SALESPERSON	465	GP1	MIN GRAPH MOTION PLANNING	345
MP3	MAX PACKING IP	461	GT6	MAX ACHROMATIC NUMBER	338
GT2	MIN DOMINATING SET	439	ND33	MIN METRIC TSP	336
GT44	MIN LINEAR ARRANGEMENT	434	LO1	MAX SATISFIABILITY	321
SP4	MIN SET COVER	423	SR1	MIN BIN PACKING	320
GT22	MAX CLIQUE	419	ND2	MIN DEGREE SPANNING TREE	312
ND8	MIN STEINER TREE	401	LO11	MIN EQUIVALENCE DELETION	308

**Table 2:** Least popular problems.
ND58	MIN DIAMETERS DECOMPOSITION	62	MP11	MIN UNSATISFYING LINEAR SUBSYSTEM	76
ND59	MAX K-FACILITY DISPERSION	65	MP17	MIN BLOCK-ANGULAR CONVEX PROG.	77
SR8	MAX COMMON POINT SET	73	ND62	MIN K-SWITCHING NETWORK	78
MS7	MIN K-LINK PATH IN A POLYGON	73	MP12	MAX HYPERPLANE CONSISTENCY	81
ND65	MIN SEPARATING SUBDIVISION	75	MS8	MIN SIZE ULTRAMETRIC TREE	81

Next: Two peculiar statistics Up: How to find the Previous: How is the compendium

Viggo Kann
1998-10-31