On the Complexity of the Production-Transportation Problem

DOI10.1137/0806014MaRDI QIDQ4877515zbMATH OpenOpenAlexFDO

Authors Dorit S. Hochbaum, Sung-Pil Hong

Publication date 13 May 1996

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/d57943fb74a569242c8c6fb4979eecece2aae2aa

zbMATH Keywords

Monge sequencepolynomial algorithmproduction-transportation problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Production models (90B30) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Nonconvex programming, global optimization (90C26) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables
• Strongly polynomial algorithm for a production-transportation problem with concave production cost
• A class of minimax problems solvable in polynomial time.
• A decomposition algorithm for solving certain classes of production-transportation problems with concave production cost
• A pseudo-polynomial primal-dual algorithm for globally solving a production-transportation problem

Cited in

(15)

• The point-to-point delivery and connection problems: Complexity and algorithms
• The complexity of makespan minimization for pipeline transportation.
• MIP formulations and heuristics for two-level production-transportation problems
• A note on the complexity of the transportation problem with a permutable demand vector
• Solving the production transportation problem via a deterministic annealing neural network method
• Complexity and algorithms for nonlinear optimization problems
• On a decentralized transportation problem
• A production-transportation problem with piecewise linear cost structures
• Strongly polynomial algorithm for a production-transportation problem with concave production cost
• scientific article; zbMATH DE number 1996458 (Why is no real title available?)
• scientific article; zbMATH DE number 1450254 (Why is no real title available?)
• Network equilibrium of production, transportation and pricing for multi-product multi-market
• Approximation algorithms for general one-warehouse multi-retailer systems
• scientific article; zbMATH DE number 3202057 (Why is no real title available?)
• A class of minimax problems solvable in polynomial time.

This page was built for publication: On the Complexity of the Production-Transportation Problem

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