Linear time algorithms for some separable quadratic programming problems

DOI10.1016/0167-6377(93)90041-EzbMath0793.90049OpenAlexW1997012643MaRDI QIDQ688207

Arie Tamir, Nimrod Megiddo

Publication date: 28 November 1993

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

Full work available at URL: https://doi.org/10.1016/0167-6377(93)90041-e

zbMATH Keywords

separable convex quadratic transportationseparable quadratic programming

Mathematics Subject Classification ID

Quadratic programming (90C20) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items

Algorithms for the continuous nonlinear resource allocation problem -- new implementations and numerical studies, Optimal iterative QP and QPQC algorithms, Quadratic resource allocation with generalized upper bounds, On a Reduction for a Class of Resource Allocation Problems, Minimizing the number of tardy jobs in two-machine settings with common due date, Staying safe and visible via message sharing in online social networks, On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems, A survey on the continuous nonlinear resource allocation problem, Breakpoint searching algorithms for the continuous quadratic knapsack problem, Order acceptance and scheduling with consideration of service level, Complexity and algorithms for nonlinear optimization problems, Hybrid rounding techniques for knapsack problems, The inverse Fermat-Weber problem, A game-theoretic approach for downgrading the 1-median in the plane with Manhattan metric, A faster polynomial algorithm for the unbalanced Hitchcock transportation problem, A faster FPTAS for knapsack problem with cardinality constraint, Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization, Approximation algorithms for knapsack problems with cardinality constraints, Variable fixing method by weighted average for the continuous quadratic knapsack problem, Minimizing the sum of the \(k\) largest functions in linear time., A faster FPTAS for knapsack problem with cardinality constraint, An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• An O(n) algorithm for quadratic knapsack problems
• Linear programming in \(O(n\times 3^{d^2})\) time
• An O(n) algorithm for the multiple-choice knapsack linear program
• Linear Programming in Linear Time When the Dimension Is Fixed
• On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem