Approximation results for the weighted P4 partition problems
Toulouse, Sophie; Monnot, Jérôme (2008), Approximation results for the weighted P4 partition problems, Journal of discrete Algorithms, 6, 2, p. 299-312. http://dx.doi.org/10.1016/j.jda.2007.01.006
TypeArticle accepté pour publication ou publié
Journal nameJournal of discrete Algorithms
MetadataShow full item record
Abstract (EN)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.
Subjects / KeywordsDifferential approximation; Standard approximation; Performance ratio; Approximation algorithms; P4-packing; Graph partitioning
Showing items related by title and author.