Afficher la notice abrégée

dc.contributor.authorPaschos, Vangelis
dc.contributor.authorDella Croce, Federico
dc.date.accessioned2010-01-09T15:11:38Z
dc.date.available2010-01-09T15:11:38Z
dc.date.issued2008
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2850
dc.language.isoenen
dc.subjectWorst-case Complexityen
dc.subjectDominance Conditionsen
dc.subjectSet Coveringen
dc.subjectMax Cuten
dc.subject.ddc003en
dc.titleExploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problemsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn the design of branch-and-bound methods for NP-hard combinatorial optimization problems, dominance conditions have always been applied. In this work we show how the use of dominance conditions within search tree algorithms can lead to non trivial worst-case upper time bounds for the considered algorithms on bounded combinatorial optimization problems. We consider here the MIN 3-SET COVERING and the max cut problem with maximum degree three. Combining dominance conditions and intuitive combinatorial arguments, we derive two exact algorithms with worst-case complexity bounded above by O * (1.4492 n ) and O * (1.2920 n ) for the former and the latter problem, respectively, where notation O * (·) takes into account only exponential factors, and n is the number of subsets for MIN 3-SET COVERING and the number of vertices of the input-graph for max cut.en
dc.relation.isversionofjnlnameOperational Research
dc.relation.isversionofjnlvol8en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2008-11
dc.relation.isversionofjnlpages235-256en
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/s12351-008-0020-8en
dc.identifier.urlsitehttp://hal.archives-ouvertes.fr/hal-00116639/en/
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelRecherche opérationnelleen


Fichiers attachés à cette notice

FichiersTailleFormatConsulter

Il n'y a pas de fichiers associés à cette notice.

Ce document fait partie de la (des) collection(s) suivante(s)

Afficher la notice abrégée