Approximation Algorithm Programs

This directory demonstrates solutions to various NP-hard and NP-complete problems, written in C.

Knapsack Problem (FPTAS)

Instructions to run:

1. In the /knapsack directory, enter "make" into the command line to create the executable.
2. Type "./knapsack" and then press ENTER.
3. Type each line of data, delimited by a space, and press ENTER after each line. Data should be entered as follows:
   1. The first line should contain the profits for each item, delimited by a space.
   2. The second line should contain the sizes for each item, delimited by a space. Line 2 should contain the same number of items as Line 1.
   3. The third line should contain the capacity of the knapsack as a single integer.
   4. Finally, the fourth line should contain the value for epsilon, a decimal greater than 0 and less than 1 that sets the approximation factor for the algorithm.
4. Once the fourth line is entered and ENTER is pressed, the program will begin.

EXAMPLE:

For a problem where 5 items have profits of 4, 20, 12, 12, and 2, and sizes of 2, 7, 4, 4, and 1, respectively, the knapsack has a capacity of 9, and epsilon is 0.5, the four lines inputted would be:

1. 4 20 12 12 2
2. 2 7 4 4 1
3. 9
4. 0.5

Set Cover Problem (Primal-Dual Schema)

Instruction to run:

1. In the /setcover directory, enter "make" into the command line to create the executable.
2. Type "./setcover" and then press ENTER.
3. Type each line of data, delimited by a space, and press ENTER after each line. One line should be entered for each set in the problem, starting with the cost of the set, a space, and then each element in the set, delimited by a space.
4. Once each set's data has been entered into a line, type "0" in the final line and press ENTER to begin the program.

EXAMPLE:

For a problem with sets {a,b}, {a,c,d}, {b,d,e}, and {a,b,e}, and costs of 2, 4, 3, and 3, respectively, the lines inputted would be:

1. 2 a b
2. 4 a c d
3. 3 b d e
4. 3 a b e
5. 0