In a ratio proof, what sits between the optimum and the algorithm?

• A second run of the algorithm
• The exact optimal value
• A computable middle bound

An algorithm is a factor 2 approximation for a minimization problem. What is guaranteed?

• The answer never exceeds twice the optimum
• The answer always equals the optimum
• The typical answer is twice the optimum

A proved ratio tells you the typical gap on everyday instances.

Circle one:   True   False

An instance makes the method return exactly twice the optimum. What does that show?

• The analysis is tight and cannot be improved
• The ratio claim is refuted
• The method is useless in practice

A factor 2 method returns 12 on some instance. Type the smallest value the optimum could have.

Answer: ______________

B is 10 and your method returns 18 with a claimed factor of 2. Does the claim hold here?

• Only if the optimum equals 10
• No, 18 exceeds B
• Yes, 18 sits below twice B

Your method has a tight factor 4 bound. A rival promises factor 2 unproved. What follows?

• The tight bound proves your method is worse
• Tightness says nothing about which method wins in practice
• An unproved promise beats a tight bound

Theo computes optima on ten test cases, sees gaps near 1.1, and claims factor 1.1. What is wrong?

• Ten cases are too few to average
• Measured gaps never certify untested instances
• Optima cannot be computed on small cases