Give a counterexample to the following claim:
“A set cover instance in which each element is in exactly f sets has a (1 /f )-integral optimal fractional solution (i.e., in which each set is picked an integer multiple of 1 /f).”
Question
Solution Preview
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.
Such an instance (of set cover problem) contains collection of at most k subsets Si included in U such that U is covered by their union. We can consider a simple example like below:U={x,y,z}; Si={{x,y},{y,z},{z,x},{x,y,z}}...
Return to homework library