Observation from Calculus

Suppose n as a continuous variable, take function:

Differentiating with respect to nusing the formula given below:

Now, expanding the function by using formulae.

Where, which represents the higher order terms

So,

=differentiation and inequality showing together

Hence, monotonically increases in n and hence it is greater than 0.

[The function which increases monotonically are greater than 0 and the function which decreases monotonically are lesser than 0].

Consider the following modified algorithm of approximation scheme to find the smallest value not less than t.

APPROX-SUBSET-SUM (S,)

//copy the length of list into variable n

1.

//initialize the list by 0

2.

//for loop is used to traverse each element of list

3. for i= 1 to n

//MERGE- LIST function is used to sort the element of list

4.

// TRIM function is used to remove element from list L

5.

// for loop is used to check the value less than t

6. for j=1 to

//if statement is used for compression

7. if

//delete function is used for delete the element

8.

//store the first element of list into variable z

9.

//for loop is used to traverse each element of list

10. for k=1 to n

//if statement is used to check largest element in list

11. if

12. z =

//finally returns the largest element of list

13. return z

Analysis of Algorithm:

• In the first line of above algorithm copy the length of list into a variable n.

• In line 2^nd, initialize the variable by 0.

• ‘for’ loop in line 3-6 is used to compute the shortest list that contains a suitable trim value and remove element less than t.

• ‘if’ statement in line 7-8 is used to compare the element from t.

• In line 9 of the above algorithms initialize the variable z to store the first element of the list.

• ‘for’ loop in line 10-12 is used to display the maximum number from list.

• Finally in line 13 return the maximum value.

• In the above algorithm nested ‘for’ loop is use. Both the ‘for’ loop iterate maximum n time therefore the time complexity of above algorithm will be.

Modifying the APPROX-SUBSET-SUM procedure: Consider the algorithm APPROX-SUBSET-SUM algorithm in the section 35.5 of the textbook. Now, modifying the approximation scheme to find a value greater than t that is the sum of subset S’ of a list S by running the approximation algorithm. Then summing up the elements of the complement list S–S’ to find the final result.

APPROX-SUBSET-SUM (S, t, €)

// store the number of integers in set S

1.

// initializing the list with one element

2.

// execute the loop for all value of set

3. for i = 1 ton

// call the method MERGE-LISTS

4. L_i = MERGE-LISTS (L_i-1, L_i-1, x_i)

// trim the list by calling the procedure TRIM

5. L_i= TRIM (L_i, € / 2n)

// removing the elements larger that target t from the list

6. remove from L_i every element that is greater than t

// take the largest element from the list

7. let z^* be the largest value in L_n

// return the largest element from the list

8. return z^*

9. to find a value greater than t that is the sum of subset S’ of a list S run the below

algorithm for each list or subset of S.

APPROX-SUBSET-SUM (S’, t, €)

10. return sum the elements of the complement list S–S’

In the above algorithm first of all the number of set elements are counted and then stored in a temporary variable n. After that a list is initialized with a value zero then for each element of the set the algorithms MERGE-LIST and TRIM are called.

In the MERGE-LIST algorithm the list is merged with the elements that are resulted from adding the next element of the set with the elements of current list. After the merging of the lists the trimming of the list is performed in which the elements larger that the target value t are removed from the list. For the TRIM algorithm refer the section 35.5 from the textbook.

From the final list of element the largest value in is that is the value which is larger than anyother element of the set is selected which is returned in step 8. Now, for returning the sum of largest element of each subsets of S, call the same procedure for each subset list and return the sum of all the largest elements.

Hence, the above algorithm will also return the subset of S that sums to the value.

Illustration of algorithm:

Consider the example, and andthe trimming parameter for the algorithm is.The execution of approx. Subset algorithm is as for each subset. First of all listL is initialized in step 2 as:

Then in step 4 of the new element 103 is merged to the list:

In the step 5 of the algorithm the element are trimmed according to trim method.

In the step 6 of the algorithm the elements that are larger than the target t are removed from the list as:

Now, this process is repeated for all the other elements of the set S which is as shown:

Now, the largest element from the listis returned that is.

Now, the above algorithm gives the sum of all values and also uses the concept of polynomial time of subset sum algorithm concept (line 10). After checking the line 10 condition in above algorithm, sum operation is performed which gives the final output required.

Now, sum of.

Hence, the modified algorithm of approx. subset sum problem returns the subset of S that forms the sum to the value.