Title:
Optimal online ring routing
Authors:
Havill, Jessen T.; Hutson, Kevin R.
Citation:
Jessen, T. Havill and Kevin R. Hutson. Optimal online ring routing. Networks. Volume 57, Issue 2, March 2011, Pages: 187–197.
Publisher:
Networks
DATE ISSUED:
Mar-2011
PERMANENT LINK:
http://hdl.handle.net/2374.DEN/4995; http://hdl.handle.net/2374
Type:
Article
Language:
en_US
Description:
We study how to route online splittable flows in bidirectional ring networks to minimize maximum load. We show that the competitive ratio of any deterministic online algorithm for this problem is at least equation image, where equation image is the size of the ring, and that the online algorithm that splits each flow inversely proportionally to the length of the flow's shortest path achieves this competitive ratio for all integers equation image.
ISSN:
10970037
Appears in Collections:
Faculty Publications

Full metadata record

DC FieldValue Language
dc.contributor.authorHavill, Jessen T.en
dc.contributor.authorHutson, Kevin R.en
dc.date.accessioned2013-01-02T15:56:56Zen
dc.date.accessioned2013-12-18T21:04:42Z-
dc.date.available2013-01-02T15:56:56Zen
dc.date.available2013-12-18T21:04:42Z-
dc.date.created2011-03en
dc.date.issued2011-03en
dc.identifier.citationJessen, T. Havill and Kevin R. Hutson. Optimal online ring routing. Networks. Volume 57, Issue 2, March 2011, Pages: 187–197.en_US
dc.identifier.issn10970037en
dc.identifier.urihttp://hdl.handle.net/2374.DEN/4995en
dc.identifier.urihttp://hdl.handle.net/2374-
dc.descriptionWe study how to route online splittable flows in bidirectional ring networks to minimize maximum load. We show that the competitive ratio of any deterministic online algorithm for this problem is at least equation image, where equation image is the size of the ring, and that the online algorithm that splits each flow inversely proportionally to the length of the flow's shortest path achieves this competitive ratio for all integers equation image.en_US
dc.language.isoen_USen_US
dc.publisherNetworksen_US
dc.relation.ispartofFaculty Publicationsen_US
dc.titleOptimal online ring routingen_US
dc.typeArticleen_US
dc.contributor.institutionDenison Universityen_US
dc.date.digitized2013-01-02en
dc.contributor.repositoryDenison Resource Commonsen_US
All Items in The Five Colleges of Ohio Digital Repository are protected by copyright, with all rights reserved, unless otherwise indicated.