Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLow congestion online routing and an improved mistake bound for online prediction of graph labeling
259
0
0.0
(
0
)
Added by
Jittat Fakcharoenphol
Publication date
2008
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
For online matching with the line metric, we present a lower bound of $Omega(log n)$ on the approximation ratio of any online (possibly randomized) algorithm. This beats the previous best lower bound of $Omega(sqrt{log n})$ and matches the known upper bound of $O(log n)$.
We consider the file maintenance problem (also called the online labeling problem) in which n integer items from the set {1,...,r} are to be stored in an array of size m >= n. The items are presented sequentially in an arbitrary order, and must be stored in the array in sorted order (but not necessarily in consecutive locations in the array). Each new item must be stored in the array before the next item is received. If r<=m then we can simply store item j in location j but if r>m then we may have to shift the location of stored items to make space for a newly arrived item. The algorithm is charged each time an item is stored in the array, or moved to a new location. The goal is to minimize the total number of such moves done by the algorithm. This problem is non-trivial when n=<m<r. In the case that m=Cn for some C>1, algorithms for this problem with cost O(log(n)^2) per item have been given [IKR81, Wil92, BCD+02]. When m=n, algorithms with cost O(log(n)^3) per item were given [Zha93, BS07]. In this paper we prove lower bounds that show that these algorithms are optimal, up to constant factors. Previously, the only lower bound known for this range of parameters was a lower bound of Omega(log(n)^2) for the restricted class of smooth algorithms [DSZ05a, Zha93]. We also provide an algorithm for the sparse case: If the number of items is polylogarithmic in the array size then the problem can be solved in amortized constant time per item.
The general adwords problem has remained largely unresolved. We define a subcase called {em $k$-TYPICAL}, $k in Zplus$, as follows: the total budget of all the bidders is sufficient to buy $k$ bids for each bidder. This seems a reasonable assumption for a typical instance, at least for moderate values of $k$. We give a randomized online algorithm, achieving a competitive ratio of $left(1 - {1 over e} - {1 over k} right)$, for this problem. We also give randomized online algorithms for other special cases of adwords. Another subcase, when bids are small compared to budgets, has been of considerable practical significance in ad auctions cite{MSVV}. For this case, we give an optimal randomized online algorithm achieving a competitive ratio of $left(1 - {1 over e} right)$. Previous algorithms for this case were based on LP-duality; the impact of our new approach remains to be seen. The key to these results is a simplification of the proof for RANKING, the optimal algorithm for online bipartite matching, given in cite{KVV}. Our algorithms for adwords can be seen as natural extensions of RANKING.
Motivated by the use of high speed circuit switches in large scale data centers, we consider the problem of circuit switch scheduling. In this problem we are given demands between pairs of servers and the goal is to schedule at every time step a matching between the servers while maximizing the total satisfied demand over time. The crux of this scheduling problem is that once one shifts from one matching to a different one a fixed delay $delta$ is incurred during which no data can be transmitted. For the offline version of the problem we present a $(1-frac{1}{e}-epsilon)$ approximation ratio (for any constant $epsilon >0$). Since the natural linear programming relaxation for the problem has an unbounded integrality gap, we adopt a hybrid approach that combines the combinatorial greedy with randomized rounding of a different suitable linear program. For the online version of the problem we present a (bi-criteria) $ ((e-1)/(2e-1)-epsilon)$-competitive ratio (for any constant $epsilon >0$ ) that exceeds time by an additive factor of $O(frac{delta}{epsilon})$. We note that no uni-criteria online algorithm is possible. Surprisingly, we obtain the result by reducing the online version to the offline one.
In the online labeling problem with parameters n and m we are presented with a sequence of n keys from a totally ordered universe U and must assign each arriving key a label from the label set {1,2,...,m} so that the order of labels (strictly) respects the ordering on U. As new keys arrive it may be necessary to change the labels of some items; such changes may be done at any time at unit cost for each change. The goal is to minimize the total cost. An alternative formulation of this problem is the file maintenance problem, in which the items, instead of being labeled, are maintained in sorted order in an array of length m, and we pay unit cost for moving an item. For the case m=cn for constant c>1, there are known algorithms that use at most O(n log(n)^2) relabelings in total [Itai, Konheim, Rodeh, 1981], and it was shown recently that this is asymptotically optimal [Bulanek, Koucky, Saks, 2012]. For the case of m={Theta}(n^C) for C>1, algorithms are known that use O(n log n) relabelings. A matching lower bound was claimed in [Dietz, Seiferas, Zhang, 2004]. That proof involved two distinct steps: a lower bound for a problem they call prefix bucketing and a reduction from prefix bucketing to online labeling. The reduction seems to be incorrect, leaving a (seemingly significant) gap in the proof. In this paper we close the gap by presenting a correct reduction to prefix bucketing. Furthermore we give a simplified and improved analysis of the prefix bucketing lower bound. This improvement allows us to extend the lower bounds for online labeling to the case where the number m of labels is superpolynomial in n. In particular, for superpolynomial m we get an asymptotically optimal lower bound {Omega}((n log n) / (log log m - log log n)).
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
