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.

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