An O(n) algorithm for quadratic knapsack problems

DOI10.1016/0167-6377(84)90010-5zbMATH Open0544.90086OpenAlexW1978119584MaRDI QIDQ797501FDOQ797501

Authors: Peter Brucker 

Publication date: 1984

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(84)90010-5

Recommendations

• On the continuous quadratic knapsack problem
• Algorithms for the solution of quadratic knapsack problems
• Fast algorithm for the quadratic knapsack problem
• Efficient Methods For Solving Quadratic 0–1 Knapsack Problems
• Linear programming for the \(0-1\) quadratic knapsack problem

zbMATH Keywords

knapsack problemparametric approachbounded quadratic optimization

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Quadratic programming (90C20) Convex programming (90C25) Analysis of algorithms and problem complexity (68Q25) Nonlinear programming (90C30)

Cites Work

• Title not available (Why is that?)
• A polynomially bounded algorithm for a singly constrained quadratic program

Cited In (80)

• Complexity and algorithms for nonlinear optimization problems
• On a discrete nonlinear and nonseparable knapsack problem
• Variable fixing method by weighted average for the continuous quadratic knapsack problem
• Simple solution methods for separable mixed linear and quadratic knapsack problem
• Minimization of a strictly convex separable function subject to convex separable inequality constraint and box constraints
• A note on optimal solutions to quadratic knapsack problems
• Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization
• A Closed-Form Solution To A Class Of Quadratic Knapsack Problems
• A penalty algorithm for solving convex separable knapsack problems
• A coordinate gradient descent method for linearly constrained smooth optimization and support vector machines training
• Linear programming with variable matrix entries
• A decomposition algorithm for nested resource allocation problems
• Approximation algorithms for indefinite quadratic programming
• Algorithms for bound constrained quadratic programming problems
• A Branch and Bound Algorithm for Integer Quadratic Knapsack Problems
• Conditional subgradient optimization -- theory and applications
• A two-phase method for solving continuous rank-one quadratic knapsack problems
• A nonlinear knapsack problem
• Algorithms for the continuous nonlinear resource allocation problem -- new implementations and numerical studies
• The symmetric quadratic knapsack problem: approximation and scheduling applications
• Quadratic bottleneck knapsack problems
• A dual method for minimizing a nonsmooth objective over one smooth inequality constraint
• On the solution of multidimensional convex separable continuous knapsack problem with bounded variables
• Level-set methods for convex optimization
• Inverse optimization for linearly constrained convex separable programming problems
• Issues in the implementation of the DSD algorithm for the traffic assignment problem
• A Newton's method for the continuous quadratic knapsack problem
• On the solution of concave knapsack problems
• A class of nonlinear nonseparable continuous Knapsack and multiple-choice knapsack problems
• An algorithm for a singly constrained class of quadratic programs subject upper and lower bounds
• Variable fixing algorithms for the continuous quadratic Knapsack problem
• Linear time algorithms for some separable quadratic programming problems
• A breakpoint search approach for convex resource allocation problems with bounded variables
• Efficient nonconvex sparse group feature selection via continuous and discrete optimization
• Algorithms for the solution of quadratic knapsack problems
• A pegging algorithm for the nonlinear resource allocation problem
• Local minima for indefinite quadratic knapsack problems
• A Benders decomposition based heuristic for the hierarchical production planning problem
• A fast algorithm for solving a simple search problem
• A sequential method for a class of box constrained quadratic programming problems
• An Efficient Hybrid Algorithm for the Separable Convex Quadratic Knapsack Problem
• A survey on the continuous nonlinear resource allocation problem
• On the continuous quadratic knapsack problem
• Solving the unit commitment problem by a unit decommitment method
• The nonlinear knapsack problem - algorithms and applications
• Quadratic resource allocation with generalized upper bounds
• An \(O(n)\) algorithm for projecting a vector on the intersection of a hyperplane and a box in \(\mathbb R^n\)
• An \(O(n^ 2)\) active set method for solving a certain parametric quadratic program
• Evasive path planning under surveillance uncertainty
• A conjugate gradient method for the unconstrained minimization of strictly convex quadratic splines
• The quadratic knapsack problem -- a survey
• Solving the continuous nonlinear resource allocation problem with an interior point method
• Alternating direction method of multipliers for sparse principal component analysis
• Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
• Maximum likelihood estimation of cell probabilities in constrained multinomial models
• The quadratic 0-1 knapsack problem with series-parallel support
• Breakpoint searching algorithms for the continuous quadratic knapsack problem
• New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds
• Fast algorithm for singly linearly constrained quadratic programs with box-like constraints
• On linear-time algorithms for the continuous quadratic Knapsack problem
• Convergent Lagrangian heuristics for nonlinear minimum cost network flows
• Decision model and analysis for investment interest expense deduction and allocation
• On a Reduction for a Class of Resource Allocation Problems
• Using quadratic programming to solve high multiplicity scheduling problems on parallel machines
• Finding the projection onto the intersection of a closed half-space and a variable box
• IMPROVED PROJECTED GRADIENT ALGORITHMS FOR SINGLY LINEARLY CONSTRAINED QUADRATIC PROGRAMS SUBJECT TO LOWER AND UPPER BOUNDS
• A New Combinatorial Algorithm for Separable Convex Resource Allocation with Nested Bound Constraints
• Sparse regularization via bidualization
• Title not available (Why is that?)
• Computing Ground States of Bose--Einstein Condensates with Higher Order Interaction via a Regularized Density Function Formulation
• A fast algorithm for quadratic resource allocation problems with nested constraints
• Complexity Estimation for an Algorithm of Searching for Zero of a Piecewise Linear Convex Function
• A Bregman–Kaczmarz method for nonlinear systems of equations
• Comparative study of two fast algorithms for projecting a point to the standard simplex
• Using Nemirovski's Mirror-Prox method as basic procedure in Chubanov's method for solving homogeneous feasibility problems
• Total Variation Regularization Strategies in Full-Waveform Inversion
• Minimum variance allocation among constrained intervals
• Efficient projection onto the intersection of a half-space and a box-like set and its generalized Jacobian
• Computational aspects of the inverse single facility location problem on trees under \(l_k\)-norm
• Estimating networks with jumps

This page was built for publication: An O(n) algorithm for quadratic knapsack problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q797501)