Publications
Detailed Information
On the Complexity of the Production-Transportation Problem
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hochbaum, Dorit S. | - |
dc.contributor.author | Hong, Sung-Pil | - |
dc.date.accessioned | 2009-07-10T07:50:43Z | - |
dc.date.available | 2009-07-10T07:50:43Z | - |
dc.date.issued | 1996-02 | - |
dc.identifier.citation | SIAM J. Optim., 6 (1996), pp.250-264 | en |
dc.identifier.issn | 1052-6234 | - |
dc.identifier.uri | https://hdl.handle.net/10371/5346 | - |
dc.description.abstract | The production-transportation problem (PTP) is a generalization of the transportation problem. In PTP, we decide not only the level of shipment from each source to each sink but also the level of supply at each source. A concave production cost function is associated with the assignment of supplies to sources. Thus the objective function of PTP is the sum of the linear transportation costs and the production costs. We show that this problem is generally NP-hard and present some polynomial classes. In particular, we propose a polynomial algorithm for the case in which the transportation cost matrix has the Monge property and the number of sources is fixed. The algorithm generalizes a polynomial algorithm of Tuy, Dan, and Ghannadan [Open Res. Lett., 14 (1993), pp. 99-109] for the problem with two sources. | en |
dc.description.sponsorship | This research has been supported in part by Office of Naval Research grant N00014-91-J-1241. | en |
dc.language.iso | en | - |
dc.publisher | Society for Industrial and Applied Mathematics | en |
dc.subject | production-transportation problem | en |
dc.subject | concave minimization | en |
dc.subject | parametric linear programming | en |
dc.subject | Monge sequence | en |
dc.title | On the Complexity of the Production-Transportation Problem | en |
dc.type | Article | en |
dc.contributor.AlternativeAuthor | 홍성필 | - |
dc.identifier.doi | 10.1137/0806014 | - |
dc.identifier.doi | 10.1137/0806014 | - |
dc.citation.journaltitle | SIAM Journal on Optimization | - |
- Appears in Collections:
- Files in This Item:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.