| Abstract: | We apply and extend the priority algorithm framework introduced by Borodin, Nielsen, andRackoff to define  greedy-like algorithms for the (uncapacitated) facility location problems and set cover problems. These problemshave been the focus of extensive research from the point of view ofapproximation algorithms and for both problems greedy-like algorithmshave been proposed and analyzed. The priority algorithm definitions are general enough to capture a broad class of algorithms that can be characterized as greedy-like while still possible to derive non-triviallower bounds on the approximability of the problemsby algorithms in such a class. Our results are orthogonal to complexity considerations, and hence apply to algorithms that are not necessarily polynomial time. |
