Show simple item record

dc.contributor.authorEscoffier, Bruno
dc.contributor.authorHammer, Peter
dc.date.accessioned2010-01-26T08:24:04Z
dc.date.available2010-01-26T08:24:04Z
dc.date.issued2007
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3125
dc.description.abstractfrNous étudions dans cet article l'approximation polynomiale du problème de la couverture d'ensemble quadratique. Ce problème, qui apparaît dans de nombreuses applications, est une généralisation naturelle du problème usuel de la couverture d'ensemble. Nous montrons que ce problème est très difficile à approcher dans le cas général, et même dans des cas particuliers classiques (quand la taille des ensembles ou quand la fréquence des éléments est bornée par une constante). Nous nous focalisons ensuite sur le cas convexe et nous donnons des résultats d'approximation à la fois positifs et négatifs. Dans un dernier temps, nous étudions la version non pondérée de ce problème.
dc.language.isoenen
dc.subjectLogical Analysis of Dataen
dc.subjectApproximation Algorithmsen
dc.subjectQuadratic Set Coveringen
dc.subject.ddc005en
dc.titleApproximation of the Quadratic Set Covering Problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe study in this article the polynomial approximation properties of the Quadratic Set Covering problem. This problem, which arises in many applications, is a natural generalization of the usual Set Covering problem. We show that this problem is very hard to approximate in the general case, and even in classical subcases (when the size of each set or when the frequency of each element is bounded by a constant). Then we focus on the convex case and give both positive and negative approximation results. Finally, we tackle the unweighted version of this problem.en
dc.relation.isversionofjnlnameDiscrete Optimization
dc.relation.isversionofjnlvol4en
dc.relation.isversionofjnlissue3-4en
dc.relation.isversionofjnldate2007-12
dc.relation.isversionofjnlpages378-386en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.disopt.2007.10.001en
dc.identifier.urlsitehttp://hal.archives-ouvertes.fr/hal-00116702/en/
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record