Computer Science Canada any approximation algorithms for this minimization problem? |
| Author: | grasssu [ Tue May 20, 2008 4:01 am ] |
| Post subject: | any approximation algorithms for this minimization problem? |
a set of objects (i from 1 to m), each has: vi: the value of object i; si: size of object i. try to find a subset that can minimize the total value, subject to the condition that total size greater than or equal to B Any known approximation algorithms for it? Thanks! |
|
| Author: | Vermette [ Tue May 20, 2008 8:38 pm ] |
| Post subject: | RE:any approximation algorithms for this minimization problem? |
Are negative values legal? |
|
| Author: | HeavenAgain [ Tue May 20, 2008 8:49 pm ] |
| Post subject: | RE:any approximation algorithms for this minimization problem? |
well, what is the range of m? and.... there is a greedy way to do it, complexity is O(nlogn) i think. where you sort it first, then start packing it |
|