Computer Science – Data Structures and Algorithms
Scientific paper
2008-09-11
Computer Science
Data Structures and Algorithms
5 pages
Scientific paper
In this paper, we show a connection between a certain online low-congestion routing problem and an online prediction of graph labeling. More specifically, we prove that if there exists a routing scheme that guarantees a congestion of $\alpha$ on any edge, there exists an online prediction algorithm with mistake bound $\alpha$ times the cut size, which is the size of the cut induced by the label partitioning of graph vertices. With previous known bound of $O(\log n)$ for $\alpha$ for the routing problem on trees with $n$ vertices, we obtain an improved prediction algorithm for graphs with high effective resistance. In contrast to previous approaches that move the graph problem into problems in vector space using graph Laplacian and rely on the analysis of the perceptron algorithm, our proof are purely combinatorial. Further more, our approach directly generalizes to the case where labels are not binary.
Fakcharoenphol Jittat
Kijsirikul Boonserm
No associations
LandOfFree
Low congestion online routing and an improved mistake bound for online prediction of graph labeling does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Low congestion online routing and an improved mistake bound for online prediction of graph labeling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Low congestion online routing and an improved mistake bound for online prediction of graph labeling will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-474516