Lower bounds for on-line graph problems with application to on-line circuit and optical routing
Yair Bartal, Amos Fiat, Stefano Leonardi · 1996
We present lower bounds on the competitive ratio of randomized algorithms for a wide class of on-line graph optimization problems and we apply such results to online virtual circuit and optical routing problems.Lund and Yannakakis [LY93a] give inapproximability results for the problem of finding the largest vertex induced subgraph satisfying any non-trivial, hereditary, property r.E.g., independent set, planar, acyclic, bipartite, etc.We consider the on-line version of this family of problems, where some graph G is fixed and some subgraph H is presented on-line, vertex by vertex.The on-line algorithm must choose a subset of the vertices of i7, choosing or rejecting a vertex when it is presented, whose vertex induced subgraph satisfies property m.Furthermore, we study the on-line version line algorithms for any of these problems.As a consequence, we obtain an fl(n') lower bound on the competitive ratio of randomized on-line algorithms for virtual circuit routing on general networks, in contrast to the known results for some specific networks.Moreover, this lower bound holds even if the use of preemption is allowed.Similar lower bounds are obtained for on-line optical routing as well,