Name
Abstract | ||
|---|---|---|
We introduce and study the approximability of the following problem. There is a set of useful objects that are available for purchase, and another set of useless objects that can be sold. Selling useless objects generates revenue which allows to acquire useful objects. We search for a sequence of decisions (buying or selling objects) which optimizes either the number of purchased objects or their global utility. One of the constraints is that, at any time, only a limited amount of money can be held. We introduce an optimization problem which is related to knapsack.We give an upper bound of 1 / 2 + ε on the performance guarantee of any approximation algorithm (unless P = NP ).An approximation algorithm with almost matching lower bound is provided. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.ipl.2015.05.001 | Information Processing Letters |
Keywords | Field | DocType |
Approximation,Greedy algorithms,Knapsack problem | Revenue,Approximation algorithm,Mathematical optimization,Combinatorics,Upper and lower bounds,Performance guarantee,Algorithm,Greedy algorithm,Knapsack problem,Optimization problem,Mathematics | Journal |
Volume | Issue | ISSN |
115 | 10 | 0020-0190 |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Laurent Gourvès | 1 | 241 | 30.97 |