Med tanke på en nite uppsättning S punkter (dvs. stationer av ett radionät) på en d-dimensionell Euclidean utrymme och ett positivt heltal 1 h jSj? 1, Min dd h-Range-uppdraget problemet består i att tilldela överföringsområden till stationerna för att minimera den totala strömförbrukningen, förutsatt att överföringsområdena för stationerna ser till att kommunikationen beween några par stationer i de flesta h humle. Två huvudfrågor som rör detta problem behandlas i detta dokument: handel-o mellan energiförbrukningen och antalet humle, beräkningskomplexet för problemet med Mind h-Range-uppdraget. När det gäller den första frågan, ger vi en lägre gräns på den minsta effektförbrukningen för stationer på planet för konstant h. Den nedre gränsen är en funktion av jSj, h och den minsta avståndet över alla par av stationer i S. Sedan får vi en konstruktiv övre gräns som en funktion av jSj, h och den maximala avståndet över alla par av stationer i S (dvs. diametern på S). Det visar sig att när det minsta avståndet mellan två stationer är \ inte för liten" (dvs. väl spridda fall) den övre gränsen matchar den nedre gränsen. Tidigare resultat för detta problem var kända endast för mycket speciella 1-dimensionella konverger (dvs. när punkter arrangeras på en linje på enhetlig avstånd) Kirousis, Kranakis, Krizanc, Pelc 1997]. När det gäller den andra frågan, observerar vi att tätheten i vår övre gräns innebär att Min 2d h-Range Uppdrag begränsad till väl spridda fall medger en polynom tid approximation algoritm. Sedan visar vi också att samma approximativa resultat kan erhållas för slumpmässiga fall. Å andra sidan bevisar vi att för h = jSj? 1 (dvs. det obundna fallet) Min 2d h-Range-uppdraget är NP-hard och Min 3d h-Range-uppdraget är APX-komplett.
Området tilldelning problem är NP-hård i alla dimensioner d ≥ 2 för alla värden på avstånd-effekt gradient p REF.
On the Power Assignment Problem in Radio Networks
{'venue': 'Electronic Colloquium on Computational Complexity (ECCC', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}