Log In
5 votes
Consider the following problem. Given $n$ positive integers $a_{1}, a_{2}\dots a_n,$ it is required to partition them in to two parts $A$ and $B$ such that

$|\sum_{i \in A} a_{i} - \sum_{i \in B} a_{i}|$ is minimised

Consider a greedy algorithm for solving this problem. The numbers are ordered so that $a_{1} \geq a_{2} \geq \dots a_{n},$ and at $i^{th}$ step, $a_i$ is placed in that part whose sum in smaller at that step. Give an example with $n=5$ for which the solution produced by the greedy algorithm is not optimal.
in Algorithms 543 views
This is the partition problem which is NP-Complete. The greedy algorithm would be selecting the elements in reverse order and in alternating fashion distributing them in a and b. This is an approximation algorithm.

1 Answer

6 votes

Let $S = \{12,11,8,8,8\}$

As per the given greedy algorithm we get $A = \{12,8 \}$ and $B = \{11,8,8\}$ and $|\sum_{i \in A} a_{i} - \sum_{i \in B} a_{i}| = |20 - 27| = 7.$ 

This is not minimal because if we partition $S$ as $A = \{12,11\}$ and $B = \{8,8,8\}$ we get $|\sum_{i \in A} a_{i} - \sum_{i \in B} a_{i}| = |23 - 24| = 1.$ 

Thus greedy algorithm fails for this example.

Working algorithm: 

Ordered in decreasing order
My mistake. You're right!

I'll delete my comment


at $i^{th}$ step, $a_i$ is placed in that part whose sum in smaller at that step.

This is what is means by the above-quoted line$?$

$12\Rightarrow set_1,$ $set_1=\{12\}$

$11\Rightarrow set_2,$ $set_2=\{11\}$

$8\Rightarrow set_2,$ $set_2=\{11,8\}$

$8\Rightarrow set_1,$ $set_1=\{12,8\}$

$8\Rightarrow set_2,$ $set_2=\{11,8,8\}$

$set_1=\{12,8\}$  $set_2=\{11,8,8\}$

Related questions

7 votes
1 answer
18 votes
2 answers
Express $T(n)$ in terms of the harmonic number $H_{n}= \sum_{t=1}^{n} 1/i, n \geq 1$, where $T(n)$ satisfies the recurrence relation, $T(n)=\frac{n+1}{n} T(n - 1)+1$, for $n \geq \sum$ and $T(1) = 1$ What is the asymptotic behaviour of $T(n)$ as a function of $n$ ?
asked Nov 27, 2016 in Algorithms makhdoom ghaya 1.5k views
0 votes
0 answers
Consider the following instance of the $0 -1$ Knapsack problem: $\max 6X_{1} + 11X_{2} + 16X_{3} + 21X_{4} + 26X_{5}$ Subject to $4X_{1} + 8X_{2} + 12X_{3} + 16X_{4} + 20 X_{5} < 32$ and $X_{i}=0$ or $1$ for $i=1,\dots,5$. ... . Number the nodes in the tree in the order in which they are expanded and for each node show the bound on the partial solutions and the decision which leads to that node.
asked Nov 25, 2016 in Algorithms makhdoom ghaya 308 views
4 votes
3 answers
The following program computes values of a mathematical function $f(x)$. Determine the form of $f(x)$. main () { int m, n; float x, y, t; scanf ("%f%d", &x, &n); t = 1; y = 0; m = 1; do { t *= (-x/m); y += t; } while (m++ < n); printf ("The value of y is %f", y); }
asked Nov 25, 2016 in Algorithms makhdoom ghaya 676 views