Show simple item record

dc.contributor.authorAusiello, Giorgio
dc.contributor.authorBoria, Nicolas
dc.contributor.authorGiannakos, Aristotelis
dc.contributor.authorLucarelli, Giorgio
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2012-07-17T12:29:10Z
dc.date.available2012-07-17T12:29:10Z
dc.date.issued2012
dc.identifier.issn0166-218X
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/9759
dc.language.isoenen
dc.subjectGraphs
dc.subjectMaximum k coverage
dc.subjectCompetitive ratio
dc.subjectNegative results
dc.subject.ddc511en
dc.titleOnline maximum k-coverage
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherInstitut Universitaire de France;France
dc.contributor.editoruniversityotherDipartimento di Informatica e Sistemistica, Università degli Studi di Roma “La Sapienza”;Italie
dc.description.abstractenWe study an online model for the maximumView the MathML source-vertex-coverage problem, in which, given a graph G=(V,E) and an integer View the MathML source, we seek a subset A⊆V such that View the MathML source and the number of edges covered by A is maximized. In our model, at each step i, a new vertex vi is released, and we have to decide whether we will keep it or discard it. At any time of the process, only View the MathML source vertices can be kept in memory; if at some point the current solution already contains View the MathML source vertices, any inclusion of a new vertex in the solution must entail the definite deletion of another vertex of the current solution (a vertex not kept when released is definitely deleted). We propose algorithms for several natural classes of graphs (mainly regular and bipartite), improving on an easy View the MathML source-competitive ratio. We next settle a set version of the problem, called the maximumView the MathML source-(set)-coverage problem. For this problem, we present an algorithm that improves upon former results for the same model for small and moderate values of View the MathML source.
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol160
dc.relation.isversionofjnlissue13-14
dc.relation.isversionofjnldate2012
dc.relation.isversionofjnlpages1901-1913
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.dam.2012.04.005
dc.identifier.urlsitehttps://hal.archives-ouvertes.fr/hal-00876975
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-02-21T08:20:52Z


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