کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418810 | 681720 | 2009 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Approximation algorithms and hardness results for the clique packing problem Approximation algorithms and hardness results for the clique packing problem](/preview/png/418810.png)
For a fixed family FF of graphs, an FF-packing in a graph GG is a set of pairwise vertex-disjoint subgraphs of GG, each isomorphic to an element of FF. Finding an FF-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F={K2}F={K2}. In this paper we provide new approximation algorithms and hardness results for the KrKr-packing problem where Kr={K2,K3,…,Kr}Kr={K2,K3,…,Kr}.We show that already for r=3r=3 the KrKr-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed rr. For r=3,4,5r=3,4,5 we obtain better approximations. For r=3r=3 we obtain a simple 3/23/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldórsson. For r=4r=4, we obtain a (3/2+ϵ)(3/2+ϵ)-approximation, and for r=5r=5 we obtain a (25/14+ϵ)(25/14+ϵ)-approximation.
Journal: Discrete Applied Mathematics - Volume 157, Issue 7, 6 April 2009, Pages 1396–1406