Vi undersöker problemet inom-Strip Diskrete Unit Disk Cover (WSDUDC), där man vill hitta en minimal uppsättning enhetsdiskar från en ingångsuppsättning D så att en uppsättning punkter P täcks. Dessutom är alla punkter och diskcentrum placerade i en strimma av höjd h, definierad av ett par parallella linjer. Vi ger en allmän approximationsalgoritm som finner en 3 / 1 - h 2 - faktor approximation till den optimala lösningen. Vi erbjuder också en 4-ungefärlig lösning med en remsa där h ≤ 2 ε 2/3, och en 3-approximering i en remsa om h ≤ 4/5, förbättra över 6-approximering för sådana remsor med hjälp av det allmänna schemat. Slutligen visar vi att WSDUDC är NPfullständig för en remsa med valfri höjd h > 0.
Latter, Fraser och López-Ortiz REF föreslog ett approximativt resultat för 0 ≤ h < 1 för 3 och 1–h 2–faktor.
The Within-Strip Discrete Unit Disk Cover Problem
{'venue': 'CCCG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}