View Proposal
-
Proposer
-
Mahmoud Mousa
-
Title
-
Proposing approximation algorithms for NP-complete problems such as Knapsack Problem.
-
Goal
-
The goal of this project is to study an NP-complete problem such as Knapsack problem and proposing algorithms to find optimal and approximate solutions for this problem.
-
Description
- The goal of this project is to study an NP-complete problem such as Knapsack problem and proposing algorithms to find optimal and approximate solutions for this problem. The optimal algorithms for NP-complete problems usually take a long time, could be exponential complexity, to generate optimal solutions, especially for hard instance datasets. The aim is to design approximate algorithms to find near optimal answers in polynomial time and compare the performance of the suggested approximation algorithm(s) to the optimal one(s).
- Resources
-
Mousa, Mahmoud AA, Sven Schewe, and Dominik Wojtczak. "Optimal control for simple linear hybrid systems." 2016 23rd International Symposium on Temporal Representation and Reasoning (TIME). IEEE, 2016.
Mousa, Mahmoud AA, Sven Schewe, and Dominik Wojtczak. "Optimal control for multi-mode systems with discrete costs." Formal Modeling and Analysis of Timed Systems: 15th International Conference, FORMATS 2017, Berlin, Germany, September 5–7, 2017, Proceedings 15. Springer International Publishing, 2017.
-
Background
-
-
Url
-
External Link
-
Difficulty Level
-
Moderate
-
Ethical Approval
-
None
-
Number Of Students
-
0
-
Supervisor
-
Mahmoud Mousa
-
Keywords
-
optimal algorithms, approximation algorithms, np-complete, knapsack problem, optimisation
-
Degrees
-
Master of Science in Artificial Intelligence
Master of Science in Artificial Intelligence with SMI
Master of Science in Computing (2 Years)