Approximation Results for the Weighted P4 Partition Problems

摘要

We present several new standard and differential approximation results for P_4-partition problem by using the algorithm proposed in Hassin and Rubinstein (Information Processing Letters, 63: 63-67, 1997), for both minimization and maximization versions of the problem. However, the main point of this paper is the robustness of this algorithm, since it provides good solutions, whatever version of the problem we deal with, whatever the approximation framework within which we estimate its approximate solutions.