Project Options
Categories:
2 minute read
Project Options
MAX 3-SAT
Solve Problem using Independent Set Approximation
For this option, you must develop code that transforms the 3-SAT input into input for the independent set problem (in a polynomial number of steps). Many examples of how to do this are in publication, you just need to implement one of them and discuss how it works.
You can then use the instructor provided approximation algorithm for independent set and compare it to how your team’s approximation method (part D) performs.
Enumerate Clauses and Showcase Results (in development)
For all values of $$3 \ge n \ge 5$$, enumerate all possible input clauses and then show the ratio of unsatisfiable sets versus satisfiable sets.
Max Clique
TSP
Advanced Approximation Strategies
Augment the approximation strategy to:
- Many approximations reach a local min and can’t improve from there. Augment the approximation code to detect this local min and restart the approximation. Track each approximation and show the variance encountered by your program as well as the quality of the best solution as a function of time. Plot these results and discuss.
Longest Path
Test Cases
Generate at least 1000 interesting test cases and perform a comprehensive comparison of how the optimal solution/code differs from the approximation codes results.
Min Vertex Cover
Perform a reduction to Independent Set
For this option, you must develop code that transforms the Min Vertex Cover input into input for the independent set problem (in a polynomial number of steps). Many examples of how to do this are in publication, you just need to implement one of them and discuss how it works.
You can then use the instructor provided approximation algorithm for independent set and compare it to how your team’s approximation method (part D) performs.