Vi anser att den uppsättning multi-cover problem i geometriska inställningar. Med tanke på en uppsättning punkter P och en samling geometriska former (eller uppsättningar) F, vill vi hitta en minsta kardinalitet delmängd av F så att varje punkt p  på P täcks av (som ingår i) minst d(p) uppsättningar. Här d(p) är ett heltal efterfrågan (krav) för p. När kraven d(p) = 1 för alla p, är detta standard set omslag problem. Den uppsättning täcka problem i geometriska inställningar medger en approximation förhållande som är bättre än den för den allmänna versionen. I detta dokument visar vi att man också kan uppnå liknande förbättringar när det gäller problemet med flera täckningsområden. I synnerhet, vi får en O (log opt) approximation för inställda system av avgränsad VCdimension, och en O(1) approximation för att täcka punkter med halvrymder i tre dimensioner och för vissa andra klasser av former.
Det oviktade multi-cover problemet har studerats i geometriska inställningar av Chekuri et al. Hoppa över det.
On the set multi-cover problem in geometric settings
{'venue': "SCG '09", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}