- 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
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".
- 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.
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 by the author.