A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks

DOI10.1007/BF01581240zbMath0795.90021MaRDI QIDQ2366611

Arie Tamir

Publication date: 30 August 1993

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

strongly polynomial algorithmtwo-terminal series-parallel graphsconvex separable quadratic cost function

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20) Deterministic network models in operations research (90B10) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications, A note on algebraic expressions of rhomboidal labeled graphs, On lengths of edge-labeled graph expressions, On a Reduction for a Class of Resource Allocation Problems, Scaling, proximity, and optimization of integrally convex functions, On algebraic expressions of directed grid graphs, The symmetric quadratic knapsack problem: approximation and scheduling applications, Single machine scheduling with a generalized job-dependent cumulative effect, Using quadratic programming to solve high multiplicity scheduling problems on parallel machines, MINIMIZING TOTAL WEIGHTED EARLINESS-TARDINESS ON A SINGLE MACHINE AROUND A SMALL COMMON DUE DATE: AN FPTAS USING QUADRATIC KNAPSACK, Complexity and algorithms for nonlinear optimization problems, A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives, Avoiding bad steps in Frank-Wolfe variants, Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product, Decomposition methods for generating algebraic expressions of full square rhomboids and other graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algebraic optimization: The Fermat-Weber location problem
• Some proximity and sensitivity results in quadratic integer programming
• A polynomial algorithm for minimum quadratic cost flow problems
• Towards a strongly polynomial algorithm for strictly convex quadratic programs: An extension of Tardos' algorithm
• Minimum cost flow algorithms for series-parallel networks
• A strongly polynomial minimum cost circulation algorithm
• Strongly polynomial algorithm for a class of combinatorial LCPs
• Lower Bounds for Computations with the Floor Operation
• Solving integer minimum cost flows with separable convex cost objective polynomially
• The Recognition of Series Parallel Digraphs
• Obnoxious Facility Location on Graphs
• Technical Note—Allocation of Effort Resources among Competing Activities
• A bad network problem for the simplex method and other minimum cost flow algorithms
• Convex separable optimization is not much harder than linear optimization