Det har funnits ett stort intresse för nätverksgemenskapen när det gäller effekterna av kaskadeffekter på spridningen av uppgraderingar av nätverksteknik på Internet. Att tänka på det globala Internet som en graf, där varje nod representerar en ekonomiskt motiverad Internet Service Provider (ISP), ett nyckelproblem är att bestämma den minsta uppsättning noder som kan utlösa en kaskad som orsakar varje annan nod i diagrammet att anta protokollet. Vi designar den första approximationsalgoritmen med en bevisbar prestandagaranti för detta problem, i en modell som fångar följande nyckelfråga: en nods beslut att uppgradera bör påverkas av beslut av de fjärrnoder den vill kommunicera med. Med tanke på ett internetwork G(V, E) och tröskelfunktion, antar vi att node u aktiverar (uppgraderar till den nya tekniken) när den gränsar till en ansluten komponent av aktiva noder i G i storlek som överstiger nod u tröskel  och u. Vårt mål är att välja den minsta uppsättning noder som kan få resten av grafen att aktiveras. Vårt huvudsakliga bidrag är en approximationsalgoritm baserad på linjär programmering, som vi kompletterar med beräkningshårdhetsresultat och ett nästan optimalt integratitetsgap. Vår algoritm, som inte förlitar sig på submodulära optimeringstekniker, belyser också den stora algoritmiska skillnaden mellan vårt problem och liknande frågor som studeras i samband med sociala nätverk.
Goldberg och Liu Ref studerar en annan variant av fast tröskelmodell och tillhandahåller en approximationsalgoritm baserad på linjär programmeringsteknik.
The Diffusion of Networking Technologies
{'venue': 'SODA 2013', 'journal': 'arXiv: Social and Information Networks', 'mag_field_of_study': ['Computer Science', 'Physics']}