Improved Online Algorithms for Buer Management in QoS Switches

发布于:2021-09-17 08:58:41

?????? ??? ? ? ?? ? ?× ?? ?? ? ? ? ? ?? ? ??? ?? ? ×
? ? ??

?

??



? ???

?

? ?

?

??

?

??? × ? ?

?

×?? ?
We consider the following bu?er management problem arising in QoS networks: packets with speci?ed weights and deadlines arrive at a network switch and need to be forwarded so that the total value of forwarded packets is maximized. If a packet is not forwarded before its deadline, 64 it is lost and brings no pro?t. The main result of the paper is an online 33 1 939-competitive algorithm – the ?rst deterministic algorithm for this problem with competitive ratio below 2. We also study the ×-?? ??? case, in which all packets have the same span × (the di?erence between ? the deadline and the arrival time), for which we give an algorithm with ratio 5 ? 10 1 838. Our algorithm achieves the same ratio in a more general scenario when all packets are similarly ordered. Our last two results concern the 2-uniform case, for which we give an algorithm with ratio 1 377 and a matching lower bound.

?

????? ? ? ??

One of the issues arising in IP-based QoS networks is how to manage the packet ?ows at a router level. In particular, in case of overloading, when the total incoming tra?c exceeds the bu?er size, the bu?er management policy needs to determine which packets should be dropped by the router. Kesselman ? ?? [6] postulate that the packet drop policies can be modeled as combinatorial optimization problems. Of the two models proposed in [6], the one relevant to this work is called ?? ? ? ? ? ?? ? ? ??? ? ?, and is de?ned as follows: Packets arrive at a network switch. Each packet is characterized by a positive weight and a deadline before which it must be transmitted. Packets can only be transmitted at integer time steps. If the deadline of a packet is reached while it is still being bu?ered, the packet is lost. The goal is to maximize the weighted number of forwarded packets. It is easy to see that this bu?er management problem is equivalent to the online version of the following unit job scheduling problem. We are given a set of unit-length jobs, with each job speci?ed by a triple (? ? ), where ? and are integral release times and deadlines, and ? is a non-negative real weight. One job can be processed at each integer time. We use the term ? ? ? ??? ??? or ? for the total weight of the jobs completed by their deadline. The goal is to compute a schedule that maximizes the weighted throughput.
? ??? ?? ? ????? ? ? ? ? ?? ? ?× ?? ? ? ??? ? ? ? ?× ? ? ??? ??????? ? ?? ? ??× ?? ? ? ? ????? ? ? ? ??? ?  ×?? ?? ? ? ? ? ? ? ? ??×? ??? ? ? ?? ?? ? ? ??? ?? ?? ? ? ?? ? ? ? ?? ??? ×?????? ? ??×? ??? ?? ? ?? ? ? ????? ? ? ? ? ?? ? ???? ? ???? ? ? ???? ?? ? ? ?? ??? ?? ? ? ?? × ???? ? ? ? ? ×? ?
?

1

In the online version of the problem jobs arrive in time and the algorithm needs to schedule one of the pending jobs without knowledge of the future. An online algorithm is ?? ??? ? ? ? if its gain on any instance is at least 1 ? times the optimal (o?ine) gain on this instance. The ??? ? ? ? ? ? ? of is the in?mum of such values ?. It is common in the literature to view the as a game between and an ? ?× ??, who issues the jobs in behavior of an online algorithm ? and schedules them in order to maximize the ratio between his gain and and the gain of . A simple greedy algorithm that always schedules the heaviest available job is 2competitive, and this is the best previous bound for deterministic algorithms for this problem. A 1 618 was shown in [1, 4, 5]. lower bound of Some restrictions on instances of the problem have been studied in the literature [6, 1, 4]. Let the span of a job be the di?erence between its deadline and the release time. In ×??? ??? ?×? ? × the span of each job is equal exactly ×. In ×? ??? instances, the span of each job is at most ×. 1 618 in [1, 4, 5] applies even to 2-bounded instances. A matching upper The lower bound of bound for the 2-bounded case was presented in [6]. The algorithms for the 2-uniform instances ? were studied by Zhu ? ?? [1], who established a lower bound of ? ( 3 + 1) 1 366 and an upper ? ? bound of 2 1 414. This bound is tight for memoryless algorithms [2], that is, algorithms which base their decisions only on the weights of pending jobs and are invariant under scaling of weights. Finally, the ?rst deterministic algorithms with competitive ratio lower than 2 for the ×-bounded instances appear in [2]. These ratios, however, depend on ×, and approach 2 as × increases. A randomized 1 582-competitive algorithm for the general case was given in [2]. For 2-bounded instances, there is a 1 25-competitive algorithm [2] and this is optimal [4]. For the 2-uniform case the currently best lower bound for randomized algorithms is 1 172 [2].
? ×? ??? ?

We present several deterministic online algorithms for the bu?er management problem. Our main result is a deterministic ?? 1 939-competitive algorithm for the general case. This is the ?rst deterministic algorithm for this problem with ratio better than 2. ? For the ×-uniform case, we give an algorithm with ratio 5 ? 10 1 838, independent of ×. In fact, this ratio holds in a much more general scenario when all jobs are similarly ordered, that is, ? implies for all jobs . Finally, we completely solve the 2-uniform case: we when ? give an algorithm with competitive ratio 1 377 and a matching lower bound. Note that this ratio is strictly in between the previous lower and upper bounds from [1].
??? ? ×???×?

?

? ?? ???? ?

?

??? ? ??

A × ?? ? speci?es which jobs are executed, and for each executed job it speci?es an integral time ?, ? ? , when it is scheduled; only one job can be scheduled at any ?. The ? ??? ??? or ? of a schedule ? is the total weight of the jobs executed in ? . If is a scheduling algorithm, by ? (? ) we denote the gain of the schedule computed by on ? . The optimal gain on ? is ? and has not been denoted by ???(? ). A job is ? ? ? in schedule ? at time ? if ? scheduled before ?. Note that all jobs released at time ? are considered pending. An instance is ×? ??? if ? ? × for all jobs . Similarly, an instance is ×??? ??? if ? ? = × for all . The di?erence ? ? is called the ×? ? of a job . An instance is called × ? ? ??? ?? ? when the release times and deadlines are similarly ordered, that is if ? ? implies for any two jobs and . Given two jobs , we say that ?? ? ? × if either (i) , or (ii) = and ? ?, or (iii) = , ? = ? and . ((iii) only ensures that ties are broken in some arbitrary but 2

consistent way.) Given a non-empty set of jobs ? , the ?? ? ?? job in ? is the one that dominates all other jobs in ? ; it is always uniquely de?ned as ‘dominates’ is a linear order. A schedule ? is called ??? ? ?? ×?? ? ? if for any jobs scheduled in ? at time ? and scheduled later in ? , either is released strictly after time ?, or dominates . I.e., at any time ?, the job scheduled by ? is the dominant pending job in ? . Any schedule can be easily converted into a canonical earliest-deadline schedule by rearranging its jobs. Thus we may assume that o?ine schedules are canonical earliest-deadline.
?
64 33 ?

??? ? ? ?

? ?? ? ?

We start with some intuitions that should be helpful in understanding the algorithm and its analysis. The greedy algorithm that always executes the heaviest job (H-job) is not better than 2-competitive. An alternative idea is to execute the earliest deadline job at each step. This algorithm is not competitive at all, as possibly many jobs of very small weight are executed even if there are heavy jobs pending with only slightly larger deadlines. A natural re?nement of this approach is to focus on su?ciently heavy jobs, of weight at least ? times the maximal weight, and chose the earliest deadline job among those (an E-job). As it turns out, this algorithm is also not better than 2-competitive. The general idea of our new algorithm is to alternate H-jobs and E-jobs. Although this simple algorithm, as stated, has ratio no better than 2, with several seemingly minor modi?cations, we can achieve competitive ratio smaller than 2.
? ?? ? ? We use parameters ? = ?? and ? = ?? and a boolean variable ? , initially set to ?× , that stores information about the previous step. At a given time step ?, update the set of pending jobs (remove jobs with deadline ? and add jobs released at ?). If there are no pending jobs, go to the next time step. Otherwise, let be the heaviest pending job (breaking ties in favor of dominant jobs) and the dominant job among the pending jobs with weight at least ?? . Schedule either or according to the following procedure:

? ?

?


= ?× ? ? schedule = ? ? set set

?

???

?



= ? + 1 and schedule



?

?? ? ? schedule

A job scheduled while ? = ?× is called an ?? ? if = , or an ? ? otherwise. A job scheduled while ? =??? is called an ?? ? . A job scheduled in the last case is called an ?? ? . The letters stand for ?bvious, arly, ?rgent, and ?eaviest. Variable ? is ??? i? the previous job was an E-job. Thus, in terms of the labels, the algorithm proceeds as follows: If an O-job is available, we execute it. Otherwise, we execute an E-job, and in the next step either a U-job (if available) or an H-job. Note that the condition = guarantees that there is a pending job if ? is ??? : if = ? then = by the de?nition of dominance; so if an E-job is executed at time ?, ? and will be pending in the next step.
? ?? ? ???

? ?

×

??

? ??? ? ? ?

? ?? ? ×? ? ?? ? ? ?? ?? ?? ? ×
3

?? ? ?

???? The proof is by a charging scheme. Fix an arbitrary (o?ine) schedule ?. For each job executed in ?, we partition its weight ? into several ? ×, and assign each charge to a job executed by ? ? . If the total charged to each job of ? ? were at most ?? , the ?-competitiveness of ? ? would follow by summation over all jobs. Our charging scheme

into disjoint does not always meet this simple condition. Instead, we divide the jobs of groups, where each group is either a single O-job, or an EH-pair (an E-job followed by an H-job), or an EU-pair (an E-job followed by a U-job). This is possible by the discussion of types of jobs before the theorem. For each group we prove that its ? ? ? ? ? is at most ?, where the charging ratio is de?ned as the total charge to this group divided by the total weight of the group. This implies is ?-competitive by summation over all groups. that

? ?

be the job executed at time ? in . Denote by and , respectively, the job executed by and the heaviest pending job at time ?. (If there are no pending jobs, introduce two “dummy” jobs of weight 0. This does not change the algorithm.) Then is charged to ’s jobs, according to the following rules. (EB) If is executed by before time ?, then charge (1 ? ? )? to and the remaining ? ? (1 ? ? )? to . (EF) Else, if is executed by after time ?, then charge ?? to and (1 ? ? )? to . (NF) Else, if is an H-job, ? ?? , and executes after time ?, then charge ?? to and (1 ? ? )? to the job scheduled by at time ? + 1. (U) Else, charge ? to . (Note that this case includes the case = .) We label all charges as EB, EF, NF, U, according to which case above applies. We also distinguish upward, forward, and backward charges, de?ned in the obvious way. Thus, for example, in case (EB), the charge of ? ? (1 ? ? )? to is a backward EB-charge. The letters in the labels refer to , and to the charge direction: xecuted- ackward, xecutedwhether was executed by orward, ?on-executed- orward, ?pward. We start with several simple observations that will be used later in the proof, sometimes without explicit reference.
? ? × ? ?

? ?

Let

? ?

?

? ?

? ?

? ?

? ? ?

? ?

Suppose that at time ? schedules a job of type O or E, and is the heaviest pending job at time ?. Then (3.1) The upward charge to is at most ? . (3.2) If executes after time ? then the upward charge is at most ?? . (3.3) The forward NF-charge to is at most (1 ? ? )? . ???? Denote by the job executed at time ? in . If is scheduled by before time ?, then the upward charge is (1 ? ? )? ?? and claims (3.1) and (3.2) hold. Otherwise is
? × ?? ? ?? ?

? × ?? ? ?? ? Suppose that at time ? schedules a job that receives a forward NFcharge from the job ? scheduled at time ? ? 1 in . Then ? is pending at time ?. ???? Denote by the heaviest pending job of at time ? ? 1. By the de?nition of ? + 1, and ?? ?? . NF-charges, ? = , ? is pending at time ? ? 1, is executed as an H-job, Therefore ? ? + 1, since otherwise would execute ? (or some other job) as a U-job at step ? ? 1. Thus ? is also pending at step ?, as claimed.

Consider the execution of . At time ?, let be the heaviest job and the dominant job of weight at least ?? . Let be any pending job. Then (1.1) ? ?. (1.2) If dominates then ? ?? . ???? Inequality (1.1) is trivial, by the de?nition of . Inequality (1.2) follows from the fact that dominates all pending jobs with weight at least ?? .
? × ?? ? ?? ?

? ?

? ?

?

? ?

? ?

? ?

?

?

? ?

4

pending at time ?. Then the upward charge is at most ? ? and (3.1) follows. If executes after time ?, then, since is canonical, job must dominate , and (3.2) follows from (1.2). (3.3) follows by Observation 2 and (1.1). ? × ?? ? ?? Suppose that at time ? executes an H-job that is executed after time ? in . Then the upward charge to is at most ?? . ???? Let be the job executed at time ? in . In case (EB), the upward charge to is at most (1 ? ? )? ?? . In all other cases, is pending at time ?, so ? ? . In cases (EF) and (NF), the charge is ?? ?? . In case (U) the charge is ? , but since (NF) did not apply, this case can occur only if ? ?? . This completes the proofs of all observations. Now we examine the charges to all groups in our partition of ’s jobs: single O-jobs, EH-pairs, and EU-pairs. ?? ? ×? Let = be an O-job executed at time ?. The forward NF-charge is at most (1 ? ? )? . If gets a backward EB-charge then gets no forward EF-charge and the upward charge is at most ?? ; the total charging ratio is at most 2 + ? ? ? ?. If does not get a backward EB-charge then the forward EF-charge is at most (1 ? ? )? and the upward charge is at most ? ; the charging ratio is at most 3 ? 2? ?. ? ? ×? Before considering EH-pairs and EU-pairs, we estimate separately the charges to E-jobs. executes an E-job , and the heaviest job is . We claim that Suppose that at time ? is charged at most ?? + (2 ? ? )? . We have two cases. Case 1: gets no backward EB-charge. Then, in the worst case, gets an upward charge of ? , a forward NF-charge of (1 ? ? )? , and a forward EF-charge of (1 ? ? )? . Using (2 ? ? )? = 2?? and ?? ? , the total charge is at most (2 ? ? )? + (1 ? ? )? ?? + (2 ? ? )? as claimed. Case 2: gets a backward EB-charge. Then there is no forward EF-charge and the upward charge is at most ?? by (3.2). Let ? be the job scheduled at time ? ? 1 in . If there is an NF-charge, at time ? by Observation 2. it is generated by ? and then ? is pending for If there is a forward NF-charge and ? , then ? is pending at the time when schedules . (Note that in this case job ? cannot be executed by , because charges EB, EF did not apply to ?.) Consequently, receives at most a backward EB-charge ? ? (1 ? ? )?? , a forward ?? + (2 ? ? )? NF-charge (1 ? ? )?? , and an upward charge ?? . The total is at most ?? + ? as claimed. Otherwise, there is no forward NF-charge, or there is a forward NF-charge and ? . In the second case, ? is pending at ?, and ? dominates , so the forward NF-charge is at most (1 ? ? )?? (1 ? ? )? . With the backward EB-charge of ? and upward charge of at most ?? , the total is at most ?? + (2 ? ? )? as claimed. ??? ?×? Let be the E-job scheduled at time ?, the heaviest pending job at time ?, and ? the H-job at time ? + 1. By the algorithm, = . Note that, since did not execute as a O-job at time ?, is still pending after the E-step and ? ? ? . We now estimate the charge to ? . There is no forward NF-charge, as the previous step is not an H-step. If there is a backward EB-charge, the additional upward charge is at most ?? ? and the total is at most (1 + ? )? ? . If there is no EB-charge, the sum of the upward charge and a forward EF-charge is at most ? ? + (1 ? ? )? ? (1 + ? )? ? . With the charge to of at most ?? + (2 ? ? )? , the total charge of the EH-pair is at most ?? + (2 ? ? )? + (1 + ? )? ? , and thus the charging ratio is at most

?

?

?

? ?

?

? ?

? ?

? ?

?

? ?

?

? ?

2??+

??

+ (2? ? 1)? ? +? ?

?

2??+

??

+ (2? ? 1)? ?? + ? ?

?

2?? +

? + 2? ? 1 ?+1

=?

5

The ?rst step follows from ? the maximum is at ? ? = ? .
??? ?×?

??

. The next expression is decreasing in

?

?

as 2?

?1

1, so

As in the previous case, let , and denote the E-job scheduled at time ? and the heaviest pending job at time ?. By and ? we denote the scheduled U-job and the heaviest pending job at time ? + 1. As in the case of EH-pairs, = and ? ? ? . Job gets no backward EB-charge, since it expires, and no forward NF-charge, since the previous step is not an H-step. The upward charge is at most ? ? , the forward EF-charge is at most (1 ? ? )? . With the charge to of at most ?? + (2 ? ? )? , the total charge of the EU-pair is at most ?? + (2 ? ? )? + ? ? + (1 ? ? )? , so the charging ratio is at most 2??+

??

?

+? ? ?? +?

2??+

?? + (1 ? ? )? ?? + ?? ?

?

2??+

?+1?? ?+?

=?

In the ?rst step, we apply bounds ? ?? and ? ?? ? . The next expression is decreasing in ? ? , so the maximum is at ? ? = ? . Summarizing, we now have proved that the charging ratio to all job groups is at most ?, and the ?-competitiveness of follows. ?

?

?

?

? ?

????

??? ? ? ?

? ?? ? ? ?? ? ? ? ??? ??

?

?? ×

We now consider the case when the jobs are similarly ordered, that is ? ? implies for all jobs . Note that, in particular, this covers the case when all jobs on input have the same span. initially set to ?× . At a given time step ?, update the set of pending jobs (remove jobs with deadline ? and add jobs released at ?). If there are no pending jobs, go to the next time step. Otherwise, let be the heaviest pending job (breaking ties in favor of dominant jobs) and the dominant job among the pending jobs with weight at least ?? . Schedule either or according to the following procedure:
? ?? ? ?

?? ?

We use one parameter

?=

?

10 5

0 633 and a boolean variable

? ,

?


= ?× ? schedule = schedule ;

?

?+1
set

?

? set ?

???

?



A job scheduled while ? = ?× is called an ?? ? if = or = ? + 1, and an ? ? otherwise. A job scheduled while ? =??? is called an ?? ? . The intuition behind the algorithm is very , and, in fact, it is simpler. It schedules O-jobs, if available, and if not, it similar to schedules an E-job followed by an H-job; note that the condition = guarantees that there will be a pending job if ? is ??? .

? ?

?

×

?? ?

?? ? ?? × ? ? ??? ?? ?

??

?? ?

×

5

?×? ? ×?

?

?

10

1 838? ???

???

? ?? ? ×? ? ?? ? ? ?? ?? ?? ?

???? The proof is by a charging scheme. The steps of the algorithm can be divided into single O-steps, and EH-pairs. This is because each E-job must be followed by an H-job, and each H-job
6

must be preceded by an E-job. Similarly as for , we give a charging scheme and show that the charging ratio to each group is at most ?. ? ? × ? ? Let be the job executed at time ? in . Denote by and , respectively, the job executed by and the heaviest pending job at time ?. (Without loss of generality, ? ’s we can assume that such jobs exist.) Let ? = 4 ? 10 0 838. Then is charged to jobs, according to the following rules. at or before time ?, then charge ? to . (EB) If is executed by (NF) Else, if ? + 1 and is an H-job, then charge ?? to and (1 ? ? )? to the job scheduled at time ? + 1. by (U) Else, charge ? to . We start with some general observations. If schedules ? before then ? : if is ? then this follows from the de?nition of canonical schedules, available at the time of scheduling and otherwise from the assumption of similar ordering. ? × ?? ? ?? ? Consider the execution of . At time ?, let be the heaviest job and the dominant job of weight at least ?? . Let be any pending job. Then (1.1) ? ?. (1.2) If dominates then ? ?? . ? × ?? ? ?? ? Suppose that at time ? schedules a job (of type O or E), and is the heaviest pending job at time ?. Then (2.1) The upward charge to is at most ? . (2.2) If executes after time ? then the upward charge is at most ?? . (2.3) The forward NF-charge to is at most (1 ? ? )? . (2.4) If executes after time ? then forward NF-charge is at most (1 ? ? )? . (2.5) If does not execute after time ? then the charge to is at most ?? . The proofs of (1.1)-(2.3) are the same as for . ; since is scheduled later we have For (2.4), let ? be the job executed at time ? ? 1 in . By the de?nition of NF-charges, ? is pending at time ?. This, by the choice of , implies ? that ?? ? and (2.4) follows. In (2.5), does not get a backward EB-charge, the upward charge is at most ? and the forward (2 ? ? )? ? = ?? . NF-charge is at most (1 ? ? )? . The total is at most (2 ? ? )? ?? ? ×? Let be an O-job executed at time ?, and let be the heaviest pending job. By the algorithm, either = or = ? + 1 (i.e., expires). If gets no backward charge, the charging ratio is at most ? by (2.5). If gets a backward EB-charge then ? + 1 and thus = . The upward charge is at most ?? = ?? and the forward NF-charge is at most (1 ? ? )? . So the charging ratio is at most 2 + ? ? ? ?. ??? ?×? Let be the E-job scheduled at time ?, be the heaviest pending job at time ?, and ? be the H-job at time ? + 1. Let and ? be the jobs executed at times ? and ? + 1 in , respectively. By the algorithm, we have = , which implies as otherwise is chosen as . ? + 2 and ? ? ? . Furthermore, Case 1: schedules after time ?. Then ? dominates or ? = , as schedules ? at ? + 1 when is pending. Also, dominates . Thus the U-charges to and ? are each at most ?? . In addition, could receive an NF-charge of at most (1 ? ? )? and the EB-charges are ? + ? ? . The total charge to the EH-pair is at most (2 ? ? )? + 2?? + ? ? , and the charging ratio is at most

? ?

?? ?

?

?? ?

?? ?

?? ?

?

?? ?

?? ?

? ? ?

? ?

?

?

?

?

1+

(1 ? ? )? + 2?? ? +? ?

1+

(1 ? ? )? + 2?? ? +? 7

1+

(1 ? ? )? + 2? =? ?+1

The ?rst inequality follows from ? ? ? , and the next inequality holds because its left-hand side is decreasing in ? ?? (note that 1 ? ? 2?). Case 2: does not schedule after time ?. We estimate the charges to and ? separately. The charging ratio of is at most ? by (2.5). We claim that the upward charge to ? is at most ?? ? . If ? is scheduled before ?, then there is no charge. If ? ? +2, then this follows by the NF-charge de?nition. Otherwise ? and thus ? ? ? ? and ? is pending at ?. Thus ? ? ? , as otherwise ? would be chosen as at time ? (note that = ? by the case condition.) So the upward charge is at most ? ?? ? ?? ? and the claim is proven. The total charge to ? , including a possible EB-charge, is at most (1+ ? )? ? = ?? ? and the charging ratio is at most ?. ?

?

???? ??? ??×? ? ×
In this section we consider 2-uniform instances, where each job satis?es = ? +2. Let ? 1 377 be the largest root of ?? + ?? ? 4? + 1 = 0. First, we prove that no online algorithm for this problem can be better than ?-competitive. Next, we show that this lower bound is in fact tight.
?? ??? ? ???

In this sub-section we prove that no deterministic online algorithm for 2-uniform instances can 1 377. Recall that ? is de?ned as the largest root of have a competitive ratio smaller than ? ?? + ?? ? 4? + 1 = 0. Fix some 0 ? 2? ? 2. We de?ne a sequence Ψ , = 1 2 , as follows. For = 1, Ψ? = ? ? 1 ? ?. Inductively, for 1, let Ψ ·? =

?(2 ? ?)Ψ + 3?? ? 5? + 1 ?(2 ? ? ? Ψ )
? 1??

=

(2 ? ?)Ψ ? (? ? 1)? 2???Ψ

where the second equality follows from
? ??

?? + ?? ? 4? + 1 = 0.
Ψ

1 ? ??

??

?? ?? ? ?

? ? 1? ??? ???? ? ?

× ?? ?

Ψ

??? ? × ??

? ???? Substituting Ψ = ? + 1 ? ?, we get ? ·? = ??????? . If 0 ? 2? ? 2 ? ?, then ? ? ???? 0 ? ·? ????·? ? . Thus 0 ? 2? ? 2 ? ? for all , lim ? ? = 0, and the lemma follows. ?

?

?? ? ?? ? ? × ?? ? ? ? ×? ?? ? ? ? ??

? ?? ? ×? ??? ?

? ?? ? ? ?? ?

2???

??? × ? ? ??? ? ? ?

???? The proof is by contradiction. Assume that there exists a (? ? ?)-competitive algorithm , for some ? 0. We develop an adversary strategy that will force ’s ratio to be bigger than ? ? ?. Throughout this proof, to simplify notation, we will identify jobs by their weight. Thus, when we say “job ?”, we mean the job with weight ?. Such job will be always either uniquely de?ned by the context, or there will be two such identical jobs, in which case one of them can be chosen arbitrarily. At each step ?, we distinguish ?? ? ? ? ? ×, that is, those that were released at time ? ? 1 but not executed, from the newly released jobs. Without loss of generality, we can assume that there is always (except for the last step) exactly one old pending job. (All old pending jobs
8

except the heaviest one can be ignored. The situation with no old pending jobs can be simulated by pretending that we have an old pending job with weight 0.) By a ??? ?? ? ?? we mean a pair ? ? , where ?, ? denote the old pending jobs of and the adversary, respectively. 1 de?ne Let Ψ be the sequence from Lemma 5.1. For = 1?Ψ ??1 and = 2???Ψ (? ? 1)?

?

Note that by the ?rst part of Lemma 5.1 we have 1 for all . We now describe the adversary strategy. Initially, we issue two jobs of some arbitrary weight ?? 0. Both and the adversary execute one job ?? and we enter the con?guration ?? ?? . Suppose now that after ? 1 iterations, the current con?guration is ? ? . The adversary now follows the following steps: (1) issue one job ? executes ? execute ? , ? and halt ?× ( executes ? ) at the next time step issue ? executes ? execute ? , ? , ? , and halt ?× ( executes ? ) at the next time step issue two jobs ? ·? = ?

(2) (3)

execute

?, ?, ?

If executes ?rst ? and then ? , then after step (3) it will execute one job ? ·? = ? , and the new con?guration will be ? ·? ? ·? , and the game continues. The adversary strategy is illustrated in Figure 1, where we assume that ? = 1, and to simplify notation we write = and = . Jobs are represented by line segments, with dark rectangles representing if and when the job is executed by , while the lightly shaded rectangles represent job executions by the adversary. If the game completes ? 1 iterations, then de?ne ? and ? to be the gain of and the adversary in these ? 1 iterations (that is, ending in con?guration ? ? .) We claim that for any , either the adversary wins the game before iteration , or else in iteration we have (? ? ?)

?

?

?

Ψ

?

(1)

The proof of (1) is by induction on . For = 1, (? ? ?) ?? ? ? ? (? ? ?)?? ? ?? = Ψ? ?? , as claimed. Suppose that (1) holds after iteration ? 1, that is, when the con?guration is ? ? . If executes ? in step (1), then, denoting by the sequence of jobs up to this step, using the inductive assumption, and substituting the formula for , we have (? ? ?)

? ( ) ? ? ( ) = (? ? ?)

? ? ? + (? ? ?) ? [Ψ ? 1 + (? ? ? ? 1) ]? 0

? (?

+

?)

contradicting the (? ? ?)-competitiveness of . If executes ? and then ? in step (2), then, ? the sequence of jobs up to this step, using the inductive assumption, and again, denoting by substituting the formulas for , we have (? ? ?)

? ( ? ) ? ? ( ? ) = (? ? ?) ? ? ? + (? ? ?)(? + ? ) ? (? + ? + ? ) [Ψ + ? ? 1 ? ? + (? ? ? ? 1) ? ]? 0
9

11 00 x 11 00
x

adversary move (no new jobs)

11 00x 11 00
x

adversary move

11 00 x 11 00
x ax

algorithm and adversary move

11 00 x 11 00

11 00

x ax

algorithm and adversary move

algorithm move

11 00 x 11 00 111 000 111 000 x

11 00 x 11 00 11 00 11 00 x
ax

adversary move

11 00 x 11 00 11 00 11 00 x
ax bx

algorithm and adversary move

11 00 x 11 00 11 00 11 00 x 11 00
ax bx

next iteration

11 00 x 11 00 11 00 11 00 x 111 000 ax 111 000 bx 11 00 11 00
bx

algorithm and adversary move

algorithm move

11 00 x 11 00 11 00 11 00 x 11 00 ax 11 00

adversary move bx bx

11 00 x 11 00 11 00 11 00 x 11 00 ax 11 00

bx

Figure 1: The adversary strategy. and this again contradicts the (? ? ?)-competitiveness of . The only other possibility is that will execute ?rst ? , then ? , and then it will have no choice but execute ? . In the new con?guration ? ·? ? ·? we will have (? ? ?)

? ·? ? ?

·?

(? ? ?)

[Ψ + ?(1 +

?

?

? + (? ? ?)(? + ? + ? ) ? ( ? + 2 ? ) + ) ? ( + 2 )]? = ? Ψ ·? = ? ·? Ψ ·?

completing the proof of (1). From (1) and from Lemma 5.1, we obtain that for large enough we will have (? ? ?) ? ? ? Ψ ? (1 ? ? + ?)? . But this contradicts the (? ? ?)-competitiveness of , since, denoting by ± the sequence of all jobs issued up to this time (including the pending jobs ? ), we have (? ? ?)

? (±) ? ? (±) = (? ? ?) ? ? ? + (? ? ?)? ? ? (1 ? ? + ?)? + (? ? ?)? ? ? = 0

?
?? ??? ? ???

In this section we present an online algorithm for 2-uniform jobs with competitive ratio ?. Given that the 2-uniform case seems to be the most elementary case of unit job scheduling (without being trivial), our algorithm (and its analysis) is surprisingly di?cult. Recall, however, that any ? algorithm for 2-uniform instances whose competitive ratio is better than 2 cannot be memoryless (see [2]). In other words, in addition to the pending jobs, it needs to use some information about the jobs that were already executed or that expired. Further, when the adversary uses the strategy from the lower bound proof in the previous section, any online algorithm needs to behave in an essentially unique way in order to be ?-competitive. Our algorithm was in fact designed to match 10

this optimal strategy, and then extended (by interpolation) to other adversarial strategies. Thus we suspect that the complexity of the algorithm is inherent in the problem and cannot be avoided. We start with some intuitions. Let be our online algorithm. Suppose that at a certain time ? we have one old pending job ? , and two new pending jobs with . In some cases, the can ignore ? and execute in the current step. decision which job to execute is easy. If ? , If ? , can ignore and execute ? in the current step. If ? , faces a dilemma: it needs to decide whether to execute ? or . In general, the choice will be made based on the ratio ? . If ? exceeds a certain threshold (possibly dependent on the past computation), we execute ? , otherwise we execute . We can handle all three cases by using a parameter, say , and making the decision according to the following procedure:
??? ??

???

If

?

+ (1 ? ) schedule ? , otherwise schedule .

To derive an online algorithm, say , we examine the adversary strategy in the lower bound ?, and let ? = lim ? = ? (? ? 1) and ? = proof. Consider the limit case, when lim ? = ? (? ? 1)? . Assume that in the previous step two jobs ? were issued, so that the current con?guration is ? ? . If the adversary now issues a single job , then needs to do the following: if ? , execute ? , and if ? , then execute . (The tie for = ? ? can be broken ? ? either way.) Thus in this case we need to apply ? with the threshold ? = 1 ? = (? ? 1) ?. Then, suppose that in the ?rst step executed ? , so that in the next step is pending. If the adversary now issues a single job , then (assuming ? ) must to do the following: if ? , execute , and if ? , then execute . Thus in this case we need to apply ? ? ? with the threshold ? = ? ? = ? ? 1. Suppose that we execute . In the lower-bound strategy, the adversary would now issue two jobs in the next step. But what happens if he issues a single job, say ? Routine calculations show that , in order to be ?-competitive, needs to use yet a di?erent parameter in . This parameter is not uniquely determined, but it must be at least ? = (3 ? 2?) (2 ? ?), which is greater than ? ? 1. Further, it turns out that the same value ? can be used on subsequent single-job requests. Our algorithm is derived from the above analysis: on a sequence of single-job requests in a row, with parameter ? in the ?rst step, then ? in the second step, and ? in all subsequent use steps. In general, of course, two jobs can be issued at each step (or more, but only two heaviest jobs need to be considered.) We think of an algorithm as a function of several arguments. The values of this function on the boundary are determined from the optimal adversary strategy, as explained above. The remaining values are obtained through interpolation. We now give a formal description of our algorithm. We de?ne constants

???

???

???

???

?

=

??1 ?

0 27

?

=

??1

0 38

?

=

3 ? 2? 2??

0 39

We also use two functions ( ) = min 1 where 0 1 and ? ( ) 1, ? ?( ) 0 ?(0 ?) = ? , ?(0 ? ) = ? .
? ?? ? ?

?? ???

?(

)=

? + (1 ?

)[? + (? ? ? ) ( )] , within their ranges, we have = ?, ? (0 ) ? for any , and

? . Note that for the parameters ? . Function ? also satis?es ?(1 )

that

?

?) and (where

?? ?

?

Fix a time step ?. Let ? ? be the two jobs released at time ? ? 1 (we assume ) be the jobs released at time ?. Let ? ? ? ? be the old pending 11

job. Let also be the parameter of used at time the job to execute as follows: ? ? If ? = ? run with = ? ( ? ), ? If ? = ? run with = ?.

???

? ? 1 (initially

= ?). Then

?? ?

chooses

??? ???

?

?? ? ?? ? ?? ? ? ?? ? × ?? ??? ? ? ? ?? ? ? ? ×? ???? ? ?? + ?? ? 4? + 1 = 0?

2???

??? × ? ? ? ?

1 377

×?

The proof of the theorem is by tedious case analysis of an appropriate potential function, and is included in the appendix.
?? ??× ??×

We established the ?rst upper bound better than 2 on the competitiveness of deterministic scheduling unit jobs to maximize weighted throughput. There is still a wide gap between our upper bound of 1 939 and the best known lower bound of . Closing or substantially reducing this gap is a is not memoryless, as it challenging open problem. We point out that our algorithm uses one bit of information about the previous step. Whether it is possible to reduce the ratio of 2 with a memoryless algorithm remains an open problem. Another intriguing open problem is to determine the competitiveness of the case when the jobs are similarly ordered, or when they all have the same span. We gave an algorithm for this version with competitive ratio 1 838. The lower bound of applies to similarly ordered jobs. As for the uniform span case, to the best to our knowledge, the best lower bound is 1 377 given in this paper for the 2-uniform case.

? ?

?

? ? ×

[1] N. Andelman, Y. Mansour, and A. Zhu. Competitive queueing policies in QoS switches. In ??? ? ? ? ????? ?? × ? ? ? ?? ? ?× ??? ?, pages 761–770. ACM/SIAM, 2003. [2] Y. Bartal, F. Y. L. Chin, M. Chrobak, S. P. Y. Fung, W. Jawor, R. Lavi, J. Sgall, and T. Tich?. y Online competitive algorithms for maximizing weighted throughput of unit jobs. In ??? ? ??×? ????? ?? ? ?? ? ? ×? ?× ? ????? ? ? ? ??? ??, 2004. to appear. [3] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss. An architecture for di?erentiated services. Internet RFC 2475. 1998. [4] F. Y. L. Chin and S. P. Y. Fung. Online scheduling for partial job values: Does timesharing or randomization help? ? ?? ? ? , pages 149–164, 2003. [5] B. Hajek. On the competitiveness of online scheduling of unit-length packets with hard deadlines in slotted time. In ?? ? ? ? ?? ??? ? ?? ? ? × ? ??×? ?×, pages 434–438, 2001. [6] A. Kesselman, Z. Lotker, Y. Mansour, B. Patt-Shamir, B. Schieber, and M. Sviridenko. Bu?er over?ow management in QoS switches. In ??? ? ??? ????? ? ??? ? ????? ? ???? ?, pages 520–529. ACM, 2001.

12

?

? ?? ? ? ?? ?

???? ???

×

Recall that the algorithm uses the following constants

?
where

=

??1 ?

0 27

?

=

??1

0 38

?

=

3 ? 2? 2??

0 39

? is the largest root of ?? + ?? ? 4? + 1 = 0.
( ) = min 1

We also use the following two functions

?(
where 0

) =

?? ? ?? ? + (1 ? )(? + (? ? ? )
( ) 0 for any [? =

( ))

1. Note that these functions satisfy the following properties:

? : [0

1] ? [?

?(1 ?(0

?]
) )

? for any ? for any

?]

Fix a time step ?. Let ? ? be the two jobs released at time ? ? 1 (we assume that ? ? ) and (where ) be the jobs released at time ?. Let ? ? ? ? be the old pending job. Let also be the parameter of used time ? ? 1 (initially = ?). Then chooses the job to execute as follows: ? ? If ? = ? run with = ? ( ? ), ? If ? = ? run with = ?.
? ?? ? ? ?

?? ?

???

?? ?

We use a potential function argument to show that is ?-competitive. The proof for the 2-uniform cases is based on a ??? ?? ? ?? ? ?? argument. We de?ne below a potential function Φ that maps all possible con?gurations into real numbers. (In general, a con?guration at a given step may encode all information about the computation up to this step, both for the algorithm and the adversary. Here it is su?cient only to remember the jobs issued in last two steps.) Intuitively, the potential represents ? × savings at a given step. At each time step, an online algorithm and the adversary execute a job. The proof is based on the following lemma which can be proven by a simple summation over all steps.
? ??× ×? ? ?? ?? ? ? ? ??? ? ? ?? ? ? ?? × ?? ? ?? ? ? ×? ? ? Φ ? ? × 0 ?? ??? ?? ? ??× ? ? ?? ? ? ? ? ×? ? ? ×? ? × ? ×? ×

??? ???

?? ?

??? ?? ? ?? ? ??
(2)

???

?

?

? + ?Φ ? ? ? ? ? ?? × ?? ?× ? ?

? ? ?Φ ? ?? × ??× ? ? ? ? ??? ?? ?? ? ? ? ? ? × ×? ?? ? ? × ?? ??? ? ? ? ?

? ?× ??

Each con?guration is de?ned by the parameter of used in the previous step, the jobs released in the previous step, and the pending jobs ? ? ? ? ? of the algorithm and the adversary respectively. The con?guration is thus described by a ?ve-tuple ? ? ? ? . To simplify the

???

13

notation we write Φ?? (? Φ?? (?

?

) instead of Φ( ) = ) = ) = ) =

????

). We de?ne ( ) ( )?1

? Φ?? (? ? Φ?? (? ? Φ?? (? ?

?? (1 ? ? ? ? ?(? ? 1 ? ? ? ?? ?(1 ? ?)

( )) + ? +

( )) + ?(?

?)

where = 2 ? ?? = ?(? ? 1) = ?? + 3? ? 6. Note that 0 Recall that by and we denote the jobs released at this step and that we assume that By Lemma A.1 it is su?cient to prove that Φ?? (?

.
(3)

?

) + ??

??? ?

?

? are the parameters of used in this and the next steps, and ? ? ?? ? ? are the pending where jobs of the algorithm and the adversary in this and the next steps respectively. We start by introducing several lemmas and facts that let us avoid a number of technical issues later in the proof.
? ??

???

? + Φ???? ( ? )

(1) Φ?? (? (2) Φ?? (? (3) Φ?? (?

??

? ? ?

Φ?? (? ? ) × ? ×? × ? ????? ) Φ?? (? ? ) ) Φ?? (? ? ) ) ? ? = Φ?? (? ? ) ? ?

? ???? ?? × ?? ?? ? ?

?? ? ?

??

???? (1) We have to show that

Note that the expression on the left-hand side is minimized for ? = ?, and the expression on the right-hand side is maximized for ? = ?. We may thus assume that ? = ? and reduce the inequality to 1 ? ? ? ? 1 ? ? 1 ? which holds as + 1 ? = 2? ? 2. (2) Note that Φ?? (? ? ) = ? ? ?? ? ? ?? = Φ?? (? ? ). (3) We have Φ?? (? ? ) ? ? = ? ? ?? ? ? = ??? + (? ? ? ) = (1 ? ?)? ? ? = Φ?? (? ? ) ? ? . ?
? ?? ??

?? (1 ? ? ? ?

( )) + ?

( )

?(? ? 1 ?

+

( )) + ?(?

( )?1

?)

???

?

? ? ×? ???? ? ?? + ?? ? 4? + 1 = 0? ?

????? ? ? ?? ? ? × ??
(4) (5) (6) (7)

?7? ?9?
?
= = ( )
?

7?? ? 6? ? 5
?

?

+ 14? ? 6 + 3? ? 6

0 0 0 0

?

+ 32? ? 27

For the purpose of this analysis, it is also convenient to de?ne

( Note that

?)

? + (1 ?

)(? + (? ? ? )?) = ? (

)

satis?es the following properties: (1 ?) = (0 ?)

? for any ? ? for any ?
14

(8) 0 (9)

Solutions of the following linear programs will be used to obtain bounds on certain expressions. In these programs ? denotes a constant such that ? ? ? .

??1 :
max s.t.

(1 ? ?)

? ?


??2 :

1 0 max s.t.

(1 ? ?)( + ) ? + (1 ? ?)

??3 :

1 0 max s.t.

+



? + (1 ? ?)



? + (1 ? ?)


1 0

(? ? 1 ? + (?)) = (1 ? (?) ? 1 ?) = solution: = =

solution: = =

0 1 ?

solution: = 1 = 1

0 1 ?

We are now ready to prove that (3) holds. Let step. We distinguish the following cases.

???

be the algorithm executed in the previous

Case 1: Suppose that ? was executed in the previous step. Then algorithm applies ?.

???
?

? is pending for ?? ?

and the

Case 1a: If inequalities

?

+ (1 ? ?) then Φ?? (? Φ?? (?

???? schedules ?, and we have to verify the following four
?
max

? ?

) + ?? ) + ??

?+Φ ?+Φ

( (

?
max

+ Φ ( + Φ (

?) ?) ?) ?)

Note that the ?rst and the third inequalities are equivalent by Lemma A.2. Also, the last inequality implies the second one by the same lemma. Without the loss of generality we may assume that ? = 1. After substitution, the third and the fourth inequalities reduce to (1 ? ?)? + ?? (1 ? ?)? + ??

?+

?

+ (? ? 1 ?

(1 ? ?)

(10) ) ?

?

(11)

The right-hand sides of inequality (10) is maximized for = 0 and the inequality holds trivially. After rearranging, and using the fact that 1 = ? ? ? + (1 ? ?) , inequality (11) reduces to 0 (1 ? ?) which holds. Case 1b: If inequalities

?

?

+ (1

? ?)
? ?

then

????

schedules , and we need to verify the following

Φ?? (? Φ?? (?

)+? )+?

? + Φ ( ?) + Φ ( ?) ? ? + Φ ( ?) max + Φ ( ?)
max 15

?

Note that the ?rst and the third inequalities are equivalent by Lemma A.2. Also, the last inequality implies the second one by the same lemma. We may assume that ? = 1, and the remaining inequalities reduce to (1 ? ?)? + ? (1 ? ?)? + ?

?+(

? ? ) + (1 ? ?)

(12) (13)

After using the case condition, the inequality (12) reduces to 0 ? ? and holds. The inequality (13) reduces to ? + which holds by the case condition. Case 2: Now we assume that ? was not executed in the previous step. So ? for , and the algorithm applies = ?. ? ?? , where

?? ?

???

? is now the pending job
and we need to show the

( ?) + (1 ? ( Case 2a: If ? following four inequalities Φ?? (? Φ?? (?

?)) then the algorithm executes ? + Φ ( + Φ ( ? ? + Φ ( max + Φ (
max

? ?

)+? )+?

?

( ( ( (

?)) ?)) ?)) ?))

Once again, note that the last inequality implies the second one by Lemma A.2. We assume that ? = 1, and the remaining inequalities reduce to

?? (1 ? ? ? ?) + ? + ? ?(? ? 1 ? + ?) ? ? ? 1 ? + ? ?(? ? 1 ? + ?) ? ? ? 1 ? + ?
inequality

? ? ? + ? ? + (1 ? ?)
1+

(14) (15) (16)

???? ? ? ?? ? ?? (16). We start by regrouping the terms to reduce (16) to the following

?? (1 ? ? ? ?) + ?

1 + (1 ? ?) ? ?

We now face the following problem: we wish to maximize the right-hand side of this inequality, subject to the case condition and conditions 0, . For now, the term (? ?) from the case condition is treated like a constant, say ?, where ? ? ? . It is easy to see now, that the above problem can be formulated as a linear program with variables . In fact, it is equivalent to the program 1. We conclude that it is enough to verify the inequality for = 1 (? ?) = 0, as this is the solution of 1. Further, the left-hand side of (16) is minimized for ? = 0 and ? = 1, so overall this inequality reduces to 2(? ? 1) + 1 ? which holds.

??

??

???? ? ? ?? ? ?? (14). Once again, we start by regrouping the terms to reduce (14) to

?(? ? 1 ?

+

?) ? ? ? 1 ?

?+

(1 ? ?) ? ? =1 0 (? ?)

As in the proof of (16) we notice that it is enough to verify the inequality for as this is the solution of 1. The inequality now reduces to

??

= 0,

[?? + (1 ? ? )(? + (? ? ? )?)][?? ? (? ? 1 + 16

?) + ? ? 1] + ? ? 1

Let ?(? ?) denote the expression on the left-hand side of this inequality. The function ? is a polynomial of third degree in ? . The coe?cient of ? ? is (? ? 1 + ?)(? ? ? + (? ? ? )?) 0, so to prove that the inequality holds it is enough to show that for any ? ? [0 1], ?(0 ?) 0, ?(1 ?) 0, ? and that the second derivative  ? (? ?) 0. ?? Since

?(0 ?) = [? + (? ? ? )?][ ? ? 1] + ? ? 1
0, it is su?cient to show that is quadratic in ?, ?(0 0) = 0, and the coe?cient of ?? is (? ? ? ) ??? ?? (0) ??? ?? (0) = ?(? ? ? ) + ? , and the inequality 0 to prove that ?(0 ?) 0. Indeed, ? ? ?(? ? ? ) + ? 0 reduces to 7?? ? 6? ? 5 0 which holds. ? Since, ?(1 ?) = 0, it remains to verify that the second derivative  ? (? ?) 0. Since, ??

?? (? ?) = (? ? 1 + ?)[4? (? ? ? + (? ? ? )?) ? 2(?? + (1 ? ? )(? + (? ? ? )?))] ??
it is enough to verify that

?? + (1 ? ?)(? + (? ? ? )?) ? 2?(? ? ? + (? ? ? )?)

0

Since this is a linear inequality and the coe?cient of ? is 3(? ? ? ? (? ? ? )?) 0, it is enough to verify it for ? = 1. The inequality now reduces to 3? ? 2(? + (? ? ? )?) 0, and it is su?cient to show that it holds for ? = 1 as the coe?cient of ? is ?2(? ? ? ) 0 and the inequality is linear in ?. The inequality now reduces to ?? + 3? ? 6 0 and holds.

???? ? ? ?? ? ?? (15). We start by regrouping the terms to obtain reduce (15) to

?(? ? 1 ?

+

?) ? ? ? 1 ?

(1 ? ?) + (1 ? ?) = = 1, as

Similarly to the proof of (16) we notice that it is enough to verify the inequality for this is the solution of 2. It is now enough to prove

??

(? ?)(? (? ? 2 ?

+

?) ? ? ? 1 ?) + ? ? 1

0

The coe?cient of ?? is (1 ? ? )(? ? ? ) (? ? 1) for ? = 0 1. For ? = 0 the inequality reduces to

0 so it is enough to verify that the inequality holds

(?? + ? ? ?? )(?? (2 ? ? +

)?1

?) + ? ? 1

0

(17)

This is a quadratic inequality in ? . The coe?cient of ? ? is (? ? ?)(2 ? ? + ) 0 so it is enough to verify that the derivative with respect to ? is negative for ? = 1. Let denote the expression on the left-hand side of (17). Then

? (?) = (? ? ? )(??(2 ? ? + ) ? 1 ?) ? (?? + ? (1 ? ?))(2 ? ? + )
The inequality ? (1) 0 can be reduced to 4 For ? = 1 the inequality reduces to 3?, so it holds.

(?? + (1 ? ? )? )(?? (2 ? ?) ? 17

? 1 ?) + ? ? 1

0

This again is a quadratic inequality in ? with coe?cient of ? ? equal (? ? ?)(2 ? ?) 0. So to show that it holds it is enough to verify that the derivative in ? is negative for ? = 1. The derivative of the expression on the left-hand side is (? ? ? )(?? (2 ? ?) ? and for

? 1 ?) + (?? + (1 ? ?)? )(? ? 2)
0 which holds.

? = 1 it reduces to 7?? ? 14? + 6 ? ? ?
(

Case 2b: Suppose that following inequalities:

?)

+ (1 ? (

?)) .

???

?

?? executes ?. We need to verify the

Φ?? (? Φ?? (?

) + ?? ) + ??

?
max

?+Φ ?+Φ

( (

?
max

+ Φ ( + Φ (



( ( ( (

?)) ?)) ?)) ?))

(18) (19)

Note that the last inequality implies the second one by Lemma A.2. We may assume that and the remaining inequalities reduce to

? = 1,
(20) (21) (22)

?? (1 ? ? ? ?) + ? + ? ?(? ? 1 ? ?(? ? 1 ?
+ +

1+

? ?

(1 ? ? ? (1 ? ? ? +

( (? ?))) + ( (? ?))) + ( (? ?))) +

( (? ?)) ( (? ?))

?) ? ? ? 1 ? + ? ?) ? ? ? 1 ? + ?

?+

+ (? ? 1 ? (?

( (? ?)) ? 1

?)

???? ? ? ?? ? ?? (20). It is enough to show that (1 ? ?)(? + ? ? 1) case condition 1 (? ?) so it is enough to show
(? ?)(? ? 1)(? +

( (? ?)). By the

? ? 1)

( (? ?))

We distinguish two cases. If (? ?) ? then ( (? ?)) = 1, (1 ? ? )(? ? ? + (? ? ? )?)

? ? ? and it is enough to show

? (? ? ?)(? + ? ? 1)

(? ? ? + (? ? ? )?)

This inequality is linear in ? so it is enough to verify it for ? = 0 1. Actually it is enough to verify it for ? = 0 as ? (? ? ?) ? (? ? ? ) 0. For ? = 0 the inequality reduces to ? (? ? 1) which holds. If (? ?) ? then ( (? ?)) = ( (? ?) ? ?) (? ? ?), and we need to show (? ? ?) (? ?)(1 ? ? )(? + (? ? ?) (? ?)(? +

? ? 1)

( (? ?) ? ?)

Note that (? ?) ? ? = (1 ? ? )(? ? ? + (? ? ? )?), so it is enough to show

? ? 1)

(? ? ? + (? ? ? )?)

(23)

This is a linear inequality in ? . So it is enough to verify it for ? = 0 1. Actually, it is enough to verify it for ? = 1, as the coe?cient of ? is (? ? ?)(? + ? ? 1)(? ? ? ? (? ? ? )?) 0. The inequality 18

reduces to (? ? ?)?(? + ? ? 1) ? (? ? ? + (? ? ? )?) 0. This inequality is linear in ? and the coe?cient of ? is [(? ? ?)? ? (? ? ? )] 0, so it is enough to verify it for ? = 0. The inequality reduces now to ?(? ? 1) ? 0 which holds. ???? ? ? ?? ? ?? (21). It is enough to show that (? ? 1)(? ? 2 ? +

?)

( (? ?))

We distinguish two cases. If (? ?) ? , then ( (? ?)) = 1, and (1 ? ? )(? ? ? + (? ? ? )?) to

? ? ?.

The inequality reduces

? (? ? ? )(2 + ? ? ? ?) ? (? ? ? + (? ? ? )?) 0 This is a linear inequality in ?. The coe?cient of ? is ?? (? ? ?) ? (? ? ? ) 0, so it is enough to verify the inequality for ? = 1. The inequality now reduces to ? 1, which holds. If (? ?) ? , then ( (? ?)) = ( (? ?) ? ?) (? ? ?), and the inequality reduces to (? ?)(2 + ? ? ? ?)(? ? ?) (? ? ? + (? ? ? )?) It is now enough to prove that 2 + ? ? ? ? ? + ? ? 1 for any ? ? [0 1], to show that this 2?, which holds. For inequality follows from (23). For ? = 0 the inequality reduces to 3 + ? = 1 the inequality reduces to 3 2? + , which also holds. ???? ? ? ?? ? ?? (22). We ?rst observe that the problem of maximizing the right-hand side of
(22) subject to case conditions can be formulated as the linear program 3. It is therefore enough to verify the inequality for = 1 (? ?) = 0. As in the proof of (20) we distinguish two cases. If (? ?) ? the inequality reduces to (? ?)(? (? ? 1 ? +

??

?) ? ? ? 1 ? + ?) 3 ? 2? This is a quadratic inequality in ? . The coe?cient of ? ? is (? ? 1 ? + ?)(? ? ? ? (? ? ? )?) 0 so we need to verify that it holds for ? = 0 1. For ? = 0 the inequality reduces to [? + (? ? ? )?](? ? ? 1 ? + ?) 3 ? 2?. This is a quadratic inequality in ?. For ? = 0 it reduces to ? (?1 ? + ?) 3 ? 2? which holds. For ? = 1 it reduces to ? (2 ? ?) 3 ? 2? which also holds. The coe?cient of ?? is ? (? ? ? ) 0 so the inequality holds. For ? = 1 the inequality reduces to ? 3 ? 2? which holds. If (? ?) ? the inequality reduces to (? ?)(? (? ? 1 ? + ?) ? ? ? 1 ? + ?) 1 ? 1 ? ? ( (? ?) ? ?) (? ? ?) Since the coe?cient of ? ? is (? ? 1 ? + ?)(? ? ? ? (? ? ? )?) 0 it is enough to verify the inequality for ? = 0 and ? = 1. For ? = 1 the inequality reduces to ? 1 ? 1 ? which holds. For ? = 0 the inequality reduces to [? + (? ? ? )?](? ? ? 1 ? + ?) 1 ? 1 ? ? (? ? ? + (? ? ? )?) (? ? ?) This is a quadratic inequality in ?. For ? = 0 it reduces to ? (? ? 1 ?) 1 ? 1 ? ? which holds. For ? = 1 it reduces to ? (2 ? ?) 1 ? 1 ? ? (? ? ?) (? ? ?), which in turn reduces to ?9?? + 32? ? 27 0, which holds. The coe?cient of ?? is (? ? ? )(? ) 0, so the inequality
holds. This completes the proof of inequality (3). The ?-competitiveness of Lemma A.1. 19

?? ?

follows now from


相关推荐

最新更新

猜你喜欢