Subset sum problems with digraph constraints
From MaRDI portal
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 belongs to the solution, then the latter comprises all its outgoing nodes (node 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.
Recommendations
- Subset sum problems with special digraph constraints
- Solutions for subset sum problems with special digraph constraints
- A Structural Approach to Subset-Sum Problems
- Structural approach to subset sum problems
- A finer reduction of constraint problems to digraphs
- Subset-sum problems with different summands: Computation
- scientific article; zbMATH DE number 841593
- On the maximum acyclic subgraph problem under disjunctive constraints
Cites work
- scientific article; zbMATH DE number 3523580 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 2107164 (Why is no real title available?)
- A Depth-First Dynamic Programming Algorithm for the Tree Knapsack Problem
- Algorithms and Data Structures
- Approximating the minimum maximal independence number
- Approximation hardness of dominating set problems in bounded degree graphs
- Clique-based facets for the precedence constrained knapsack problem
- Composing equipotent teams.
- Computing and Combinatorics
- Fast algorithms for finding Hamiltonian paths and cycles in in-tournament digraphs
- Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping
- Motion planning with pulley, rope, and baskets
- On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
- On lazy bureaucrat scheduling with common deadlines
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- On the complexity of variations of equal sum subsets
- On the equal-subset-sum problem
- Partially ordered knapsack and applications to scheduling
- Some APX-completeness results for cubic graphs
- The Lazy Matroid Problem
- The knapsack problem with neighbour constraints
- The lazy bureaucrat problem with common arrivals and deadlines: approximation and mechanism design
- The lazy bureaucrat scheduling problem
- The shifting algorithm technique for the partitioning of trees
- Vote trading and subset sums
Cited in
(8)- Envy-free allocations respecting social networks
- Approximation schemes for subset-sums ratio problems
- Subset sum problems with special digraph constraints
- The knapsack problem with special neighbor constraints on directed co-graphs
- Solutions for subset sum problems with special digraph constraints
- Knapsack problems -- an overview of recent advances. I: Single knapsack problems
- Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items
- The knapsack problem with special neighbor constraints
This page was built for publication: Subset sum problems with digraph constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1631654)
