-----------------------------------

grasssu

Tue May 20, 2008 4:01 am


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!


-----------------------------------

Vermette

Tue May 20, 2008 8:38 pm


RE:any approximation algorithms for this minimization problem?

-----------------------------------

Are negative values legal?


-----------------------------------

HeavenAgain

Tue May 20, 2008 8:49 pm


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