Abstract
We initiate a competitive analysis of packet forwarding policies for maximum and average flow in a line network. We show that the policies Earliest Arrival and Furthest-To-Go are scalable, but not constant competitive, for maximum flow. We show that there is no constant competitive algorithm for average flow.
Original language | English |
---|---|
Title of host publication | LATIN 2014: Theoretical Informatics |
Subtitle of host publication | 11th Latin American Symposium, Montevideo, Uruguay, March 31–April 4, 2014. Proceedings |
Editors | Alberto Pardo, Alfredo Viola |
Place of Publication | Berlin, Heidelberg |
Publisher | Springer |
Pages | 610-621 |
ISBN (Electronic) | 978-3-642-54423-1 |
ISBN (Print) | 978-3-642-54422-4 |
DOIs | |
Publication status | Published - 2014 |
Externally published | Yes |
Event | 11th Latin American Symposium on Theoretical Informatics, LATIN 2014 - Montevideo, Uruguay Duration: 31 Mar 2014 → 4 Apr 2014 Conference number: 11 |
Conference
Conference | 11th Latin American Symposium on Theoretical Informatics, LATIN 2014 |
---|---|
Abbreviated title | LATIN |
Country/Territory | Uruguay |
City | Montevideo |
Period | 31/03/14 → 4/04/14 |