aUniversité Paris Dauphine, CNRS LAMSADE, UMR 7024, 75016 Paris, France;bUniversité Paris 13, Institut Galilée LIPN, CNRS UMR 7030, 93430 Villetaneuse, France
Abstract:
We present several new standard and differential approximation results for the P4-partition problem using the Hassin and Rubinstein algorithm Information Processing Letters 63 (1997) 63–67]. Those results concern both minimization and maximization versions of the problem. However, the main point of this paper lies in the establishment of the robustness of this algorithm, in the sense that it provides good quality solutions for a variety of versions of the problem, under both standard and differential approximation ratios.