OPT_UCM

Implementation of NP-hard problems and solvers from Optimization course. Master in Computer Science at Complutense University of Madrid. Course 2020-2021.

Problems & Algorithms

• Knapsack problem
  • Exhaustive search
  • Greedy algorithm
  • Dynamic programming
  • FPTAS
• Set cover problem
  • Exhaustive search
  • Greedy algorithm
  • Genetic algorithm
• Vertex Cover
  • Greedy algorithm

Final Project

Solving the Steiner tree and the travelling salesman problems using the River Formation Dynamics (RFD) algorithm.

References

• Vazirani, V. V. (2013). Approximation algorithms. Springer Science & Business Media.
• P. Rabanal, I. Rodríguez, and F. Rubio, “Applying river formation dynamics to solve NP-complete problems,” Stud. Comput. Intell., vol. 193, pp. 333–368, 2009, doi: 10.1007/978-3-642-00267-0_12.