## 3 The Static Form of the Problem
### Scalability and Error Analysis  
#### 3.3.1 Scalability  
We use [PERSON]'s random graph model [20] to randomly generate test coding graphs. This model generates graphs by \(G(N,p)\), where \(N\) denotes the number of vertices and \(p\) denotes the probability by which each edge is selected. For each set of parameters, we generate 25 random graphs and test our algorithm, as well as a non-approximation algorithm (NA). Though the number 25 is chosen arbitrarily, it turns out to be sufficient to demonstrate the performance differences. The non-approximation algorithm also has the feature of pruning unnecessary branches, but it does not quantize total weights into blocks. Therefore, it needs to consider a lot more branches when no pruning rule is applicable, but the solution it provides is an accurate answer.  
Since WCCP solves the problem on a weighted graph, weight information should be attached to the randomly generated graphs. In this evaluation, we set the weights assigned to each vertex to be a random variable conforming to a log-normal distribution. Log-normal distribution is chosen, because it is the simplest yet practical distribution for real-life variables with positive values, finite mean and finite variance. By adjusting the mean and standard deviation of this log-normal distribution, we are able to test the algorithm with different scales of weights. The _Colt_ ([[http://acs.lbl.gov/ACSSoftware/colt/](http://acs.lbl.gov/ACSSoftware/colt/)]([http://acs.lbl.gov/ACSSoftware/colt/](http://acs.lbl.gov/ACSSoftware/colt/))) library is the back-end for the random number generator.  
The setting of the simulation environment is as follows: Intel i5-3570 3.40 GHz, 8 GB memory, Windows 7 Enterprise 64-bit SP1. Because some of the test graphs are so complicated that it is impractical to wait so long for the result, we take a different approach to measure the run time when the program has been running for too long. We keep track of the amount of search tasks in the program. When the program has run for 10 min and is still running, we estimate the total run time by dividing 10 min by the proportion that has finished searching. We have tested the validity of this approach for some of the scenarios when the estimation is above 10 min but below two hours; the estimation error is generally within 20%. Since we are more concerned about the order of magnitude instead of the absolute value, this error is acceptable. In addition, even though the 25 graphs are generated using the same set of parameters, their processing times can span from milliseconds to days or more. In order to capture this distribution, we take the median value among these 25 values and draw the figures.  
The baseline scenario is set with the parameters shown in Table 1. This baseline is chosen after weighing two factors. Firstly, we want the scenario to be of some complexity. However, secondly, we want to keep the size of the maximum clique as smaller than six. This number is worked out in [19] as the theoretical maximum clique size in a coding graph. By setting the probability of generating a six-node clique as 5%, we have worked out the baseline parameters. Then, we evaluate the performance of the algorithm by adjusting each single parameter. Note that the ratio between the mean and the standard deviation is fixed at 2:1 for the log-normal distribution. Figures 3 and 4 show that: (1) the processing time grows for both algorithms when the size of the problem grows; (2) our algorithm consistently runs faster than the non-approximation algorithm; and (3) the improvement (as big as several orders of magnitude) is most significant when the scale of the problem is big. Figure 5 measures the performance with different mean weights. It is clear that our algorithm is roughly invariant on the weight factor, while the non-approximation algorithm grows exponentially with the mean weights.