Följande problem med nätverksdata övervägs. Källnoder i ett riktat acykliskt nätverk genererar oberoende meddelanden och en enda mottagare nod beräknar en målfunktion f av meddelandena. Målet är att maximera det genomsnittliga antalet gånger f kan beräknas per nätverksanvändning, dvs. "beräkningskapacitet". Problemet med nätkodning för ett enda mottagare-nätverk är ett specialfall av problemet med nätdata, där alla källmeddelanden måste reproduceras vid mottagaren. För nätkodning med en enda mottagare, routing är känd för att uppnå kapaciteten genom att uppnå nätverket min-cut övre gräns. Vi utvidgar definitionen av min-cut till nätdataproblem och visar att min-cut fortfarande är en övre gräns för maximal uppnåelig hastighet och är trång för beräkning (med kodning) någon målfunktion i flerkantiga trädnät och för beräkning linjära målfunktioner i alla nätverk. Vi studerar också gränsens täthet för olika klasser av målfunktioner. I synnerhet ger vi en lägre gräns för datorkapaciteten i termer av Steinerträdets förpackningsnummer och ett differentnet som är symmetriskt bundet. Vi visar också att för vissa nätverk och målfunktioner kan datorkapaciteten vara mindre än en godtyckligt liten del av den minskärning som är bunden.
Målet är att maximera frekvensen av målfunktionsberäkning per nätverksanvändning REF.
Network Coding for Computing: Cut-Set Bounds
{'venue': None, 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}