Priority Algorithms for Graph Optimization Problems.

Allan Borodin, Joan Boyar, and Kim S. Larsen.
In 2nd Workshop on Approximation and Online Algorithms (WAOA), volume 3351 of Lecture Notes in Computer Science, pages 126-139. Springer, 2005.

We continue the study of priority or "greedy-like" algorithms as initiated in [Borodin, Nielsen, Rackoff: (Incremental) priority algorithms, Algorithmica, 37: 295-326, 2003] and as extended to graph theoretic problems in [Davis, Impagliazzo: Models of greedy algorithms for graph problems, Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, 2004]. Graph theoretic problems pose some modelling problems that did not exist in the original applications of [BNR03] and [Angelopoulos, Borodin: On the power of priority algorithms for facility location and set cover, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, volume 2462 of Lecture Notes in Computer Science, 26-39, Springer-Verlag, 2002]. Following [DI04], we further clarify these concepts. In the graph theoretic setting there are several natural input formulations for a given problem and we show that priority algorithm bounds in general depend on the input formulation. We study a variety of graph problems in the context of arbitrary and restricted priority models corresponding to known "greedy algorithms".

---

publication

Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any): The final publication is available at link.springer.com.

full version

Link to the journal version containing all the material and proofs, some of which are usually omitted in the conference version due to space constraints.

other publications

Other publications by the author.