This is the authors' abstract. We don't add key points for this paper.
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 on-line virtual circuit and optical routing problems. Lund and Yannakakis [The approximation of maximum subgraph problems, in Proceedings of the 20th International Colloquium on Automata, Languages and Programming, 1993, pp. 40-51] give inapproximability results for the problem of finding the largest vertex induced subgraph satisfying any nontrivial, hereditary property pi--e.g., independent set, planar, acyclic, bipartite. We consider the on-line version of this family of problems, where some graph G is fixed and some subgraph H of G is presented on-line, vertex by vertex. The on-line algorithm must choose a subset of the vertices of H, choosing or rejecting a vertex when it is presented, whose vertex induced subgraph satisfies property pi. Furthermore, we study the on-line version of graph coloring whose off-line version has also been shown to be inapproximable [C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, in Proceedings of the 25th ACM Symposium on Theory of Computing, 1993], on-line max edge-disjoint paths, and on-line path coloring problems. Irrespective of the time complexity, we show an Omega(n epsilon ) lower bound on the competitive ratio of randomized on-line algorithms for any of these problems. As a consequence, we obtain an Omega(n epsilon ) 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. Similar lower bounds are obtained for on-line optical routing as well.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Bartal et al. (2006) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: