Vi anser att schemaläggningen av godtyckliga trådlösa länkar i den fysiska modellen av störningar minimerar tiden för att uppfylla alla förfrågningar. Vi studerar här det kombinerade problemet med schemaläggning och kraftstyrning, där vi söker både en tilldelning av effektinställningar och en partition av länkarna så att varje uppsättning uppfyller begränsningarna signal-till-interference-plus-buller (SINR). Vi ger en algoritm som uppnår ett approximationsförhållande av O(log n · log log ), där n är antalet länkar och är förhållandet mellan den längsta och den kortaste länklängden. Under det naturliga antagandet att längder representeras i binära, detta ger den första approximation förhållandet som är polylogaritmisk i storleken på inmatningen. Algoritmen har den önskvärda egenskapen att använda en oöverträffad makttilldelning, där den kraft som tilldelas en avsändare endast beror på länkens längd. Vi ger bevis för att detta beroende av är oundvikligt, vilket visar att varje rimligtvis ouppmärksam makttilldelning resulterar i en (logglogg )-uppskattning. Dessa resultat har också för det (viktade) kapacitetsproblemet att hitta en maximal (viktad) del av länkar som kan schemaläggas i en enda tidsrymd. Dessutom får vi förbättrad approximation för en dubbelriktad variant av schemaläggning problem, ge partiella svar på frågor om nyttan av grafer för modellering av fysisk störning, och generalisera inställningen från standard 2-dimensionella Euclidean plan till dubblering mätvärden. Slutligen undersöker vi nyttan av grafmodeller för att fånga trådlös störning.
Mer, i REF, författaren presentera en approximationsalgoritm för den trådlösa schemaläggning problem med förhållandet O(log n · log log.).
Wireless scheduling with power control
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}