Show simple item record

dc.contributor.authorGourvès, Laurent
dc.contributor.authorMonnot, Jérôme
dc.contributor.authorTlilane, Lydia
dc.date.accessioned2019-04-19T14:50:16Z
dc.date.available2019-04-19T14:50:16Z
dc.date.issued2018
dc.identifier.issn1382-6905
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18721
dc.language.isoenen
dc.subjectSubset sumen
dc.subjectMaximal problemsen
dc.subjectDigraph constraintsen
dc.subjectComplexityen
dc.subjectDirected acyclic graphsen
dc.subjectOriented treesen
dc.subjectPTASen
dc.subject.ddc511en
dc.titleSubset sum problems with digraph constraintsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe introduce and study optimization problems which are related to the well-known Subset Sum problem. In each new problem, a node-weighted digraph is given and one has to select a subset of vertices whose total weight does not exceed a given budget. Some additional constraints called digraph constraints and maximality need to be satisfied. The digraph constraint imposes that a node must belong to the solution if at least one of its predecessors is in the solution. An alternative of this constraint says that a node must belong to the solution if all its predecessors are in the solution. The maximality constraint ensures that no superset of a feasible solution is also feasible. The combination of these constraints provides four problems. We study their complexity and present some approximation results according to the type of input digraph, such as directed acyclic graphs and oriented trees.en
dc.relation.isversionofjnlnameJournal of Combinatorial Optimization
dc.relation.isversionofjnlvol36en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2018-10
dc.relation.isversionofjnlpages937-964en
dc.relation.isversionofdoi10.1007/s10878-018-0262-1en
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2019-03-27T18:05:39Z
hal.person.labIds989
hal.person.labIds989
hal.person.labIds989
hal.identifierhal-02104830*


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record