On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
From MaRDI portal
Publication:4744041
DOI10.1287/moor.8.1.1zbMath0506.90035OpenAlexW2157952725WikidataQ89214295 ScholiaQ89214295MaRDI QIDQ4744041
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) Integer programming (90C10) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)
Related Items (59)
A compact labelling scheme for series-parallel graphs ⋮ The knapsack problem with special neighbor constraints ⋮ Approximation algorithms for simple assembly line balancing problems ⋮ An algorithm to generate the ideals of a partial order ⋮ Extended formulations for the cardinality constrained subtree of a tree problem ⋮ A pegging approach to the precedence-constrained knapsack problem ⋮ Subset sum problems with digraph constraints ⋮ Primal-Dual Algorithms for Precedence Constrained Covering Problems ⋮ Best location of service centers in a treelike network under budget constraints ⋮ Integer knapsack problems with set-up weights ⋮ Quantifying inductive bias: AI learning algorithms and Valiant's learning framework ⋮ Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems ⋮ Multiattribute electronic procurement using goal programming ⋮ A memetic algorithm for the cost-oriented robotic assembly line balancing problem ⋮ An efficient algorithm for a capacitated subtree of a tree problem in local access telecommunication networks ⋮ Optimizing constrained subtrees of trees ⋮ MineLib: a library of open pit mining problems ⋮ An efficient algorithm for optimal pruning of decision trees ⋮ Balancing profits and costs on trees ⋮ Primal-dual algorithms for precedence constrained covering problems ⋮ Partially ordered knapsack and applications to scheduling ⋮ The connected critical node problem ⋮ The knapsack problem with neighbour constraints ⋮ Analysis of the simple assembly line balancing problem complexity ⋮ Solution techniques for bi-level knapsack problems ⋮ Min‐sum controllable risk problems with concave risk functions of the same value range ⋮ Exact algorithms for the product configuration problem ⋮ Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items ⋮ Clique-based facets for the precedence constrained knapsack problem ⋮ Attack and defense in the layered cyber-security model and their \((1 \pm \varepsilon)\)-approximation schemes ⋮ Solutions for subset sum problems with special digraph constraints ⋮ Locating a discrete subtree of minimum variance on trees: new strategies to tackle a very hard problem ⋮ Exact approaches for solving a covering problem with capacitated subtrees ⋮ Tailored Lagrangian relaxation for the open pit block sequencing problem ⋮ The precedence constrained knapsack problem: separating maximally violated inequalities ⋮ Algorithms for the bounded set-up knapsack problem ⋮ Nonconvex piecewise linear knapsack problems ⋮ The cardinality and precedence constrained maximum value sub-hypergraph problem and its applications ⋮ Complexity of the sex-equal stable marriage problem ⋮ Sex-equal stable matchings: complexity and exact algorithms ⋮ On the complexity of assembly line balancing problems ⋮ On a class of branching problems in broadcasting and distribution ⋮ Shift-and-merge technique for the DP solution of the time-constrained backpacker problem ⋮ Polyhedral results for the precedence-constrained knapsack problem ⋮ Most balanced minimum cuts ⋮ Island partition of the distribution system with distributed generation ⋮ Locating tree-shaped facilities using the ordered median objective ⋮ A strengthened formulation and cutting planes for the open pit mine production scheduling problem ⋮ Tree knapsack approaches for local access network design ⋮ 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 ⋮ Partitioning of trees for minimizing height and cardinality ⋮ An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs ⋮ Heuristic and exact algorithms for the precedence-constrained knapsack problem ⋮ A dynamic programming algorithm for the local access telecommunication network expansion problem ⋮ Electing a committee with dominance constraints ⋮ Exact and heuristic algorithms for dynamic tree simplification ⋮ Precedence-Constrained Min Sum Set Cover ⋮ Pseudopolynomial algorithms for the solution of backpack problems
This page was built for publication: On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
