|
| | | | |
| | | |
| Stat |
Members: 3669
Articles: 2'599'751
Articles rated: 2609
18 March 2025 |
|
| | | | |
|
Article overview
| |
|
|
Subset Sum Problems With Digraph Constraints | | Laurent Gourvès
; Jérôme Monnot
; Lydia Tlilane
; | | Date: |
5 Sep 2016 | | Abstract: | We introduce and study four optimization problems that generalize the
well-known subset sum problem. Given a node-weighted digraph, select a subset
of vertices whose total weight does not exceed a given budget. Some additional
constraints need to be satisfied. The (weak resp.) digraph constraint imposes
that if (all incoming nodes of resp.) a node $x$ belongs to the solution, then
the latter comprises all its outgoing nodes (node $x$ itself resp.). The
maximality constraint ensures that a solution cannot be extended without
violating the budget or the (weak) digraph constraint. We study the complexity
of these problems and we present some approximation results according to the
type of digraph given in input, e.g. directed acyclic graphs and oriented
trees.
Key words. Subset Sum, Maximal problems, digraph constraints, complexity,
directed acyclic graphs, oriented trees, PTAS. | | Source: | arXiv, 1609.1078 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER