### short

```N. Bansal1, M. Charikar2, R. Krishnaswamy2, S. Li3
1TU
Eindhoven
2Princeton
University
3TTIC

requests






1
3
5
2
4
5
1
3
4
5
3
response time = 2
1
2
4
5
response time = 3
4
3
2
Time
a server holding n pages
1 2 3 4 5
requests come over time
broadcast 1 page per time slot
all outstanding requests for the page satisfied
minimize average response time
offline version

Our Results

approximation
integrality gap
hardness
previous best
O(log2n) *
1 + tiny const #
NP-hard ~
our results
O(log3/2n)
Ω(log n)
Ω(log1/2 n)
[Bansal-Coppersmith-Sviridenko 08]
# [Bansal-Charikar-Khanna-Naor 05]
~ [Erlebach-Hall 02]
*
Discrepancy Approach

 negative results (integrality gap and hardness)
 connection to permutation discrepancy
 positive result
 Lovett-Meka algorithmic framework for discrepancy
minimization
Discrepancy Approach

 negative results (integrality gap and hardness)
 connection to permutation discrepancy
 positive result
 Lovett-Meka algorithmic framework for discrepancy
minimization
3-Permutation Discrepancy

 give 3 permutations of [n]
 find a coloring χ : [n]{±1}
 minimize the maximum discrepancy over all
prefixes of the permutations
5 6 3 1 4 2
6 3 1 4 2 5
1 5 2 3 4 6
χ: 1 2 3 4 5 6
discrepancy = 2
Why 3 Permutations?

 1 permutation : discrepancy=1, trivial
 2 permutations : discrepancy=1, easy exercise
 3 permutations?
 upper bound : O(log n)
 lower bound [Newman-Nikolov 11]: Ω(log n)
 l ≥ 3 permutations
 upper bound : O(l1/2 log n)
 lower bound : max{Ω(l1/2), Ω(log n)}
Negative Results

Main Lemma
l-permutation
instance Π
“discrepancy”
instance I
=
optimal response time
LP(I) = O(1)
 Main + Ω(log n)-disc. for 3-perm.  Ω(log n)-int. gap
 Main + Ω(l1/2)-hard. for l-perm.(new)  Ω(log1/2 n)-hard.
Fractional Schedule from LP

response time
0.4×1+0.6×2=1.6
requests
integral
schedule
fractional
schedule
1
3
5
2
4
5
3
4
5
1
2
4
Time
Main Lemma
l-permutation
instance Π
“discrepancy”
instance I
=
optimal response time
LP(I) = O(1)
 proof steps:




construction of BS instance from l permutations
Θ(1) LP value
small discrepancy  small response time
small response time  small discrepancy
Construction of BS Instance

 given 3 permutations π1 π2 π3 of size m
 π1 = (5, 8, 4, 6, 3, 2, 1, 7)
 π2 = (6, 7, 3, 8, 5, 1, 2, 4)
 π3 = (7, 1, 3, 2, 8, 5, 6, 4)
m/2
Req:
permutation interval
forbidden interval
P1
P2
P3
P4
P5
P6
5431
8627
5431
8627
6352
7814
6352
7814
7386
1254
7386
1254
π1
π2
π3
P7
P1
5431
8627
Brd: 3458
Req:




P2
P3
5431
3
8627
6 7
12766
6352
7814
8534
3

P4
P5
P6
P7
6352
7814
6721
7
7386
1254
4835
7386
1254
7216
3485
average response time ≈ # bad requests
a request in Pi is good if it is satisfied at Pi or Pi+1
Θ(1) LP Value

Req:
P1
P2
P3
P4
P5
P6
5431
8627
5431
8627
6352
7814
6352
7814
7386
1254
7386
1254
 LP solution
request
½ satisfied
P7
½ satisfied
 each time slot, broadcast ½ fraction of each page requested
 P7: broadcast ½ fraction of the m pages arbitrarily
 all requests are good:
 ½ of request in Pi is satisfied immediately
 remaining ½ satisfied at Pi+1
How to Make All Requests Good
in an Integral Schedule?

P1
5431
8627
Brd: 3421
Req:
P2
P3
P4
P5
P6
P7
5431
8627
5867
6352
7814
4312
6352
7814
6785
7386
1254
1324
7386
1254
7856
3421
 all m pages requested in all intervals(except P7)
 each P-interval has m/2 slots
 solution:
 m/2 pages are broadcast in P1, P3, P5, P7
 m/2 pages are broadcast in P2, P4, P6
 giving a balanced ±1 coloring of the m pages
How to Make All Requests Good
in an Integral Schedule?

P1
5431
8627
Brd: 3421
Req:
P2
P3
P4
P5
P6
P7
5431
8627
5867
6352
3 2
7814
14
4312
6352
7814
6785
7386
1254
1324
7386
1254
7856
3421
 enough to make all requests good?
 No! Broadcast may be before the request
 no bad requests only if two requests at the same
time have different colors
 discrepancy of 3-permutation system is 1
Requests

 suppose discχ(πi) = d





πi =(1, 10, 2, 6, 8, 7, 3, 11, 5, 12, 4, 9)
χ =(1, 10, 2, 6, 8, 7, 3, 11, 5, 12, 4, 9) d = 2
order of red elements (1,6,3,5,4,9)
right rotate by d-1=1 positions: (9,1,6,3,5,4)
broadcast according to this ordering in P2i-1
requests =
1 2 8 3 5 4
10 6 7 11 12 9
broadcasts = 9 1 6 3 5 4
Remarks

 “discrepancy” = average discrepancy of l
permutations
 size of BS instance is exponential in l
P1
P2
request
P3
good
P4
P5
P6
P7
 lengths of forbidden intervals grow exponentially
Discrepancy Approach

 negative results (integrality gap and hardness)
 connection to permutation discrepancy
 positive result
 Lovett-Meka algorithmic framework for discrepancy
minimization
Lovett-Meka Framework

 A  Rm×n, x  [0,1]n, b=Ax,
n
m
A
“error”
n
×
x
=
b
 λ1, λ2, …, λm s.t.
A
m
å
m
i=1
e
- li2
n
£
16
×
y
=
b
±λ1||A1||
±λ2||A2||
±λ3||A3||
...
±λm||Am||
 output: y  [0,1]n, s.t. ½ fraction of coordinates in
y are integral
Tentative Scheduling

 we may broadcast more than 1 page at a time slot
# broadcast between s and t ) - (t - s +1))
(
(
 backlog = max
s£t
6 time slots, 11 broadcast, backlog = 5
 tentative schedule of backlog b  valid schedule,
with additive b loss in the average response time
Goal

 assumptions:
 fractional schedule is ½-intergal
 every page is broadcast ≤ Δ = O(log n) times
  # timeslots ≤ 2Δ × n
 locally consistent distributions
with probability 1/2
with probability 1/2
Interesting Intervals

 # time slots ≤ 2Δ × n
64Δ
λ= 0
λ= 1
λ= 2
…
……

å
m
i=1
e
- li2
n i -i2 n
£å
2e £
i=0 32
16
¥
 “error”£ 2å¥i=0 i
64D
=Q
i
2
( D) = Q(
logn
)
 repeat log n times : backlog = O(log3/2n)
Summary

approximation
integrality gap
hardness
previous best
O(log2n)
1 + tiny const
NP-hard
our results
O(log3/2n)
Ω(log n)
Ω(log1/2 n)
 Open problems
 hardness for 3-permutation(implying the same hardness