A polynomial algorithm for an integer quadratic non-separable transportation problem

DOI10.1007/BF01581207zbMath0761.90061MaRDI QIDQ1198737

Dorit S. Hochbaum, Ron Shamir, J. George Shanthikumar

Publication date: 16 January 1993

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

zbMATH Keywords

single machinequadratic objective functionpolynomial algorithmtotal weighted tardinesslarge sets of identical jobstransportation constraints

Mathematics Subject Classification ID

Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20) Deterministic scheduling theory in operations research (90B35) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (12)

Quadratic M-convex and L-convex functions ⋮ A unified approach to polynomially solvable cases of integer ``non-separable quadratic optimization ⋮ Separable relaxation for nonconvex quadratic integer programming: Integer diagonalization approach ⋮ A polynomial case of convex integer quadratic programming problems with box integer constraints ⋮ Using quadratic programming to solve high multiplicity scheduling problems on parallel machines ⋮ Complexity and algorithms for nonlinear optimization problems ⋮ On polynomial solvability of the high multiplicity total weighted tardiness problem ⋮ Multiplicity and complexity issues in contemporary production scheduling ⋮ A binary integer program to maximize the agreement between partitions ⋮ Exact and approximate algorithms for high-multiplicity parallel machine scheduling ⋮ Discrete convex analysis ⋮ A framework for the complexity of high-multiplicity scheduling problems

Cites Work

• Unnamed Item
• Unnamed Item
• Strongly polynomial algorithm for a class of combinatorial LCPs
• Bin packing can be solved within 1+epsilon in linear time
• A Polynomial-Time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and Its Power Series Extension
• The Traveling Salesman Problem with Many Visits to Few Cities
• Solving integer minimum cost flows with separable convex cost objective polynomially
• A Dynamic Programming Approach for Sequencing Groups of Identical Jobs
• Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem
• Convex separable optimization is not much harder than linear optimization

This page was built for publication: A polynomial algorithm for an integer quadratic non-separable transportation problem