Randomized Lower Bounds for Online Path Coloring.

Stefano Leonardi Andrea Vitaletti

Published in: RANDOM (1998)

Keyphrases

lower bound
online algorithms
upper bound
online learning
shortest path
randomized algorithms
branch and bound algorithm
worst case
np hard
optimal solution
lower bounding
real time
greedy algorithm
lower and upper bounds
linear programming relaxation
optimal cost
objective function