On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
DOI10.1287/MOOR.8.1.1zbMATH Open0506.90035OpenAlexW2157952725WikidataQ89214295 ScholiaQ89214295MaRDI QIDQ4744041FDOQ4744041
Authors: K. A. Niemi, D. S. Johnson 
Publication date: 1983
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: http://digital.library.wisc.edu/1793/58238
acyclic directed graphcomplexity resultsdynamic programming techniquesNP- completenessfully polynomial time approximation schemesout-treemaximum- valued subset of verticespartially ordered knapsack problempseudopolynomial time optimization algorithmsweighted and valued graph
Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Integer programming (90C10)
Cited In (59)
- Electing a committee with dominance constraints
- Primal-dual algorithms for precedence constrained covering problems
- Attack and defense in the layered cyber-security model and their \((1 \pm \varepsilon)\)-approximation schemes
- Polyhedral results for the precedence-constrained knapsack problem
- Complexity of the sex-equal stable marriage problem
- Locating a discrete subtree of minimum variance on trees: new strategies to tackle a very hard problem
- Algorithms for the bounded set-up knapsack problem
- Heuristic and exact algorithms for the precedence-constrained knapsack problem
- Most balanced minimum cuts
- Locating tree-shaped facilities using the ordered median objective
- Island partition of the distribution system with distributed generation
- An algorithm to generate the ideals of a partial order
- Integer knapsack problems with set-up weights
- A memetic algorithm for the cost-oriented robotic assembly line balancing problem
- Exact and heuristic algorithms for dynamic tree simplification
- Approximation algorithms for simple assembly line balancing problems
- Subset sum problems with digraph constraints
- On the complexity of project scheduling to minimize exposed time
- Fully polynomial approximation schemes for locating a tree-shaped facility: A generalization of the knapsack problem
- A dynamic programming algorithm for the local access telecommunication network expansion problem
- Clique-based facets for the precedence constrained knapsack problem
- Best location of service centers in a treelike network under budget constraints
- On a class of branching problems in broadcasting and distribution
- Shift-and-merge technique for the DP solution of the time-constrained backpacker problem
- Optimizing constrained subtrees of trees
- Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems
- Solutions for subset sum problems with special digraph constraints
- Tree knapsack approaches for local access network design
- A pegging approach to the precedence-constrained knapsack problem
- Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items
- Tailored Lagrangian relaxation for the open pit block sequencing problem
- Multiattribute electronic procurement using goal programming
- Partitioning of trees for minimizing height and cardinality
- MineLib: a library of open pit mining problems
- Balancing profits and costs on trees
- Pseudopolynomial algorithms for the solution of backpack problems
- Nonconvex piecewise linear knapsack problems
- The knapsack problem with neighbour constraints
- The knapsack problem with special neighbor constraints
- An efficient algorithm for optimal pruning of decision trees
- The precedence constrained knapsack problem: separating maximally violated inequalities
- Partially ordered knapsack and applications to scheduling
- A strengthened formulation and cutting planes for the open pit mine production scheduling problem
- Extended formulations for the cardinality constrained subtree of a tree problem
- An efficient algorithm for a capacitated subtree of a tree problem in local access telecommunication networks
- Solution techniques for bi-level knapsack problems
- Exact approaches for solving a covering problem with capacitated subtrees
- On the complexity of assembly line balancing problems
- An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
- A compact labelling scheme for series-parallel graphs
- The cardinality and precedence constrained maximum value sub-hypergraph problem and its applications
- Sex-equal stable matchings: complexity and exact algorithms
- Quantifying inductive bias: AI learning algorithms and Valiant's learning framework
- Precedence-Constrained Min Sum Set Cover
- Primal-dual algorithms for precedence constrained covering problems
- Min‐sum controllable risk problems with concave risk functions of the same value range
- Analysis of the simple assembly line balancing problem complexity
- Exact algorithms for the product configuration problem
- The connected critical node problem
This page was built for publication: On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4744041)
