ON COMPETITIVE ONLINE ALGORITHMS FOR THE DYNAMIC PRIORITY-ORDERING PROBLEM

The vertices of a directed acyclic graph (DAG) are correctly prioritiz ed if every vertex v in the graph is assigned a priority, denoted by p riority(v), such that if there is an edge in the DAG from vertex v to vertex w then priority(v) < priority(w). The dynamic priority-ordering problem is to maintain a correct prioritization of the graph as the D AG is modified. We show that the Alpern et al. algorithm for this prob lem does not have a constant competitive ratio, where the cost of the algorithm is measured in terms of the number of primitive priority-man ipulation operations. The proof shows that there exists no algorithm f or the problem that has a constant competitive ratio, as long as the a llowed primitive priority-manipulation operations satisfy a simple pro perty. The proof also shows that there exists no algorithm for the pro blem of maintaining a topological-sort ordering that has a constant co mpetitive ratio.