Kapaciteten hos ett trådlöst nätverk är den största möjliga mängden samtidig kommunikation, med beaktande av störningar. Formellt behandlar vi följande problem. Givet är en uppsättning länkar, var och en en avsändare-mottagare par ligger i ett metriska utrymme, och en tilldelning av makt till avsändare. Vi söker en maximal delmängd av länkar som är möjliga i SINR-modellen: den signal som tas emot på varje länk bör vara större än summan av störningarna från de andra länkarna. Vi ger en konstant-faktor approximation som håller för alla längd-monoton, sub-linjär effekt tilldelning och alla avstånd metrisk. Vi använder detta för att ge i huvudsak snäva karakteriseringar av kapacitetsmaximering under effektkontroll med hjälp av omedvetna kraftuppdrag. Specifikt visar vi att medeleffekttilldelningen är optimal för kapacitetsmaximering av dubbelriktade länkar, och ger en tight (log n)-approximering av schemaläggning av dubbelriktade länkar med effektstyrning med hjälp av oöverträffad effekt. För enkelriktade länkar ger vi en nästan optimal O(log n + log log Δ)-uppskattning till effektregleringsproblem med medeleffekt, där Δ är förhållandet mellan längsta och kortaste länkar. Tillsammans klargör dessa resultat avsevärt den centraliserade komplexiteten i problem med trådlös kommunikation.
I ett annat arbete REF uppnåddes konstant faktor approximation för alla icke-avtagande, sublinjära effekttilldelningar.
Wireless capacity with oblivious power in general metrics
{'venue': "SODA '11", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}