The Gateway to Computer Science Excellence
+3 votes
239 views
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 by Boss (30.8k points) | 239 views
0
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

+1 vote

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: https://www.geeksforgeeks.org/partition-a-set-into-two-subsets-such-that-the-difference-of-subset-sums-is-minimum/ 

by Veteran (431k points)
0
Ordered in decreasing order
0
My mistake. You're right!

I'll delete my comment

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,291 answers
198,212 comments
104,903 users