Priority algorithms for the subset-sum problem

摘要

Greedy algorithms are simple, but their relative power is not well understood. The priority framework (Borodin et al. in Algorithmica 37:295-326, 2003) captures a key notion of "greediness" in the sense that it processes (in some locally optimal manner) one data item at a time, depending on and only on the current knowledge of the input. This algorithmic model provides a tool to assess the computational power and limitations of greedy algorithms, especially in terms of their approximability. In this paper, we study priority algorithm approximation ratios for the Subset-Sum Problem, focusing on the power of revocable decisions, for which the accepted data items can be later rejected to maintain the feasibility of the solution. We first provide a tight bound of alpha approximate to 0.657 for irrevocable priority algorithms. We then show that the approximation ratio of fixed order revocable priority algorithms is between beta approximate to 0.780 and gamma approximate to 0.852, and the ratio of adaptive order revocable priority algorithms is between 0.8 and delta approximate to 0.893.