Skip to content
College Subject Practice · College Year 3

Approximation Algorithms practice questions — College Subject Practice · College Year 3 Algorithms

Practise approximation algorithms with topic-based questions. Preview a sample, then start a short session.

See the question style before signup · Get instant feedback · Continue with focused practice

Try a sample question

Check your answer to see the explanation where one has been published.

Try this question
A key idea in proving hardness of approximation is reducing from a gap problem produced by the:

1 sample question · No signup needed

Something unclear? Report this question.

2
In the knapsack FPTAS, profits are scaled by a factor K=ϵPmax/nK = \epsilon P_{max} / n. What is the purpose of this scaling?
3
The double-tree (tree-doubling) algorithm for metric TSP achieves what ratio?
Start a sample session

50 published questions available for this topic.