Question

13.5 Show that the integrality gap of the relaxation for the following two variants of multiset multicover, based on LP (13.2), is not bounded by any function of n. 1. Remove the rest riction that M(S, e) <re 2. Impose the constraint that each set can be picked at most once. What is the best approximation guarantee you can establish for the greedy algorithm for the second variant. Σ(3)ES minimize (13.2) SES rs2 1, eeU subject to S: eES SES

Answer 1

nfeg alty gap Cleg cn) Cah be Shouun vsing ANS- the Set cover Lp has the iateguality Jop f Set covex galos field of two elements G Co) dat each elemont ee U be a a bhay oaip of angth K ield numbex fe: ee- 1 oPT (1) T2 Se se Seg elements,that is te e) do not Span U So this colleoflon has Fest el e viet e Se 9Ck Suppare g does nol Span all non zero nullspace ingide U diost fomalate the IP set Covex- Coe mioi mizo C(s)X Se'S Sabject to e eu S: ecs s Eo, SeS the dual Intuitively chagng we Can think eaoh eleman ome nogave prices ye asot Covex non for ite coverageby The gum a the prices (n Some Set S, or 1: ees than the cost af sel Qan not be mooe