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
Type
Communication / ConférenceExternal document link
http://hal.archives-ouvertes.fr/hal-00017259/en/Date
2005Conference title
15th International Symposium on Fundamentals of Computation Theory (FCT '05)Conference date
2005-08Conference city
LübeckConference country
AllemagneBook title
Fundamentals of Computation Theory 15th International Symposium, FCT 2005, Lübeck, Gemany, August 17-20, 2005, ProceedingsBook author
Liskiewicz, Maciej; Reischuk, RüdigerPublisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
3623Published in
Berlin
ISBN
978-3-540-28193-1
Number of pages
576Pages
377-385
Publication identifier
Metadata
Show full item recordAbstract (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 partitionRelated items
Showing items related by title and author.
-
Toulouse, Sophie; Monnot, Jérôme (2008) Article accepté pour publication ou publié
-
Toulouse, Sophie; Paschos, Vangelis; Monnot, Jérôme (2003) Article accepté pour publication ou publié
-
Monnot, Jérôme; Paschos, Vangelis; Toulouse, Sophie (2001) Communication / Conférence
-
Toulouse, Sophie; Monnot, Jérôme (2007) Chapitre d'ouvrage
-
Paschos, Vangelis; Monnot, Jérôme; Toulouse, Sophie (2003) Article accepté pour publication ou publié