Approximation results for the weighted P4 partition problems
Monnot, Jérôme; Toulouse, Sophie (2005), Approximation results for the weighted P4 partition problems, in Liskiewicz, Maciej; Reischuk, Rüdiger, Fundamentals of Computation Theory 15th International Symposium, FCT 2005, Lübeck, Gemany, August 17-20, 2005, Proceedings, Springer : Berlin, p. 377-385. http://dx.doi.org/10.1007/11537311_34
TypeCommunication / Conférence
External document linkhttp://hal.archives-ouvertes.fr/hal-00017259/en/
Conference title15th International Symposium on Fundamentals of Computation Theory (FCT '05)
Book titleFundamentals of Computation Theory 15th International Symposium, FCT 2005, Lübeck, Gemany, August 17-20, 2005, Proceedings
Book authorLiskiewicz, Maciej; Reischuk, Rüdiger
Series titleLecture Notes in Computer Science
Number of pages576
MetadataShow full item record
Abstract (EN)We present several new standard and differential approximation results for P4-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.
Subjects / Keywordsdifferential approximation; standard approximation; performance ratio; approximation algorithms; 3-length chain; Graph partition
Showing items related by title and author.