Approximation Algorithms Quiz Form
Please answer all questions to the best of your knowledge. This quiz covers key concepts in approximation algorithms, including definitions, ratios, problem types, and complexity.
What is the definition of an approximation ratio in the context of approximation algorithms?
*
Which of the following problems is known to be NP-hard and commonly studied in approximation algorithms?
*
Vertex Cover
Breadth-First Search
Binary Search
Bubble Sort
Name an algorithm that achieves a 2-approximation for the metric Traveling Salesman Problem (TSP).
*
Select all statements that correctly describe properties of approximation algorithms.
*
They provide solutions close to optimal in polynomial time.
They always find the exact optimal solution.
They are used for NP-hard problems.
They guarantee a solution within a specific factor of the optimal.
Which complexity class do approximation algorithms typically address when finding exact solutions is infeasible?
*
NP-hard
P
BPP
L
Fill in the table with the correct approximation ratios for each problem.
*
Rows
Approximation Ratio
Vertex Cover
Set Cover (Greedy)
Metric TSP (Christofides)
Knapsack (Greedy)
Which of the following is NOT a valid performance guarantee for an approximation algorithm?
*
Solution is within a factor of 2 of optimal.
Solution is always optimal.
Solution is within a factor of log(n) of optimal.
Solution is within a factor of 1.5 of optimal.
Briefly explain the significance of the PCP theorem in the context of approximation algorithms.
*
Which algorithm provides a logarithmic approximation for the Set Cover problem?
*
For which of the following problems is there currently no known polynomial-time constant-factor approximation algorithm?
*
Clique
Vertex Cover
Metric TSP
Knapsack
Submit Quiz
Should be Empty: