Name
Abstract | ||
|---|---|---|
In this paper, we focus on the Sort & Search method initially proposed by Horowitz and Sahni (1974) [6] to solve the knapsack problem, which has already show its applicability to derive exponential-time algorithms for some scheduling problems. We propose an extension of this method to a general class of problems called Multiple Constraint Problems and show that the extended Sort & Search method enables one to derive new exponential-time algorithms, with O^*(m^n^2) worst-case complexity, for two scheduling problems. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.tcs.2013.05.023 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
knapsack problem,new exponential-time algorithm,Multiple Constraint Problems,worst-case complexity,extended Sort,general class,search method,exponential-time algorithm,scheduling problem | Journal | 511, |
ISSN | Citations | PageRank |
0304-3975 | 6 | 0.49 |
References | Authors | |
4 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ch. Lenté | 1 | 6 | 0.49 |
| Mathieu Liedloff | 2 | 243 | 24.23 |
| Ameur Soukhal | 3 | 119 | 10.15 |
| V T'kindt | 4 | 54 | 4.55 |