Name
Abstract | ||
|---|---|---|
A notion of multi-parameter complexity analysis of a discrete problem as the determining of complexities of its subproblems over all possible combinations of constraints on key parameters is introduced, and a notion of a basis system of subproblems is defined. Basic theorems on the existence, uniqueness and finiteness of the basis system are established. As an illustration to this approach, some results on the 4-parameter complexity analysis of the open shop scheduling problem and of the connected list coloring problem are presented. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.ejor.2004.04.009 | European Journal of Operational Research |
Keywords | Field | DocType |
Complexity theory,Combinatorial optimization,Parameterized family of subproblems,Scheduling,Coloring | Existence theorem,Uniqueness,Mathematical optimization,Overlapping subproblems,Scheduling (computing),Uniqueness theorem for Poisson's equation,List coloring,Open-shop scheduling,Combinatorial optimization,Mathematics | Journal |
Volume | Issue | ISSN |
165 | 2 | 0377-2217 |
Citations | PageRank | References |
4 | 0.42 | 0 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sergey V. Sevastianov | 1 | 66 | 7.09 |