Vi studerar approximationsalgoritmer för följande geometriska version av problemet med maximal täckning: Låt P vara en uppsättning n viktade punkter i planet. Låt D representera ett plant objekt, såsom en rektangel, eller en disk. Vi vill placera m kopior av D så att summan av vikterna av de punkter i P som omfattas av dessa kopior maximeras. För alla fasta ε > 0, presenterar vi effektiva approximationssystem som kan hitta en (1 − ε)- tillnärmning till den optimala lösningen. Särskilt för m = 1 och för specialfallet där D är en rektangel körs vår algoritm i tid O(n log(
Problemet att placera m rektanglar sådan att summan av vikterna av de punkter i P som omfattas av dessa rektanglar maximeras anses i REF.
Linear Time Approximation Schemes for Geometric Maximum Coverage
{'venue': None, 'journal': None, 'mag_field_of_study': ['Computer Science']}