104k views
2 votes
Give a polynomial-time algorithm that takes a sequence of supply values s1, s2, . . . , sn and returns a schedule of minimum cost. for example, suppose r = 1, c = 10, and the sequence of values is

User Samu
by
8.3k points

1 Answer

3 votes
Assuming the sequence is unsorted.

Try a rudimentary proposition, do a bubble sort, that gives O(n^2) for worst and average case. It is a polynomial algorithm.

We can also do a quick sort, with worst case O(n^2) and average case O(nlogn), which is already better.

Do we need to sort everything? Not really.

What about a single pass, and store the minimum found, exchange as required, such as:

small=A(0)
for i:1, n {
if A(i)<small small: A(i)
}
return small

This is a linear algorithm, best case n, worst case 2n so O(n)
User Tenaya
by
8.1k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.