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