Scheduling Search Procedures.
We analyze preemptive on-line scheduling against randomized adversaries, with the goal to finish an unknown distinguished target job. Our motivation comes from clinical gene search projects, but the subject leads to general theoretical questions of independent interest, including some natural but unusual probabilistic models. We study problem versions with known and unknown processing times of jobs and target probabilities, and models where the on-line player gets some randomized extra information about the target. For some versions we get optimal competitive ratios, expressed in terms of given parameters of instances.
In many cells from a certain type of tumor, small end segments of chromosome 1 of
varying lengths are deleted. This suggests the conjecture of a tumor suppressor gene located
in the shortest missing segment. This putative suppressor gene is knocked out only if it is
absent or damaged on the partner chromosome, too. (Note that a somatic cell contains two
versions of every chromosome.) Therefore one wishes to identify a gene in that region which
exhibits fatal mutations on the partner chromosome in the available examples of tumor cells
but works properly in healthy control cells.
us represent the chromosome as unit interval [0; 1], where some right end segment
is deleted in every such clinical case. A deletion is characterized by its breakpoint, i.e.
the new endpoint of the damaged chromosome. Breakpoint locations are fairly accurately
known in all cases. However, checking the status of candidate genes on the corresponding
partner chromosome is a time-consuming job, as it requires DNA sequencing, alignment and
comparison of sequences, mutation detection, interpretation of ndings, investigation of the
eect of genetic changes on the encoded protein and its function in the cell, etc. This does
not only take a long time, the processing time is also hard to predict, and one must be
prepared for surprises.
It is natural to assume that breakpoints follow some xed probability distribution and
are independent in dierent examples. Under the conjecture of a single suppressor gene, this
target gene must be to the right of all observed breakpoints.
One aspect of this gene search problem is: Given a sample of breakpoints and a set
of candidate genes, how should we distribute simultaneous work among these candidates
so as to optimize the chances of early success? Since this is a vague description of an
optimization problem, let us formulate the problem in a more abstract way that also allows
several generalizations. A framework and formal problem statements will be given in Section
In a set of n objects (here: the candidate genes), one object is the target (here: the
suppressor gene). Our goal is to identify the unknown target as early as possible. In order
to check whether or not an object is the target, one has to perform some job on that object.
In view of our application we allow preemptive scheduling without preemption penalty. (It
is not a big deal to switch to another candidate gene.) Thus one can even run a mix of jobs,
where every job permanently gets some fraction of time. In practice one has to approximate
such continuous schedules by ne-grained allocation of time slots according to the prescribed
fractions. The search stops when the target job has been nished, but since the target is
unknown, it is unavoidable to run the other jobs as well, at least partly. Thus we get an
on-line problem, with the target completion time as the cost to minimize.
A crucial point here is that the on-line player (searcher) has some prior knowledge about
probable target positions that she should take advantage of. In our case, the target is
most likely close to the rightmost breakpoint, since otherwise we should have observed
more breakpoints to the right, i.e. smaller deletions that still remove the suppressor gene.
However, from the modeling point of view it is problematic to assign probabilities to the
target candidates, given the rightmost breakpoint. Rather the target is given by nature, and
the observed rightmost breakpoint, in the following called the signal, obeys some distribution
depending on the target. We call this scenario the adversarial instance random signal (AIRS)
framework. Another perspective is the Bayesian setting where one assigns prior probabilities
to the targets which are then modied by the signal to posterior probabilities, according to
Bayes' formula. In particular, the prior probabilities may be assumed to be equal, if there
is no reason to favor one of the candidates. Note that, in contrast to Bayesian learning or
decision making (cf. [5, Chapter 15]), our goal is not to predict or guess a hypothesis but
to schedule jobs in order to really identify the true target. Hence the performance measure
is dierent.
We believe that the AIRS framework is natural and might be of interest also for other
problems with costly decisions under incomplete knowledge. Note that parameter estimation
in statistics and typical machine learning problems are of similar nature. The unknown
parameters of a distribution form the instance, the random sample is the signal, and the
accuracy of the resulting hypothesis determines in some way the cost or gain of using this
hypothesis in the application at hand.
In our particular case, the target candidates are n points close to 1 in interval [0; 1], and
the signal is sampled by the following random experiment: For a number m (the number of
clinical cases in a population monitored during several years), m breakpoints in [0; 1] have
been independently sampled according to the uniform distribution. (The breakpoints could
follow an arbitrary continuous distribution, but then we could map it to [0; 1] such that
the new coordinate of a point is the probability that the breakpoint falls to the left of this
point. So we can w.l.o.g. consider the uniform distribution on the unit interval.) Our signal
is the rightmost breakpoint to the left of the target, other breakpoints do not add useful
information.
If the target is point t, the signal density near point t is, by routine calculation, approximately
me (s t)m where s  t denotes the signal, and 0 for s > t. We may stretch the axis
by factor m, such that the signal density is approximately e s t for s  t, and 0 for s > t.
For large enough m we may even forget about the nite interval, as the signal density at
remote s is negligible, and take e s t as the exact signal density. This simplies calculations
without introducing a signicant error.
If the distribution of breakpoints and/or the positions of candidate genes is not known
precisely enough, we still have that the posterior probabilities of candidate genes decrease
to the right (of the rightmost breakpoint). This motivates some of our models where the
on-line player knows the order of the target probabilities, but not their numerical values.
Here we nish the outline of our particular motivation and begin working with formal
objects only.
On-line problems with randomized input
2.1 Choice tree, instances, and signals
The reader is supposed to be familiar with the basics of competitive analysis. We refer
to [5, 13]. We use o-line player and adversary as synonyms. Some criticism against the
malicious assumption of an omnipotent adversary and the corresponding classical denition
of competitive ratio is discussed in [8], and generalized models, called diuse adversary and
comparative analysis, have been studied. We describe a framework as we need it to capture
the scheduling problems we are interested in.
On-line problems can be considered as games. One part of this game is a mechanism
that determines a state of the problem. We split every state into an instance, which alone
determines the costs that any strategy will incur, and a signal that captures all extra information
that a player gets about the instance. By this abstract notion of signal one can
model any kind of extra knowledge (cf. the notion of comparative analysis in [8]). In the
worst case for the on-line player, the signal is just constant or independent of instances and
thus not informative.
The adversary generates a state by decisions we can think of as a rooted tree. Every
inner node including the root is either a chance node or an adversary node. Edges going from
a chance node to its children are labeled by probabilities that sum up to 1. The adversary
starts her decision process at the root. From an adversary node she can proceed to an
arbitrary child, but from a chance node the adversary must proceed to a child according to
the given probabilities. Every leaf is labeled by an instance (hidden from the on-line player)
and a signal (forwarded to the on-line player). Both players know the tree and all its labels
completely. Intuitively, the tree encodes the on-line player's background knowledge.
This tree model resembles the games trees in [5, Section 6.1.1], but here we use a tree only
to describe the generation of states, whereas the players' strategies are considered separately.
We allow nodes with uncountably innite fan-out, in that case we may have to deal with a
probability density on the set of children, rather than with single probabilities.
If an adversary (chance) node is child of another adversary (chance) node then we can
obviously merge it with the parent node. Thus we may w.l.o.g. consider trees consisting
of alternating layers of chance and adversary nodes. Moreover, the adversary may make all
her deterministic decisions rst, conditional on the outcomes of chance nodes. Thus we can
transform any such tree into an equivalent two-layer tree, merely consisting of an adversarial
root, chance nodes as its children, and leaves. This is the diuse adversary from [8] who
selects a distribution of states from a class of distributions. (However, for concrete problems,
these normalizations might not always be natural and can blow up the tree. As we will see
below, it is in some cases simpler to use more levels.)
2.2 Costs, regret, and competitive ratio
An action assigns a cost to every instance. We assume that both players have the same
actions available. A strategy is to deterministically choose and apply an action. (In the
present paper we do not consider randomized strategies.) The on-line player may take the
signal as a parameter for her choices.
Next we dene the competitive ratio of a strategy. Due to the above normalization we can
restrict the denition to the two-layer case. Once we have dened the competitive ratio of a
strategy for every chance node, we just take the maximum as the \overall" competitive ratio
of the strategy, since the adversary has the free choice among the chance nodes. We adopt
the following denition of competitive ratio for any chance node. Note that expectation
refers to the probability distribution on the children of the considered chance node.
Denition 2.1 ER of an on-line strategy is the expected ratio of the on-line cost and the
cost of a best action for the same instance.
This is justied particularly under the following assumptions: The on-line player sees in
retrospect what the instance was, and imagines that the adversary would have applied the
cheapest action on this instance, and the game is invariant under scaling, i.e. multiplying
all costs by any positive factor is an isomorphism of the labeled tree. Then ER measures
the on-line player's expected \multiplicative regret" (see [5, Chapter 15]), maximized over
all adversarial choices.
In [8], the competitive ratio for the diuse adversary has been dened dierently. To
distinguish this measure from ER we denote it by RE (ratio of expectations):
Denition 2.2 RE of an on-line strategy is the ratio of the on-line player's expected costs
and the expected cost of best actions for all instances.
Rather obviously but amazingly, RE at a chance node is the limit of ER when the same
game is played many times with the same strategy and the total costs of on-line player
and adversary are compared. Our interpretation of this fact is that an on-line player who
aims at minimizing ER has a long-run view, maybe because she must permanently solve
problems of this type, whereas for an on-line player faced with a single instance of a problem,
it is more natural to use ER as performance measure. In this sense, ER seems to be more
fundamental. Since both relations ER  RE and RE  ER are possible, we always have
to state which version of competitive ratio a result refers to.
Finally, we may extend our model towards comparative analysis and relax the assumption
of an omniscient adversary, assuming that she also gets a signal, but a more informative one
as the on-line player does. denition is straightforward.) This allows to evaluate
the power of certain components of information.
Examples of the notions are given in the next subsection, when we dene our problem
scenarios.
2.3 Notation and contributions
We will discuss various natural versions of preemptive on-line scheduling of search proce-
dures, which dier in the power of on-line player and adversary. According to our general
assumption that both players have the same actions available at the same costs, the adversary
is always supposed at least to verify the target.
To make the presentation consistent in itself we use some notation that may deviate from
standard terminology (like ER, RE dened above, denotation of job parameters etc. Let
n be the number of objects, one of them being the target. The amount of time to recognize
whether the ith object is the target is called the decision time of this object/job and is
denoted c i .
In order to get in easier, we will rst consider simple models where the jobs have target
probabilities
turn out that the main results carry over to
the Bayesian model and to the AIRS setting where the on-line player gets a random signal
correlated to the adversarial target. We also brie
y consider the use of partially known
decision times of objects.
In the following we state the main problem versions that will be considered. (Other,
rather marginal ones are left out, in order to keep the introduction reasonably short.) We
also summarize the main results.
Scenario 1. The adversary assigns target probabilities p i and decision times c i to all objects
(adversarial root). The target is chosen according to the p i (level of chance nodes).
The on-line player gets the p i as input (signal) and can start processing the jobs.
Results: RE < 2 is asymptotically tight, and optimal subject to a
constant factor. The former bound generalizes a result from [12].
Scenario 2. The adversary assigns target probabilities p i to all objects i (adversarial root).
The target is chosen according to the p i (level of chance nodes). The adversary learns
the target and assigns decision times c i to all objects (level of adversarial nodes). The
on-line player gets the p i as input (signal) and can start processing the jobs.
Results:
Scenario 3. As Scenario 2, but the on-line player gets as input only the indices of jobs
sorted by decreasing p i , not the values of the p i .
Results: ER is within factor O(log n) of the optimal ER for known target probabil-
ities, and this is asymptotically optimal.
Scenario 4. For each object t, the adversary assigns signal probabilities denoted p(sjt) to
all signals s and selects a target t and decision times for all jobs (adversarial root). A
signal s is chosen according to the p(sjt) for the selected t (level of chance nodes). The
on-line player gets as input the table of signal probabilities and the random signal s
and can start processing the jobs.
Results:
Scenario 5. The adversary assigns a minimum and maximum decision time a i and b i ,
respectively, to every object i, selects a target, and assigns real execution times c i ,
a i  c i  b i to all jobs (adversarial root only, no further tree nodes, no randomness).
The on-line player gets the a i and b i as input (which re
ects some knowledge on the
decision times) and can start processing the jobs.
Results: Competitive ratio
a
1 is optimal.
In contrast to games with randomized strategies against malicious adversaries, in the
present paper we consider only deterministic strategies, although it would be interesting in
some cases to explore the benets of randomization. Some remarks are added in the last
section.
Totally ordered targets and one-sided signals. Back to our original motivation,
we will apply the result for Scenario 4 to the problem from Section 1 (being conscious of the
fact that scheduling is only one facet of the potential applications).
Recall the signal density function e s t for s  t, and 0 for s > t. For the sake of simplicity
we will not distinguish signals between the same consecutive targets candidates, that is, we
only use n signals corresponding to the n 1 intervals between objects (genes) together
with the innite leftmost interval. Let t 1 be the target candidate points, with
convenience, and let signal s i appear if the rightmost breakpoint
falls in interval (t the likelihood p(s i jt j ) as a function of j is
monotone decreasing.
We dene L i :=
We can express the signal probabilities in terms of the L i ,
and then the optimal strategy gives advice how much of the time should (roughly) be spent
on each candidate, given the positions t i . It is also interesting to estimate the competitive
ratio e.g. for equidistant t i . We get the upper bound (1 + L)=(1 L) where
i. (Since the number of breakpoint data acts as a stretch factor on the coordinate axis, L
decreases exponentially as this number grows.)
2.4 Related literature
The study of on-line scheduling was initiated in [12]. (We do not clearly distinguish between
the original naming \nonclairvoyant scheduling" and \on-line scheduling". These attributes
stress dierent aspects: the player's lack of knowledge and the unforeseeable nature of the
input.) The problem versions considered in the present paper are static in that all jobs are
released in the beginning, and no further jobs appear over time, unlike most of the usual
\on-line" problems. Only the parameters of these initially given jobs are unknown to the
on-line player. For other recent results in the eld and further pointers we refer e.g. to [3].
Scheduling against randomized adversaries is also addressed in [11], but the execution times
are random variables, while the objective functions are the classical ones there. Thus there
is no overlap with our work. Geometric search problems as in [1, 10] are of similar nature,
but they dier very much in the costs of \preemptions", i.e. changing directions of search.
There might be connections between target search problems and deadline scheduling where
the goal is to nish as many (protable) jobs as possible before a deadline, under partial
ignorance of the parameters. We refer to [4, 6, 9] for more information. Slowdown is a
measure that resembles the goal in our Scenario 2, however the assumptions and goals in [2]
are dierent.
3 Models with Target Probabilities
3.1 Minimizing the expected completion time
An obvious goal for any player who knows the p i and c i but not the actual
target, is to minimize the expected completion time of the target job. Dene d
Sort the jobs such that d 1 . Then the optimal solution is simply to execute the
jobs one-by-one in this ordering. This is known as Smith's Rule and proved by an obvious
exchange argument.
Dening d 0 := 0 and e i := d i d i 1 , the expected target completion time OPT in the
optimal solution can be written as
Now we start comparing dierent players. First consider an adversary who selects the
but not the target. If we adopt RE as competitive ratio, this adversary has to use
Smith's Rule to minimize her expected costs, such that OPT becomes the denominator in
RE.
Suppose that the on-line player also knows the p i but not the c i (Scenario 1). For the
special case p 1=n, it has been shown in [12] that the simple Round Robin algorithm that
devotes equal time fractions to all jobs not nished yet gives the optimal competitive ratio
n+1 . (The result in [12] refers to minimizing the sum of completion times, but this is
obviously an equivalent formulation.) We generalize the asymptotic competitive ratio 2 to
arbitrary \weights" p i by the following strategy.
Weighted Round Robin (WRR):
Assign fractions of time proportional to the p i to the jobs not yet completed.
Theorem 3.1 WRR has competitive ratio RE < 2 against an adversary who knows the
target probabilities and decision times but not the target.
Proof. Just by the denition, d k would be the completion time of job k if we constantly
assigned time fraction p k to it, and e k would be the time between completion of jobs k 1
and k. From the rule of WRR and d 1 that also WRR completes all
jobs in the ordering of indices, but the intervals between completions are reduced by factor
since only these jobs are still under processing. Now we can calculate the expected
completion time WRR of the target job:
ik
i<k
which nally gives
For any xed k we have
ik
It follows
:In contrast to RE, one can only get poor ER:
Theorem 3.2 WRR achieves ER  n, and any deterministic strategy has competitive ratio
ER  n=2.
Proof. For the upper bound, just remember that WRR completes job k before time
ER <
For the lower bound, consider instances with some sequence of real
numbers rapidly increasing with i. If the target job is i, the adversary needs only slightly
more than c i time. Since the on-line player does not know the c i , we may assume instead that
she is told the fact that c 1 but not the numbering of jobs. Given any deterministic
on-line strategy, we construct an instance that fools it: At an arbitrary moment, the strategy
has devoted at most 1=n of the time to some job. Decide that this is job 1, and let c 1 be
the time the strategy has spent on it. Then wait much longer than c 1 time units. At any
later moment, the on-line player has devoted at most 1=(n 1) of the time to some of the
remaining jobs. Dene c 2 similarly as above, and so on. By this indexing, the on-line player
nds target i not earlier than at time (n . The cost ratio averaged over all targets
is roughly n=2. 2
3.2 On-line completion time vs. target decision time
In the remainder of the paper we consider an omniscient adversary who even knows the
target, corresponding to the \retrospective regret" reasoning in the Introduction. That
means, the adversary needs only time c i if object i is the target. An on-line strategy that
completes the ith job at time T i achieves
Now we are going to study on-line players with dierent levels of prior knowledge.
First suppose that the on-line player knows the p i and c i . Then a one-by-one schedule
where the jobs are ordered by non-decreasing c 2
optimal with respect to ER. (This
follows immediately from Smith's Rule if we look at the weighted sum of completion times
with weights p i =c i .) On the other hand, the objective to minimize RE requires to sort
the jobs by non-decreasing c i =p i . This can lead to dierent schedules depending on which
expected value one wishes to optimize: ER measures the time wasted on false candidates
relative to the target decision time, whereas RE is proportional to the expected target
completion time. Therefore the ER-minimizing strategy gives more favor to shorter jobs.
(It might be interesting to discuss if there is a natural interpretation of the schedule with
non-decreasing c
for an arbitrary exponent .)
However, we assume in the remainder of this section that the on-line player is ignorant of
the c i , but still knows the p i . Then she has to start with a WRR type strategy, otherwise the
competitive ratio can be arbitrarily large. W.l.o.g. the weights in a deterministic strategy
remain constant in time, as long as no candidate has been discarded.
We make the adversary even stronger (Scenario 2): First the target j is chosen according
to given probabilities p j . Then the adversary xes the c i conditional on the target. Trivially,
it is always good for the adversary to make the non-target decision times much larger than
may simply consider them as innite. This is an appropriate adversary model in
cases where the on-line player has a verication criterion for the target, but no falsication
criteria for non-targets. Note that the on-line player does not learn anything new during
the process, until the target is recognized. Therefore we let w.l.o.g. the weights xed all the
time. We aim at a minimum competitive ratio ER.
Let x i be the constant time fraction devoted to the ith candidate
Lemma 3.3 Given positive numbers
under the constraint
xed X, are x
results in
Proof. For any positive constants p; q; a, the function p=x+q=(a x) attains its minimum
It follows easily that our objective function is minimized if the x i are
proportional to the p p i . 2
Root:
For every i, constantly devote the fraction x
time to job i.
Since we have our problem, this choice of x i gives the best ER, which equals
We call Q the square root entropy of distribution pn . It satises
are equal. One may claim
that Q plays a similar role in our search problem as e.g. the Shannon entropy in searching
by comparisons, so far as it measures the expected amount of work needed to nd an item
under a given probability distribution. The dierence to Shannon entropy (square roots
instead of negative logarithms) comes from the fact that the mechanism to gain information
is quite dierent. We remark that several notions of entropy are in use in dierent contexts.
Anyway, we have shown:
Theorem 3.4 Root satises against an o-line player who knows the target, and
this is the optimal competitive ratio for xed-weight strategies. 2
The result suggests the idea to extend Root straightforwardly to the model with a
weaker adversary who has to x the c i before the target is selected: Always keep the x i
proportional to the p p i , such that
the sum is taken over all jobs not
nished yet. Since the xed-weight strategy cannot be better, we get ER  Q.
3.3 Monotone but unknown target probabilities
In all the previous considerations, the on-line player was aware of the p i . Now consider the
opposite case that she is completely ignorant of the p i . In other words, the p i are not part
of the signal, such that the on-line player does not know which chance node the adversary
has selected.
If also the c i are unknown then the optimal deterministic on-line strategy is RR, with
equal fractions x i . It trivially guarantees other strategy can be
worse: The adversary may set the most slighted job as the target, with probability 1, such
that the competitive ratio becomes greater than n.
We remark that, if the on-line player knows the c i (but not the p i ) then her best deterministic
strategy is to process the jobs one-by-one in order of non-decreasing c i . It guarantees
no other strategy can be better in the worst case: Let j
be the index which maximizes this expression. Note that some of the rst j jobs cannot be
completed earlier than at time T
is completed at T j or later,
then the associated object is made the target with probability 1. Since c i  c j and i takes
over the role of j, the competitive ratio can only be worse.
Interestingly, the on-line player can do better if the ordering of the p i is known, though
not their values (Scenario 3). W.l.o.g. assume that the on-line player knows
For a specic motivation see Section 1.
Once more, the on-line player is in the worst position if she does not know the c i , and the
adversary even knows the target and can x the c i after target selection. As Theorem 3.4
provides the lower bound Q in case of known p i , it is natural to ask how much performance
the on-line player looses by not knowing the p i . That means to give the competitive ratio in
terms of Q. We propose the following strategy. As usual,
1=i denotes the n-th
harmonic number.
Harmonic:
Apply WRR with x
We remark that Harmonic can be approximately realized in a nice incremental way: In
round time slot is devoted to all objects i where i divides r.
I :=
which is the expected index of the target if objects are sorted
by non-increasing target probability. Obviously, Harmonic achieves ER
I . To establish an upper bound in terms of Q we observe that the expected
index I is related to Q:
Lemma 3.5 For any p 1
Proof. By monotonicity, we have appears twice
in the right hand side if i 6= j and once if From these observations we obtain
It follows 2I 1  Q. Together with the preceding calculation this shows:
Theorem 3.6 For monotone p i , Harmonic achieves competitive ratio ER  Hn I <
against an adversary who knows the target. 2
We show that the result is optimal in the following sense:
Theorem 3.7 No deterministic strategy can guarantee
Proof. The on-line player has to x the x i without knowing the p i , while the adversary
can choose, in particular, one of the n distributions where the rst k objects (1  k  n)
have the same target probability 1=k. Note that
The minimum over all x
is a worst-case lower bound
on ER=Q. Consider an optimal solution x xn such that S is minimized. We derive
some further properties that an optimal solution w.l.o.g. enjoys.
First of all we can suppose x by an obvious argument: If some x k < x k+1 ,
then exchanging these two values decreases S k and does not increase other S i .
Consider a pair x k > x k+1 . If we transfer a small amount from x k to x k+1 , then S k
increases, and all S i with i > k decrease, as long as we keep x k  x k+1 . Thus we reach
either increasing S. A sequence of such manipulations cannot
run into a cycle, since transfer goes to higher indices only. Thus we can also suppose that
Next consider a sequence x k > x . Due to the previous
discussion suppose S form an arithmetic
sequence,
convex function of j. It follows S k+j > S for 0 < j < m, contradiction. Thus a sequence of
several equal x i is necessarily prex or su-x of x . The prex case can be excluded:
Hence there exists a cut-o point c such that S
are equal. However if actually c < n then Sn < S by the same convexity argument. Then
we can nally transfer a small amount from xn to x 1 , such that all S i except Sn properly
decrease, and Sn remains below S. This contradicts the minimality of S. We obtain that
w.l.o.g. all S k are equal.
The
quadratically, hence the 1=x k grow linearly, which means that the
behave like a harmonic sequence. From this, the lower bound follows. 2
4 Targets That Give Random Signals
4.1 Adversarial instances, random signals (AIRS) and a Bayesian
model
In the AIRS setting, the target is freely chosen in the adversarial root of the tree. If object
t is the target then, in the chance node for t, signal s is forwarded to the on-line player with
probability p(sjt) (where
every t). The adversary xes decision time c t
as soon as she knows the target. To avoid technicalities we restrict our presentation to the
case of nite sets of targets and signals, although extensions are possible.
We have described these assumptions in Scenario 4. The Bayesian setting is similar,
but the target is chosen according to prior probabilities rather than by the adversary. In
the simplest case we may set all prior probabilities to 1=n, if there is no reason to prefer a
candidate. Conditional signal probabilities p(sjt) are introduced as above.
For the same reasons as discussed earlier, the adversary would make all non-target decision
times innite, and the on-line player can restrict herself to xed-weight Round Robin
strategies.
Let T st be the time that the on-line player needs to nish the target job if the target is t
and signal s is received. (Remember that costs of actions depend on t only, but the on-line
strategy may depend on s, hence the completion time depends on both.) According to the
denition of competitive ratio ER, we have
s p(sjt)T st =c t in the AIRS model
and
s p(sjt)T st =c t in the Bayesian model with equal priors. Note that T st =c t
is the on-line player's multiplicative regret for the particular state (t; s).
Let x(tjs) be the time fraction devoted by the on-line strategy to object t if the signal
was s. The strategy is completely characterized by these x(tjs). Since T st
we get
s p(sjt)=x(tjs) in the AIRS model. In the Bayesian model, replace
t . We wish to x the x(tjs) so as to minimize ER, under the constraints
4.2 The optimal solution in the AIRS model
Lemma 4.1 In an optimal solution to the above scheduling problem, all terms
s p(sjt)=x(tjs)
are equal.
Proof. Consider any solution, some s, and dierent targets t; t 0 . If we
but change the summands, we can lower the sum for one target and raise it
arbitrarily for the other target. After a sequence of such changes we can raise the sums for
all targets except one to the current maximum. Finally raise the unique smallest sum and
let the others equally decrease, until all sums are equal. Details are straightforward. 2
Lemma 4.1 and the following conclusion can be generalized to any AIRS problem where,
within the set of available strategies, costs can be continuously exchanged between targets
in this way.
Lemma 4.2 Let t 1 be one of the target objects. Minimizing
under the
original constraints
and the further constraints
is equivalent to the problem of minimizing ER.
Proof. Since any feasible solution to the new problem has to satisfy the original con-
straints, it is also a feasible solution to the original problem. Conversely, by Lemma 4.1, an
optimal solution to the original problem is among the feasible solutions to the new problem.Since the new objective function from Lemma 4.2 is dierentiable, we can apply La-
grange's method. The Lagrange function is
s
s
s
s
Dening an extra factor  t 1
t , we can write this more compactly:
s
s
This also takes away the articial distinction of one target, at cost of an additional constraint:
1. The derivatives are
For a system of x(tjs) to be an extremum, all these derivatives must be 0. This yields
The signal-wise constraints
p(sjt). Using abbreviation
we may now write the time fractions of the on-line schedule as
p(sjr). Thus, in an optimal solution, the x(tjs) for any xed s
are proportional to weighted
p(sjt), where the weights w t depend on the target only, in
other words, they are equal for all signals. The weights must satisfy
1. Using the
introduced notion, the competitive ratio is
s
r
Let us minimize the inner product for any xed s, for the moment ignoring the demand
that the weights have to be independent of s. By the Cauchy-Schwarz inequality, this
product is at least (
. On the other hand, this lower bound is achieved if all w t
are equal. Therefore the weights minimizing each summand of the outer sum are already
independent of s, such that the whole expression is minimized if weights are equal. This
shows:
Theorem 4.3 Taking
r
p(sjr) gives the best ER which isn
This resembles the Root strategy from Theorem 3.4. The terms dened by Q(s) :=
can be interpreted as square root entropies of target likelihoods for a given
signal, although the p(sjt) for given s do not sum up to 1. Hence the Theorem says that the
competitive ratio is the average square root entropy.
Due to the denitions, any strategy for the AIRS model yields the same ER, or a better
one, also in the Bayesian model. The Lemmas imply that the optimal strategy for AIRS
yields the same ER for all prior target probabilities. It remains open whether the Bayesian
ER can be improved.
4.3 Totally ordered targets and one-sided signals
We refer to Section 1 and 2.3 for the motivation and problem statement, and for the denition
of target candidates t i , signals s i , and expressions L i , so that we can right away apply the
previous result.
Lemma 4.4 For i  j we can write
(By convention let the product be 0 if i > j, and 1 if
Proof. Clearly,
:Applying the optimal strategy we get x(t j js i
r L
calculation shows for a regular pattern of targets (with
Proposition 4.5 If equidistant targets are given then the competitive ratio is not larger
than
Proof. By Theorem 4.3 and Lemma 4.4 we have
ER =n
lack knowledge of the signal probabilities but still know that, for any s i , the
likelihood p(s i jt j ) decreases as j grows, we may apply Harmonic to the target candidates to
the right of the actual signal. Due to Theorem 4.3, Q(s i ) is the optimal competitive ratio for a
given signal s i , if the p(s i jt j ) were known, and Theorems 3.6 and 3.7 say that Harmonic then
yields (up to a constant factor) minimal deterioration compared to Q(s i ). Unfortunately,
this intuitive argument does not imply an upper bound like \uniformityO(log n)" on the
competitive ratio in the AIRS framework. We leave such a bound as an open question. Here
we can only establish a weaker result in the Bayesian model with uniform distribution on
the target candidate set. The on-line player's unawareness of the p(s i jt i ) is modeled by the
rule that the adversary can freely choose the n target candidate points on the real axis, but
then she has to take a random target from this set.
Proposition 4.6 Under the above assumptions, Harmonic achieves
Proof. The probability to sample t j and s i is 1
The probability to get s i is
therefore 1
xed s i , the posterior likelihoods of targets are proportional
to p(s i jt j ) and thus decrease with j. (Here we must make use of the uniform target
distribution.) Now we can directly apply Theorem 3.6 which does not rely on
and get log n) on condition that s i was the signal. Weighing over the total
probabilities of signals gives the result. 2
5 A Result for Known Bounds on Decision Times
In the previous sections we distinguished between known and unknown decision times only.
However one may at least be able to estimate a smallest and largest time needed for checking
an object, i.e. the on-line player knows intervals [a This surely in
uences the
competitive ratio. Recall from Section 3 that optimal schedules look very dierent in the
two extreme cases a 1. Thus it is interesting to study the cut-o or
the transition between one-by-one and RR schedules.
However this generalization raises di-cult problems in our probabilistic models. Here we
can add one result in a simpler setting only: Suppose that the adversary can freely choose
a target i and the c i in the given intervals (Scenario 5). We propose the following strategy.
Interval Round Robin (IRR):
Let t be a positive real parameter growing in time (which should not be confused with time
itself ), and devote time to the jobs in such a way that the following remains true at every
moment and for every job i:
As long as t < a i , job i has not been started yet.
- If a i  t  c i then the time already spent on the job is t.
Note that this invariant implies that IRR proceeds exclusively with the job i for a time a i
when t reaches a i (and t remains constant during this period), and that IRR always assigns
fractions to all currently running jobs which are the jobs with [a t. If we
visualize work on the t-axis, the real time runs by an integer factor faster than t grows,
namely by the number of running jobs. Moreover t may jump instantaneously from some b i
to the next larger a j if there is no interval [a k ; b k ] in between.
Theorem 5.1 IRR gives the optimal competitive ratio for every interval system [a
against an adversary who can choose both the target and the decision times within the given
intervals.
Proof. For any choice of the c j , the competitive ratio of IRR is R :=
a
1. The adversary may adjust the c j such that R be maximized. (We remark that
these c j are easy to compute, observing that every c j can w.l.o.g. be chosen as some of the
a This should not be misinterpreted in the way that the on-line player knew the
actual c j , instead they will be xed below, depending on the on-line strategy. Let Rmax be
the largest R, maximized over all c j .
We show that Rmax is the optimal competitive ratio for deterministic on-line players, by
giving a malicious adversary strategy: Consider j and c j where R achieves Rmax . Select the
jobs i with b i < c j or a i  c j  b i as possible targets. Call them short jobs and long jobs,
respectively. Given an on-line strategy, consider the rst moment when the time spent on
every long job has reached c j . Call the long job that reached c j last the slow job. If all short
jobs have already reached their respective b i then take the slow job as target. In the other
case, i.e. if some short job did not reach its b i yet, wait until the last short job did so, and
then choose this short job as target. In both cases, the competitive ratio exceeds Rmax . 2
6 Further Research
As mentioned, it remains to study scheduling with bounded decision times in probabilistic
models. There are several other easy-to-motivate problem versions, both with known and
unknown decision times and target probabilities, and with dierent standards of comparison.
Our ongoing research addresses some of them.
Randomized strategies could improve some competitive ratios, but not all. No substantial
improvement can be expected in Scenario 1, due to the negative result for the uniform case
in [12]. In Scenario 2 (and 3), the best choices for the adversary are clear, so the game
reduces to a Bayesian situation where randomization is useless. We leave the question open
In Scenario 5 one can denitely gain something by randomization, as one can
balance the
a
1 for several jobs j, however the details of an optimal
strategy seem to be tricky.
Games with several competing searchers (where the rst who nds the target wins) can
also model situations in the world of research, and good strategies may become very dierent
compared to one-party games against nature. Searching for more than one target could be
another natural generalization with new mathematical challenges.

Acknowledgments

Special thanks to Tommy Martinsson (Clinical Genetics, Sahlgrenska University Hospital,
Gothenburg) for vivid discussions about the biological side, and to Olle Nerman (Mathe-
matical Statistics, Chalmers) who brought us together. I also thank the referees for several
comments which helped much to improve the organization of the paper.



--R

Searching in the plane.


Online weighted ow time and deadline scheduling.
Online Computation and Competitive Analysis.
Preemptive scheduling in overloaded systems

Beyond competitive analysis.
Scheduling jobs before shut-down
Online parallel heuristics and robot searching under the competitive framework.

Nonclairvoyant scheduling.

--TR
Searching in the plane
Nonclairvoyant scheduling
Online computation and competitive analysis
Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines
Beyond Competitive Analysis
Scheduling jobs before shut-down
Online Parallel Heuristics and Robot Searching under the Competitive Framework
Preemptive Scheduling in Overloaded Systems
Non-clairvoyant Scheduling for Minimizing Mean Slowdown
Online Weighted Flow Time and Deadline Scheduling
On-line Scheduling

--CTR
Peter Damaschke, Scheduling search procedures: The wheel of fortune, Journal of Scheduling, v.9 n.6, p.545-557, December  2006
Anders Bergkvist , Peter Damaschke , Marcel Lthi, Linear Programs for Hypotheses Selection in Probabilistic Inference Models, The Journal of Machine Learning Research, 7, p.1339-1355, 12/1/2006
searching;bayesian models;on-line algorithms;randomized adversary