An Overview of Combinatorial Optimization Techniques

Authors(1) :-Dr. S. Dhanalakshmi

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

Authors and Affiliations

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

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

  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}

Publication Details

Published in : Volume 3 | Issue 1 | January-February 2018
Date of Publication : 2018-02-28
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 1052-1055
Manuscript Number : CSEIT1831221
Publisher : Technoscience Academy

ISSN : 2456-3307

Cite This Article :

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.
Journal URL : http://ijsrcseit.com/CSEIT1831221

Article Preview