Approximation results for the weighted P4 partition problems

Monnot, Jérôme; Toulouse, Sophie

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

Type

Communication / Conférence

External document link

http://hal.archives-ouvertes.fr/hal-00017259/en/

Date

2005

Conference title

15th International Symposium on Fundamentals of Computation Theory (FCT '05)

Conference date

2005-08

Conference city

Lübeck

Conference country

Allemagne

Book title

Fundamentals of Computation Theory 15th International Symposium, FCT 2005, Lübeck, Gemany, August 17-20, 2005, Proceedings

Book author

Liskiewicz, Maciej; Reischuk, Rüdiger

Publisher

Springer

Series title

Lecture Notes in Computer Science

Series number

3623

Published in

Berlin

ISBN

978-3-540-28193-1

Number of pages

576

Pages

377-385

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 / Keywords

differential approximation; standard approximation; performance ratio; approximation algorithms; 3-length chain; Graph partition