Linear time algorithms for some separable quadratic programming problems

DOI10.1016/0167-6377(93)90041-EzbMATH Open0793.90049OpenAlexW1997012643MaRDI QIDQ688207FDOQ688207

Authors: Nimrod Megiddo, Arie Tamir 

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

Recommendations

• Separable Quadratic Programming via a Primal-Dual Interior Point Method and its Use in a Sequential Procedure
• Linear Programming in Linear Time When the Dimension Is Fixed
• An infeasible-interior-point algorithm for separable convex quadratic programming
• Fast algorithm for the quadratic knapsack problem
• Separable standard quadratic optimization problems

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)

Cites Work

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

Cited In (26)

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

This page was built for publication: Linear time algorithms for some separable quadratic programming problems

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