Login



Other Articles by Author(s)

Nadav Voloch



Author(s) and WSEAS

Nadav Voloch


WSEAS Transactions on Computers


Print ISSN: 1109-2750
E-ISSN: 2224-2872

Volume 16, 2017

Notice: As of 2014 and for the forthcoming years, the publication frequency/periodicity of WSEAS Journals is adapted to the 'continuously updated' model. What this means is that instead of being separated into issues, new papers will be added on a continuous basis, allowing a more regular flow and shorter publication times. The papers will appear in reverse order, therefore the most recent one will be on top.



Optimal Paths of Knapsack-Set Vertices on a Weight-Independent Graph

AUTHORS: Nadav Voloch

Download as PDF

ABSTRACT: Two problems that are often studied and researches in computer science algorithms are the knapsack problem and the shortest paths on weighted graphs problem. Their combination is often addressed by dynamic programming solutions for the knapsack problem, using shortest path problem, with the creation of a knapsack graph. But these researches consider only two aspects of weight and value for an item/vertex, and here we address a different kind of problem in which we are taking into consideration three properties: item weight, item value and edge weight (that connects two items, but its weight is not depended on its vertices). Every vertex in this specific graph is a set of knapsack items. This situation is viable for real-life circumstances, in which a path has a non-dependent attribute (physical distance, travel time, etc.), and there are different kinds of items to be picked in different locations on this path. The problem presented here is finding the most efficient path between two vertices (source and target), in three aspects- minimal edge wise, maximum knapsack value wise, and a combination of maximal efficiency for both properties. An algorithm for finding these optimal paths is presented here along with specific explanations on its decision stages, and several examples for it.

KEYWORDS: Knapsack problem, Shortest paths on weighted graphs, Dijkstra's algorithm, 0-1 knapsack problem, All paths between two vertices in a graph

REFERENCES:

[1] Mathews, G. B. (1897). 'On the partition of numbers' . Proceedings of the London Mathematical Society 28: 486–490.

[2] Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. (2010) 'Highway Dimension, Shortest Paths, and Provably Efficient Algorithms'. ACM-SIAM Symposium on Discrete Algorithms, pages 782-793.

[3] Dantzig, George B. (1957). 'Discrete-Variable Extremum Problems'. Operations Research 5 (2): 266– 288.doi:10.1287/opre.5.2.266.

[4] Pisinger ,D. (1993). ' A Minimal Algorithm for the 0-1 Knapsack Problem ' . Operations Research September-October 1997 45(5):758 doi: 10.1287/opre.45.5.758

[5] Dijkstra, E. W. (1959). 'A note on two problems in connexion with graphs' . Numerische Mathematik 1: 269– 271.doi:10.1007/BF01386390.

[6] Mehlhorn, K., Sanders, P. (2008). 'Algorithms and Data Structures: The Basic Toolbox' .199- 200. Springer.

[7] Frieze, A. M. (1976). 'Shortest path algorithms for knapsack type problems' . Mathematical Programming 11: 150. doi:10.1007/BF01580382

[8] Handler, Gabriel Y., Zang, Israel (1980), ' A dual algorithm for the constrained shortest path problem', Networks- Wiley Subscription Services, Inc., A Wiley Company 10: 293-309, doi: 10.1002/net.3230100403

[9] Zhang, X., Huang, S., Hu, Y., Zhang, Y., Mahadevan, S., Deng, Y.: (2013) ' Solving 0–1 knapsack problems based on amoeboid organism algorithm.' Appl. Math. Comput. 219, 9959–9970

[10] Voloch N. (2017) ' Finding the most efficient paths between two vertices in a knapsack-item weighted graph ', International Journal of Advanced Computer Research (IJACR) Vol.7 Issue 28. http://dx.doi.org/10.19101/IJACR.2017.728003

[11] Ford, L. R.; Fulkerson, D. R. (1956). 'Maximal flow through a network' . Canadian Journal of Mathematics. 8: 399–404. doi:10.4153/CJM-1956-045-5.

[12] Edmonds, Jack; Karp, Richard M. (1972). 'Theoretical improvements in algorithmic efficiency for network flow problems'. Journal of the ACM. Association for Computing Machinery. 19 (2): 248– 264. doi:10.1145/321694.321699.

[13] Yefim Dinitz (1970). 'Algorithm for solution of a problem of maximum flow in a network with power estimation'. Doklady Akademii nauk SSSR. 11: 1277–1280.

WSEAS Transactions on Computers, ISSN / E-ISSN: 1109-2750 / 2224-2872, Volume 16, 2017, Art. #18, pp. 163-171


Copyright © 2017 Author(s) retain the copyright of this article. This article is published under the terms of the Creative Commons Attribution License 4.0

Bulletin Board

Currently:

The editorial board is accepting papers.


WSEAS Main Site