Transcript tarjan

Algorithms in the Real World:
From Application to Abstraction to Algorithm
(and Back)
Robert E. Tarjan
Princeton University
and
InterTrust Technologies
Research with Haim Kaplan and Kostas Tsioutsiouliklis
Help from Andrew Goldberg
1
Outline
Broadcast Scheduling
Scheduling Using a Kinetic Heap
[Initial Solutions]
Connections to Computational Geometry
[Additional Solutions]
A Simple Solution
(Practical?)
The Discovery/Development Process
Thoughts
2
Broadcast Scheduling
(Lecture by Mike Franklin
Server:
many
data items
research papers)
Users
Broadcast
channel
(single-item)
One server, many possible items to send.
One broadcast channel.
Users submit requests for items.
Goal: Satisfy users as well as possible, making
decisions on-line.
3
Abstractions:
All items have the same broadcast time.
Minimize the sum of waiting times?
Scheduling Policies (heuristics)
Greedy = Longest Wait first (LWF):
Send item with largest sum of waiting times.
(vs. number of requests or longest single waiting time)
R x W: Max # requests x longest waiting time
Approximations to R x W
4
5
Results of Franklin and others:
LWF schedules well “in practice” (in simulations)
but too expensive (linear-time)
This claim used to justify approximations to
R x W, still linear-time but with a smaller
(parameterized) constant.
5
Questions (for an algorithm guy or gal)
LWF does well compared to what?
_ Try a competitive analysis
Can we improve the cost of LWF?
_ What data structure?
6
Parametic Heap
A collection of items, each with an associated
key.
key (i) = ai x + bi
ai,, bi reals, x a real-valued parameter
ai = slope, bi = constant
Operations:
make an empty heap h.
insert item i with key ai x + bi into heap h.
find an item i in heap h of minimum key for x = x0.
delete item i from heap h.
7
Kinetic Heap
A parametric heap such that successive x-values
of find mins are non-decreasing.
(Think of x as time.)
xc = largest x so far (current time)
Additional operation:
decrease the key of an item i, replacing it by a key that
is no larger for all x > (next) xc
8
Broadcast Scheduling via a Kinetic Heap
Max-heap (replace find min by find max,
decrease key by increase key =
change sign of all keys)
Can implement LWF or R x W or any similar policy:
Broadcast decision is find min plus delete
Request is insert (if first) or decrease key (if not)
Only (at most) find min need be real-time, other ops
can proceed concurrently with broadcasting
Slopes are integers that count requests
9
What is known about parametric and kinetic heaps?
A key is a line _computational geometry
Equivalent problems:
maintain the lower envelope of a collection of lines
in 2 D
projective duality
maintain the convex hull of a set of points in 2D
under insertion and deletion
“kinetic” restriction = “sweep line” constraint of queries
10
(Seminal) Results
Overmars and van Leeuwen (1981)
Dynamic convex hulls and lower envelopes
in O(log n) time per query,
O(log2n) time per update, worst-case
Basch, Guibas, and Hershberger (1997)
“Kinetic” data structure paradigm
(Much other work: improvements, restrictions, etc.)
11
Our Results
Four different data structures, each one best
in a different setting.
Simple Kinetic Heap
A balanced binary tree, with items in nodes
in symmetric order by key slope.
The tree is a tournament on items by
current key.
The tree also contains swap times (times
when winning keys change) and is a
tournament on swap times.
O(1) worst-case find min,
O(log2n) amortized insert/delete
Combines seminal ideas with our own
Is it practical?
12
min key
min swap time
swap time
3.5
3
a: x + 10
d
b
2
2
b: 2x + 7
d
c: 3x +2
d:4x
xc = 0
A Simple Kinetic Heap
13
The Discovery/Development Process
Application
model
Abstraction
apply
develop
experiment
Algorithm
Old/New
Theory/Practice
14
Thoughts
Effective algorithm development and application
in the real world requires active, repeated interaction
between the application developer(s) and the
algorithm guy(s)/gal(s) – teaming.
Our training of students should include, or at least model,
this practice.
Our training should also include cross-discipline
studies – rich sources of problems for algorithm
guys/gals.
15