Vi undersöker den enkla klassen av giriga schemaläggningsalgoritmer, det vill säga algoritmer som alltid vidarebefordrar ett paket om de kan. Om man antar att endast ett paket kan levereras över en länk i ett enda steg, och att de rutter som korsas av en uppsättning paket är optimalt avstånd ("kortaste vägar"), visar vi att den tid som krävs för att slutföra överföringen av ett paket i uppsättningen begränsas av dess ruttlängd plus antalet andra paket i uppsättningen. Denna gräns håller för alla giriga algoritmer, även i fallet med olika starttider och olika ruttlängder. Den bundna generaliserar också, på det naturliga sättet, till det fall där w-paket kan korsa en länk samtidigt. Dessutom håller resultatet i den asynkrona modellen, med samma bevisteknik. Resultatets allmängiltighet visas av några få tillämpningar. Vi presenterar ett enkelt protokoll, för vilket vi härleder en allmän bunden på genomströmningen med någon girig schemaläggning. Ett annat protokoll för det dynamiska fallet presenteras, vars paketleveranstid begränsas av längden på paketets rutt plus antalet paket i nätverket i den tid det skickas.
Mansour och Patt-Shamir REF studerar giriga schemaläggningsalgoritmer (algoritmer som alltid vidarebefordrar ett paket om de kan) i den miljö där alla pakets vägar är kortaste vägar.
Greedy Packet Scheduling on Shortest Paths
{'venue': 'Journal of Algorithms', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}