Approximating the optimal sequence of acquisitions and sales with a capped budget
We introduce an optimization problem which is related to knapsack. We give an upper bound of 1/2+? 1 / 2 + ? on the performance guarantee of any approximation algorithm (unless P=NP P = NP ). An approximation algorithm with almost matching lower bound is provided.
approximation greedy algorithms knapsack problem