Search code examples
algorithmapproximation

approximation algorithm for optimization version of partitioning?

in optimization version of partitioning problem we want to partition set X to disjoint subset A and B such that max(sum(A),sum(B)) be minimal.A approximation algorithm has been suggested in wikipedia, but I can't understand why this approximation is 4/3.

Solution 
  • OPT >= sum(all)/2

    consider that the greedy algorithm give you some answer like S1 and S2 where:

    max(sum(S1), sum(S2)) > 4/3 OPT

    (without losing generality assume sum(S1) > sum(S2)) so we have :

    sum(S1) > 4/3 OPT >= 2 sum(all)/3

    so :

    sum(S1) > 4/3 OPT >= 2 sum(all)/3 so sum(S1) > 2 sum(all)/3

    so :

    sum(S1) > 2 sum(S2)

    So in one of the steps of algorithm when sum(S1) was smaller than sum(S2) you must add an element like A to S1 and after that you didnt add any element to S1

    So A must be bigger than final state of sum(S2) (because A + sum(S1) > 2 sum(S2))

    so A is bigger than current state sum(S1) (because current state of sum(S1) < current state of sum(S2) < final state of sum(S1) < A )

    And your list is sorted in descending order, so A must be the first element in the sorted list(biggest element). so your s1 must just contain A and you have.

    also you know that the sum(OPT) >= A because either it contains A or the other part contains A but sum(OPT) is bigger that sum of other parts element so 

    sum(OPT) > A

    but you have :

    A = sum(S1) > 4/3 sum(OPT) > sum(OPT) > A

    and it is a contradiction :)