Show simple item record

On the MAX MIN VERTEX COVER problem

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBoria, Nicolas
HAL ID: 21013
ORCID: 0000-0002-0548-4257		*
hal.structure.identifier
dc.contributor.authorDella Croce, Federico*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorPaschos, Vangelis*
dc.date.accessioned2013-11-18T09:38:42Z
dc.date.available2013-11-18T09:38:42Z
dc.date.issued2014
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/12087
dc.language.isoenen
dc.subjectAlgorithme et structure de données
dc.subjectComplexité
dc.subjectMathématique discrète
dc.subject.ddc003en
dc.titleOn the MAX MIN VERTEX COVER problem
dc.typeCommunication / Conférence
dc.contributor.editoruniversityotherDepartment of Computer Engineering (DAUIN),Politecnico di Torino;Italie
dc.description.abstractenWe address the max min vertex cover problem, which is the maximization version of the well studied MIN INDEPENDENT DOMINATING SET problem, known to be NP-hard and highly inapproximable in polynomial time. We present tight approximation results for this problem on general graphs, namely a polynomial approximation algorithm which guarantees an $n^{−1/2}$ approximation ratio, while showing that unless P = NP, the problem is inapproximable within ratio $n^{ε-(1/2)}$ for any strictly positive. We also analyze the problem on various restricted classes of graph, on which we show polynomiality or constant-approximability of the problem. Finally, we show that the problem is fixed-parameter tractable with respect to the size of an optimal solution, to tree-width and to the size of a maximum matching.
dc.identifier.citationpages37-48
dc.relation.ispartoftitleApproximation and Online Algorithms11th International Workshop, WAOA 2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected Papers
dc.relation.ispartofeditorPruhs, Kirk
dc.relation.ispartofpublnameSpringer
dc.relation.ispartofpublcityBerlin Heidelberg
dc.relation.ispartofdate2014
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-319-08000-0
dc.relation.conftitle11th International Workshop on Approximation and Online Algorithms, WAOA 2013
dc.relation.confdate2013-09
dc.relation.confcitySophia Antipolis
dc.relation.confcountryFrance
dc.description.submittednonen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-02-21T08:22:27Z
hal.identifierhal-01511865*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


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