- 1. The set cover problem is equivalent to which other problem?
A) Hitting set problem
B) Stable set problem
C) Vertex cover problem
D) Maximum flow problem
- 2. A subset H of U is a hitting set if it intersects all subsets in what collection?
A) S
B) C
C) U
D) U'
- 3. In the hitting set problem, what is the goal regarding the set H?
A) Find a random hitting set
B) Find a minimum hitting set
C) Find an empty hitting set
D) Find a maximum hitting set
- 4. In the construction for the equivalence, what is the size of the new universe U'?
A) m
B) n-m
C) n+m
D) n
- 5. In the bipartite graph representation, how many vertices are on the left side?
A) n-m
B) n
C) n+m
D) m
- 6. In the bipartite graph, what do the edges represent?
A) Set membership
B) Vertex coloring
C) Subset exclusion
D) Intersection size
- 7. A set cover C is a subset of which vertices in the bipartite graph?
A) Left vertices
B) Center vertices
C) Both left and right vertices
D) Right vertices
- 8. A hitting set H is a subset of which vertices in the bipartite graph?
A) Left vertices
B) Both left and right vertices
C) Center vertices
D) Right vertices
- 9. In computational geometry, what is another term for a hitting set?
A) Geometric set or point set
B) Stabbing set or piercing set
C) Covering set or packing set
D) Bounding set or layer set
- 10. What is the condition for a set H to hit a subset Sj?
A) H intersection Sj is not empty
B) H is equal to Sj
C) Sj is a subset of H
D) H is a subset of Sj
- 11. What does the equation Sj in C iff j in H' imply?
A) The size of C is smaller than H'
B) The size of C is greater than H'
C) The sets are disjoint
D) Equivalence between set cover and hitting set
- 12. What does the weight represent in the weighted set cover problem?
A) Quantity
B) Capacity
C) Cost
D) Frequency
- 13. The set cover problem is a classical question in which of the following fields?
A) Astronomy
B) Biology
C) Computer science
D) Sociology
- 14. In the set cover problem, what term is used to refer to the set of all elements {1, 2, ..., n}?
A) The collection
B) The universe
C) The subset
D) The sub-collection
- 15. In the provided example, what is the size of the universe U = {1, 2, 3, 4, 5}?
A) 5
B) 3
C) 4
D) 2
- 16. In the example where S = { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} }, what is the value of m?
A) 4
B) 2
C) 3
D) 5
- 17. What is the solution size to the set cover problem for the example U = {1, 2, 3, 4, 5} and S = { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} }?
A) 2
B) 3
C) 4
D) 1
- 18. Formally, a set cover is defined as a subfamily C of S such that the union of C is equal to what?
A) The empty set
B) The collection S
C) The integer k
D) The universe U
- 19. The decision version of set covering is classified as:
A) Undecidable
B) NP-complete
C) NP-hard
D) P
- 20. In what year was set cover shown to be one of Karp's 21 NP-complete problems?
A) 1985
B) 1990
C) 1972
D) 1960
- 21. The optimization version of the set cover problem is:
A) NP-complete
B) Solvable in linear time
C) NP-hard
D) P
- 22. The study of the set cover problem has led to the development of fundamental techniques for which field?
A) Cryptography
B) Quantum computing
C) Approximation algorithms
D) Database theory
- 23. What is the covering constraint expressed using the incidence matrix?
A) Ax = 0
B) Ax > n
C) Ax >= 1
D) Ax <= 1
- 24. How does the fractional set cover problem differ from the ILP formulation?
A) Variables x_s must be negative
B) Variables x_s can be non-integers
C) Constraints are multiplicative
D) Objective function is maximized instead of minimized
- 25. What is the constraint on x_s in the fractional set cover problem?
A) x_s = 0
B) x_s > 10
C) 0 <= x_s <= 1
D) x_s >= 1
- 26. In the incidence matrix A, what do the rows correspond to?
A) Weights
B) Elements
C) Variables
D) Sets
- 27. What is true about the coefficients in the covering problem LPs?
A) They are all zero
B) They are negative
C) They are all equal to 1
D) They are non-negative
- 28. How can the greedy algorithm be implemented in linear time?
A) Using a bucket queue to prioritize sets.
B) Using a brute-force search of all subsets.
C) Using a simple linked list to store all elements.
D) Using a recursion stack with depth-first search.
- 29. What does H(n) represent in the context of the set cover approximation ratio?
A) The set size divided by n.
B) The n-th harmonic number.
C) The natural logarithm of n.
D) The n-th prime number.
- 30. What is the approximation ratio achieved by the LP relaxation algorithm for low-frequency systems where each element is in at most f sets?
A) log n
B) f
C) ln n
D) f-1
- 31. If the Unique games conjecture is true, the hardness of approximation for low-frequency systems is improved to what?
A) f - 1 - epsilon
B) 1/f
C) f - epsilon
D) ln n
- 32. Trevisan (2001) proves that for instances with sets of size at most Delta, the approximation factor cannot be better than what?
A) ln Delta - O(ln ln Delta)
B) f - 1
C) ln n
D) ln Delta + 1
- 33. In randomized rounding for weighted set cover, a set is included in the cover with what probability?
A) xS*
B) 1/f
C) 1/n
D) 1 - xS*
- 34. Which algorithm constructs feasible solutions to both primal and dual linear programs simultaneously?
A) Randomized rounding
B) Deterministic LP rounding
C) Primal-dual algorithm
D) Greedy algorithm
|