Consider the following statements of approximation algorithm : Statement I:…

Answer: Statement I is true; Statement II is false.

• Statement I — Vertex cover:

  Algorithm: find any maximal matching M in the graph and output the set that contains both endpoints of every edge in M.

  Proof idea: each edge of the matching must have at least one endpoint in any vertex cover, so the optimum cover size is at least |M|. The algorithm returns 2|M| vertices, hence its size is at most 2·OPT, giving a 2-approximation.

• Statement II — Metric (triangle-inequality) TSP:

  The claim that there is a polynomial-time 3-approximation is not the standard or tight statement. In fact, for metric TSP:

  1. Doubling the edges of a minimum spanning tree and shortcutting repeated vertices yields a tour of length at most 2·OPT (a 2-approximation).

  2. Christofides' algorithm improves this to at most 1.5·OPT (a 3/2-approximation).

  Therefore the specific claim of a polynomial-time 3-approximation is false or at least misleading, because stronger guarantees exist.

Conclusion: Statement I is true (2-approximation exists for vertex cover); Statement II is false (metric TSP has known 2-approx and 1.5-approx algorithms).