Non-adaptive model asymptotic competitive ratio

This file complements the paper “Scheduling with a processing time oracle” by Dufossé, Dürr, Nadal, Trystram and Vásquez.

Algorithm chooses r>0 and 0 <= α < 1.
Adversary chooses 0 <= β <= α and 0 <= γ < 1-α.

The upper bounds are strict inequalities because the last touched job is always executed and short.

We have n jobs of length either p or p+x.
Algorithm decides to test the first α  fraction of the jobs and to execute untested the remaining 1-α  fraction.
Adversary decides to return a fraction β long jobs to the tests and γ fraction of long jobs to the executions.

Fractions of jobs
ALG
| α = #T              | 1-α = #E                |
| β = #Tx | α-β = #Tp | γ   = #Ex | 1-α-γ = #Ep | β = #delayed x |

OPT
| 1-β-γ = #Ep           | β+γ = #Ex             |


First we give the expressions of the costs of the schedules.
We only keep the n^2 dependent part, and multiply by 2 for simplicity.
Then we set the goal expression G, which is >=0 iff the ratio is at most 1+r.

ClearAll[ALG,OPT,G]
ALG=FullSimplify[(2β
+(1+p)(α-β)^2
+2(1+p)(α-β)(1-α+β)
+(p+x)γ^2
+2(p+x)γ(1-α+β-γ)
+p(1-α-γ)^2
+2p(1-α-γ)β
+(p+x)β^2)];
OPT=FullSimplify[(p(1-β-γ)^2
+2p(1-β-γ)(β+γ) 
+(p+x)(β+γ)^2)];
G=FullSimplify[(1+r)OPT-ALG]

All right. Now the algorithm fixes r and α. In response the adversary tries to minimize G by choosing appropriate β and γ. We use second order analysis for this. And break it into two cases.

Case x ≥ 2+1/p

Optimize β

β^2 has coefficient (1+rx) >0 in G, hence the extreme point of G in β is a minimum.

bsol=Solve[D[G,β]==0,β]

Set β to the extreme value. Our new goal is G2.

G2=Expand[G/.bsol[[1]]]

Optimize γ

G2 is quadratic in γ. What is the coefficient of γ^2 in G2?

FullSimplify[D[D[G2,γ],γ]]

Good, G2 is convex in γ. Hence it is minimized at the extreme value of γ.

gsol=FullSimplify[Solve[D[G2,γ]==0,γ]]

Our new goal is G3.

G3=Simplify[G2/.gsol[[1]]]

Optimize α

The goal is quadratic in α. What is the coefficient of α^2 in G3?

D[D[G3,α],α]

Good, hence the algorithm chooses extreme value for α.

asol=Simplify[Solve[D[G3,α]==0,α]]

G4=Simplify[G3/.asol[[1]]]

Optimize r

FullSimplify[D[D[G4,r],r]]

As expected, the goal is concave in r. So probably the goal has two roots.

rsol=Simplify[Solve[G4==0,r]]

These roots are real, since we can safely assume x>=1. First root is the smaller one.
We denote

Δ=Numerator[r/.rsol[[1]]][[4]][[2]][[1]]

We have Sqrt[Δ]>=x^2-px-1. Hence the first root is negative. As a consequence the algorithm chooses for r any value between 0 and the second root. Say the second one.

rstar = r/.rsol[[2]]

and the ratio is 1+rstar.
Now we need to verify the conditions on α,β,γ.

Domain check on α, β,γ

Let’s start with the simplest conditions to verify.

bstar= β/.bsol[[1]]

We have clearly β<=α.

gstar = γ/.gsol[[1]]

FullSimplify[(1-α)-gstar]

Ok, by α<1, this is positive. Hence γ<1-α as required.
But β or even γ could be negative. Meanwhile since we set all those values to their extreme points, the expressions are simpler.

bstar =FullSimplify[ β/.bsol[[1]]/.gsol[[1]]/.asol[[1]]/.rsol[[2]]]

We have b* = r* p - 1. See below.

FullSimplify[rstar p -1-bstar]

In other words condition β>=0 translates into r* >= 1/p. Now let’s verify this later condition instead.

Simplify[Solve[rstar==1/p,x]]

All right, this realized at x=2+1/p and only there. What happens for larger values of x?

Limit[rstar,x->Infinity]

Sanity check: What happens for smaller values, for example x=1?
We have simplify the expression under the condition p>0 to get something simple in Mathematica.

Simplify[rstar/.{x->1},p≥0]

What happens when x is between 2+1/p and infinity? 
Fur this purpose we analyze the slope of r* at x=2+1/p.

Simplify[Simplify[D[rstar,x]]/.{x->2+1/p},p≥ 0]

All right, hence b*>=0 is satisfied for all x>=2+1/p.
Now let’s verify γ>0.

Simplify[gstar/.asol[[1]]]

ok we verified all conditions.

Case 0 ≤ x < 2+1/p

We expect that the algorithm will never test in this case. Let’s see.
We computed best response β and γ as a function of α and r.
Then best choices of α and r in response. 
When x is too small, the best choice of α would lead in an invalid choice β.
It actually means that the adversary cannot choose β in that case and is limited to choose β=0.
With this new choice of β, the best responses in α and r need to be recomputed.
Contrary to what we wrote currently in the paper, even when the algorithm knows that all tested jobs will be short, then it still makes sense to test some jobs.

G5=G/.{β->0}

g2sol=Solve[D[G5,γ]==0,γ]

Very good choice, this is between 0 and 1-α for sure.

G6=FullSimplify[(2+r)G5/.g2sol[[1]]]

Is the goal function convex in α ?

d2a = FullSimplify[D[D[G6,α],α]]

Case x ≤ 2+r (small x)

In this case the algorithm chooses α=0.

G7=FullSimplify[G6/.{α->0}]

r2sol=Solve[G7==0,r]

The second root is positive. And is the ratio in this case.
Let’s verify that the case condition is satisfied.
When x=0 the we have clearly x <= 2+ r = 1 + sqrt(1+x/p).
Both sides of the inequality are continuous and increasing in x. For which value of x do we have equality?

Solve[x==1+Sqrt[1+x/p],x]

Good by case assumption this value is not reached by x. Hence condition is satisfied.

Case 2+r < x

But from the previous case assumption (one level above) we have 2+r < x < 2+1/p.

a2sol=Solve[D[G6,α]==0,α]

This means that the algorithm tests all jobs which happen to be all short. The ratio is then simply (1+p)/p=1+1/p. But then 2+r = 3+1/p which exceeds the case assumption of x < 2+1/p. So this case is void, and the analysis complete.

When 0<=x < 2+1/p then the ratio is
 Sqrt[1+x/p]
 and when x>=2+1/p the ratio is
 -((1+p x-(x^2)+(Sqrt[8 p (-1+x) (x^2)+(((1+p x-(x^2)))^2)]))/(2 p (x^2)))