Vi får en uppsättning viktade enhet diskar och en uppsättning punkter i Euclidean planet. Problemet med minimiviktenhetsdiskskydd (WUDC) kräver en delmängd diskar med minsta totalvikt som täcker alla givna punkter. WUDC är ett av de geometriska sätten att täcka problem, som har studerats ingående under de senaste två decennierna (för många olika geometriska intervall utrymmen, såsom (enhet) diskar, halvrymder, rektanglar, trianglar). Det är känt att det oviktade WUDC problemet är NP-hård och medger ett polynom-tids approximationssystem (PTAS). För det viktade WUDC-problemet har flera konstanta approximationer utvecklats. Om problemet medger ett PTAS har dock varit en öppen fråga. I detta dokument besvarar vi denna fråga positivt genom att presentera det första PTAS för WUDC. Vårt resultat innebär den första PTAS för minimal vikt dominerande set problem i enhet disk grafer. Tillsammans med befintliga idéer, kan vårt resultat också användas för att få den första PTAS för maximal livstid täckning problem och en förbättrad konstant approximation förhållande för den anslutna dominerande set problem i enhet disk grafer. - Vad är det för fel på dig?
För den viktade versionen av feltoleranta CDS-problem på UDG, till följd av det senaste arbetet REF, medger minimivikten (1, 1)-CDS-problemet en PTAS.
A PTAS for the Weighted Unit Disk Cover Problem
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}