ﻻ يوجد ملخص باللغة العربية
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.
Given $n$ colored balls, we want to detect if more than $lfloor n/2rfloor$ of them have the same color, and if so find one ball with such majority color. We are only allowed to choose two balls and compare their colors, and the goal is to minimize th
In this paper we show that many sequential randomized incremental algorithms are in fact parallel. We consider algorithms for several problems including Delaunay triangulation, linear programming, closest pair, smallest enclosing disk, least-element
A string $S[1,n]$ is a power (or tandem repeat) of order $k$ and period $n/k$ if it can decomposed into $k$ consecutive equal-length blocks of letters. Powers and periods are fundamental to string processing, and algorithms for their efficient comput
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 e
Online algorithms make decisions based on past inputs. In general, the decision may depend on the entire history of inputs. If many computers run the same online algorithm with the same input stream but are started at different times, they do not nec