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)