Consider the maximum coverage instance represented in figure left below, where the dots correspond to the clients to be covered {1,..., 12} and the small squares correspond to the potential facility locations {1,..., 7}. In this figure, the values in parenthesis are the demand values. For a given covering distance, the coverage sets for each client are given also right below. For instance, first client is covered by the first potential facility. Assuming the number of facilities to be installed as =2.

Q2. Consider the maximum coverage instance represented in figure left below, where the dots correspond to the clients to be covered {1,..., 12} and the small squares correspond to the potential facility locations {1,..., 7}. In this figure, the values in parenthesis are the demand values. For a given covering distance, the coverage sets for each client are given also right below. For instance, first client is covered by the first potential facility. Assuming the number of facilities to be installed as P=2. (10 points) (3) (1) 1 2 (2) (4) 1 3 Si = {1}, S4 = {4}, S7 = {2,6}, S10 = {4}, (2) 4 (3) 5 S2 = {1}, S5 = (3,4}, Sg = {2,5,6}, S11 = {5,7}, 2 7 (7) 3 4 S3 = {1,2}, S6 = {1,2,3,5), S9 = {3,4,7}, S12 = {7}. (1) (1) . abore wo 6 O 5 . 9 . 10 6 (2) . 11 (2) 7 12 Q2. Consider the maximum coverage instance represented in figure left below, where the dots correspond to the clients to be covered {1,..., 12} and the small squares correspond to the potential facility locations {1,..., 7}. In this figure, the values in parenthesis are the demand values. For a given covering distance, the coverage sets for each client are given also right below. For instance, first client is covered by the first potential facility. Assuming the number of facilities to be installed as P=2. (10 points) (3) (1) 1 2 (2) (4) 1 3 Si = {1}, S4 = {4}, S7 = {2,6}, S10 = {4}, (2) 4 (3) 5 S2 = {1}, S5 = (3,4}, Sg = {2,5,6}, S11 = {5,7}, 2 7 (7) 3 4 S3 = {1,2}, S6 = {1,2,3,5), S9 = {3,4,7}, S12 = {7}. (1) (1) . abore wo 6 O 5 . 9 . 10 6 (2) . 11 (2) 7 12