10-20

A Modification of Dynamic Programming Algorithms to Reduce the Running Time or/and Complexity

by Gafarov, E.R.; Lazarev, A.A.; Werner, F.

 

Preprint series: 10-20, Preprints

MSC:
90C39 Dynamic programming, See also {49L20}
90B35 Scheduling theory, See also {68M20}

 

Abstract: In this paper, we present a modification of dynamic programming algorithms (DPA), which we denote as graphical algorithms (GrA). For the knapsack problem and some single machine scheduling problems, it is shown that the time complexity of the GrA is less than the time complexity of the standard DPA. Moreover, the average running time of the GrA is often essentially smaller. A GrA can also solve large-scale instances and instances, where the parameters are not integer. In addition, for some problems, GrA has a polynomial time complexity in contrast to a pseudo-polynomial complexity of DPA.

Keywords: Dynamic Programming; Graphical algorithm; Scheduling; Single machine problems; Knapsack problem


The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster