Problem Based Benchmark Suite (2020)

Set Cover (SC):

The (unweighted) set cover problem is: given a set of sets S to find a minimum sized subset T of S such that the union of elements in T contains all elements in the union of elements in S (i.e. T covers all the elements covered by S). The set cover problem is NP hard and this benchmark is to find an approximate minimum sized set cover. The maximum allowed size of the returned set cover is specified as part of the data specification.

Input and Output Format

The input is represented as a bipartite graph in the in the adjacency graph format. Each vertex represents a set and the integers included in each adjacency list are the elements the set covers. Let m be the maximum element label in any of these adjacency lists. Not all integers between 0 and m need to be in a set, although it is assumed that the element labels are relatively dense. The output is a sequence of integers corresponding to the sets included in the set cover (0 based). The output needs to be in the sequence format. The vertex indices need not be sorted in the output.

Distributions

Each distribution should be run for n=10,000,000. The weights used for average time are given in parentheses (all equal).

• (1) Random local graph with approximately 10 edges per vertex. This graph is generated so that the probability of each edge out of a vertex is biased to nearby vertices.

  randLocalGraph -j -d 3 -m <5*n> <n> <filename>
  

• (1) An RMAT graph with parameters (.3,.1,.1,.5) and about 5n edges.

  rMatGraph -j -a .5 -b .1 -m <5*n> <n> <filename>
  

• (1) A 3 dimensional grid.

  gridGraph -j -d 3 <n> <filename>