An Overview of Combinatorial Optimization Techniques

Authors

  • Dr. S. Dhanalakshmi  Professor, Department of Computer Science and Engineering, Malla Reddy Engineering College (A), Secunderabad, Telangana, India

Keywords:

0/1 or fractional knapsack, Capacity, G reedy, Dynamic Programming and Branch & Bound

Abstract

This paper presents the overview of greedy technique, dynamic programming technique and branch & bound technique. Knapsack problem is one of the applications of that technique. This discussion is centered overview of capacity of the objects and then the objective is to obtain a filling of the knapsack that maximizes the total profit earned without exceeding the capacity of the knapsack. After solving, the problems with maximum profit then find the time complexity of greedy, dynamic programming and branch & bound d techniques

References

  1. P. Sajjan, Ravi kumar Roogi, Vijay kumar Badiger, Sharanu Amaragatti,”A New Approach to Solve Knapsack Problem”, An International Research Journal of Computer Science and Technology, ISSN:0974-6471 OnlineISSN: 2320-8481,Vol7,Issue2, {http://www.computerscijournal.org/vol7no2/a-new-approach-to-solve-knapsack-problem/pdf/vol7no2/vol7no2_219-222.pdf}
  2. Veenu Yadav1, Ms.Shikha Singh, Vijay kumar Badiger, Sharanu Amaragatti,” A Review Paper on Solving 0-1 knapsack Problem with Genetic Algorithms”,International Journal of Computer Science and Information Technologies, Vol. 7 Issue 2, 2016, PP 830-832 ISSN : 0975-9646. { http://ijcsit.com/docs/Volume%207/vol7issue2/ijcsit2016070286.pdf}
  3. Ameen Shaheen, Azzam Sleit, “Comparing between different approaches to solve the 0/1 Knapsack problem”, IJCSNS International Journal of Computer Science and Network Security, ISSN:1738–7906,Vol.16 No.7,July 2016,PP1-10, { http://paper.ijcsns.org/07_book/201607/20160701.pdf}
  4. Shafiqul Abidin, “Greedy Approach for Optimizing 0-1 Knapsack Problem”, Communications on Applied Electronic, Vol 7 IssueNo.6, September 2017, ISSN : 2394-4714,PP1-3, {http://www.caeaccess.org/archives/volume7/number6/abidin-2017-cae-652675.pdf}
  5. Salem Hildebrandt & Christopher Hanson, “0-1 Knapsack Optimization with Branch-and-Bound Algorithm”, {http://www.micsymposium.org/mics2016/Papers/MICS_2016_paper_42.pdf}

IInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology

Downloads

Published

2018-02-28

Issue

Volume 3, Issue 1, January-February-2018

Section

Research Articles

License

Copyright (c) IJSRCSEIT

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
Dr. S. Dhanalakshmi, " An Overview of Combinatorial Optimization Techniques " International Journal of Scientific Research in Computer Science, Engineering and Information Technology(IJSRCSEIT), ISSN : 2456-3307, Volume 3, Issue 1, pp.1052-1055, January-February-2018.