Subset sum problems with digraph constraints

DOI10.1007/s10878-018-0262-1zbMath1414.90345arXiv1609.01078OpenAlexW2963673213MaRDI QIDQ1631654

Jérôme Monnot, Lydia Tlilane, Laurent Gourvès

Publication date: 6 December 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1609.01078

zbMATH Keywords

complexityoriented treesPTASdirected acyclic graphssubset sumdigraph constraintsmaximal problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (6)

The knapsack problem with special neighbor constraints ⋮ Envy-free allocations respecting social networks ⋮ Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Approximation schemes for subset-sums ratio problems ⋮ Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items ⋮ Solutions for subset sum problems with special digraph constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Motion planning with pulley, rope, and baskets
• Clique-based facets for the precedence constrained knapsack problem
• Approximating the minimum maximal independence number
• Partially ordered knapsack and applications to scheduling
• Approximation hardness of dominating set problems in bounded degree graphs
• On the equal-subset-sum problem
• Fast algorithms for finding Hamiltonian paths and cycles in in-tournament digraphs
• On the algorithmic complexity of twelve covering and independence parameters of graphs
• The lazy bureaucrat scheduling problem
• Some APX-completeness results for cubic graphs
• Vote trading and subset sums
• The shifting algorithm technique for the partitioning of trees
• The knapsack problem with neighbour constraints
• On lazy bureaucrat scheduling with common deadlines
• The Lazy Bureaucrat Problem with Common Arrivals and Deadlines: Approximation and Mechanism Design
• The Lazy Matroid Problem
• Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping
• A Depth-First Dynamic Programming Algorithm for the Tree Knapsack Problem
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• Computing and Combinatorics
• Algorithms and Data Structures
• Fundamentals of Computation Theory

This page was built for publication: Subset sum problems with digraph constraints