We consider the online scheduling problem of minimizing total weighted flow time plus energy in the dynamic speed scaling model, where a processor can scale its speed dynamically between 0 and some maximum speed T. In the past few years this problem has been studied extensively under the clairvoyant setting, which requires the size of a job to be known at release time [AlF07,BPS07,BCL+08,LLT+esa08,LLT+spaa08,BCP09,GNS09,LLT+09]. For the non-clairvoyant setting, despite its practical importance, the progress is relatively limited. Only recently an online algorithm [LAPS] is known to be O(1)-competitive for minimizing (unweighted) flow time plus energy in the infinite speed model (i.e., T = ∞) [CEL+09,CEP09]. This paper makes two contributions to the non-clairvoyant scheduling. First, we resolve the open problem that the unweighted result of [LAPS] can be extended to the more realistic model with bounded maximum speed. Second, we show that another non-clairvoyant algorithm [WRR] is O(1)-competitive when weighted flow time is concerned. Note that [WRR] is not as efficient as [LAPS] for scheduling unweighted jobs as [WRR] has a much bigger constant hidden in its competitive ratio.
We investigate the relationship between the complexities of
two models of randomized decision trees
for read-once Boolean functions; namely, with the directional
restriction and without it.
A decision tree is directional if it reads a variable in a
sub-formula, then it has to evaluate the sub-formula
completely before reading another variable that appears
in a different sub-formula.
It was known that there is a read-once Boolean formula such that
an optimal randomized decision tree to evaluate it is not directional.
This was first pointed out by Saks and Wigderson [FOCS '86] and
an explicit construction of such a formula was given
by Vereshchagin [TCS '98].
In this paper, we conduct a systematic search for a certain class of
functions and
provide an explicit construction of a read-once Boolean formula
f on n variables such that the cost of the optimal directional
randomized decision tree for f is BigOmega(n^alpha) and the cost
of the optimal randomized decision tree (without the directional
restriction) for f is O(n^beta)
with alpha-beta>0.0101. This is the largest known gap
so far.
Mediators are third parties to whom the players in a game can delegate the task of
choosing a strategy; a mediator forms a mediated equilibrium if delegating is a
best response for all players. Mediated equilibria have more power to achieve
outcomes with high social welfare than Nash or correlated equilibria, but less
power than a fully centralized authority. Here we initiate the study of the
power of mediation by introducing the mediation analogue
of the price of stabilityâ€”the ratio of the social cost of the best mediated
equilibrium BME to
that of the socially optimal outcome OPT. We focus on load-balancing games
with social cost measured by weighted average latency. Even in this restricted
class of games, BME can
range from being as good as OPT to being no better than the best correlated
equilibrium.
In unweighted games BME achieves OPT; the weighted case is more subtle. Our main
results are (1) a proof that the worst-case ratio BME=OPT is at least
(1+sqrt(2))/2 ~= 1.2071
and at most 2 for linear-latency weighted load-balancing games, and that
the lower bound is tight when there are two players; and
(2) tight bounds on the worst-case BME=OPT for
general-latency weighted load-balancing games. We give similarly detailed results
for other natural social-cost functions. We also show a precise correspondence
between the quality of mediated equilibria in a game G and the quality of
Nash equilibria in the repeated
game when G is played as the stage game. The proof of this correspondence is
based on a
close connection between mediated equilibria and the Folk Theorem from the economics
literature.
This paper studies the one-way communication complexity of the