I detta dokument överväger vi konstant faktor approximation algoritmer för en variant av den diskreta piercing set problem för enhet diskar. Här ges en uppsättning punkter P; målet är att välja minsta antal punkter i P för att pierce enhet diskar centrerade på alla punkter i P. Vi föreslår först en mycket enkel algoritm som producerar 12 approximation resultat i O (n log n) tid. Därefter förbättrar vi approximationen till 4 och sedan till 3. Den värsta drifttiden för dessa algoritmer är O(n 8 log n) respektive O(n 15 log n). Förutom det utrymme som krävs för att lagra indatan är kravet på extra arbetsyta för alla dessa algoritmer O(1). Slutligen föreslår vi ett PTAS för samma problem. Med tanke på ett positivt heltal k, kan det producera en lösning med prestandaförhållande (1 +
Nyligen, De på Al. Ref beaktade den geometriska versionen av MDS-problem och föreslagna 12-faktorsalgoritmer, 4-faktorsalgoritmer och 3-faktorsalgoritmer med körtid O(n log n), O(n 8 log n) respektive O(n 15 log n).
Approximation Algorithms for a Variant of discrete Piercing Set Problem for Unit Disks
{'venue': 'Int. J. Comput. Geometry Appl.', 'journal': 'Int. J. Comput. Geometry Appl.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}