0
$\begingroup$

Recall the rod cutting problem.

Given a rod of length $n$ inches and a table of prices $p_{i}$ for $i=1,2,3,4,\,.\,.\,.$ determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces. You may assume no cutting cost.

The following is a question from CLRS 15.1-2.

Show, by means of a counterexample, that the following ‘greedy’ strategy does not always determine an optimal way to cut rods. Define the density of a rod of length i to be p_i/i, that is, its value per inch. The greedy strategy for a rod of length n cuts off a first piece of length i, where 1≤i≤n, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length n-i.

Consider prices up to length $4$ are $p_1=1, p_2=5, p_3= 8, p_4 = 9$ respectively. So, densities are $d_1=1, d_2 = 2.5, d_3= 2.67, d_4 = 2.25$ respectively.

If we are given a rod of length $4,$ then an optimal way of cutting the rod to maximize revenue is $2$ pieces of length $2$ each, generating $5+5 = 10.$

However, greedy algorithm above will suggest cutting the rod into 2 pieces of length $3$ and $1$, generating revenue $8+1=9.$

I obtain this example by merely following the same prices given in CLRS but do not understand why such greedy algorithm fails to provide optimal way of cutting the rod.

$\endgroup$
4
$\begingroup$

Because a local maximum is not always a global maximum.

The length 3 rod is the most price-for-length effective single rod piece. But the optimization goal isn't to find the best price-to-length ratio for a single piece, it's to find the best total price for how much rod we actually have! Once the greedy algorithm chooses the shiniest, most appealing first piece, it is now stuck for the rest of the problem with a highly suboptimal remaining length according to the highly nonlinear price table.

In general, most optimization problems cannot be solved optimally by a greedy strategy. Those that can tend to have some exceptional property that guarantees that a local maximum will also be a global maximum.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Greedy algorithm doesn't always generate optimal solution. To get optimal solution with it, the problem needs to have some good property such as optimal substructure or matroid. The optimal substructure means optimal solution can be constructed from the optimal solutions of divided problems. Matroid theory shows another good property to characterize where greedy algorithm works: Edmonds–Rado Theorem claims that (best-in) greedy algorithm works with any weight function if and only if the independence system is matroid. Here, independence system is a kind of formalization used to many combinatorial optimization problems. I don't explain the details, but wanted to explain greedy algorithm works for problems with good properties, that the rod cutting problem doesn't hold.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.