Name
Abstract | ||
|---|---|---|
In this paper, we first give the definition of randomized time-varying knapsack problems () and its mathematic model, and analyze the character about the various forms of . Next, we propose three algorithms for : (1) an exact algorithm with pseudo-polynomial time based on dynamic programming; (2) a 2-approximation algorithm for based on greedy algorithm; (3) a heuristic algorithm by using elitists model based on genetic algorithms. Finally, we advance an evaluation criterion for the algorithm which is used for solving dynamic combinational optimization problems, and analyze the virtue and shortage of three algorithms above by using the criterion. For the given three instances of , the simulation computation results coincide with the theory analysis. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/s10878-014-9717-1 | Journal of Combinatorial Optimization |
Keywords | Field | DocType |
Knapsack problem,Exact algorithm,Approximations,Heuristics | Dynamic programming,Mathematical optimization,Combinatorics,Exact algorithm,Heuristic (computer science),Algorithm,Greedy algorithm,Knapsack problem,Optimization problem,Mathematics,Genetic algorithm,Computation | Journal |
Volume | Issue | ISSN |
31 | 1 | 1382-6905 |
Citations | PageRank | References |
8 | 0.45 | 22 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yichao He | 1 | 44 | 4.46 |
| Xinlu Zhang | 2 | 13 | 2.64 |
| Wenbin Li | 3 | 294 | 38.79 |
| Xiang Li | 4 | 49 | 8.76 |
| Weili Wu | 5 | 2093 | 170.29 |
| Suogang Gao | 6 | 59 | 12.78 |