The point-to-point delivery and connection problems : complexity and algorithms
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 267-292 |
Journal / Publication | Discrete Applied Mathematics |
Volume | 36 |
Issue number | 3 |
Publication status | Published - 28 May 1992 |
Externally published | Yes |
Link(s)
Abstract
We consider the computational complexity of point-to-point delivery problems. These problems involve shipping one item from each one of p sources to p destinations might be prematched to sources (the fixed destination case), or a source's item might go to any destination (the nonfixed destination case). The networks can be directed or undirected. Up to K items at once can share a truck on an arc, and costs are linear in the number of trucks used. We also consider the closely related point-to-point connection problems, which are to find a minimum cost arc subset connecting sources with destinations. We find that all variations of both problems are strongly NP-hard for all K≤2, but that there are polynomial algorithms in some cases if p is fixed, or if the underlying network is a grid with sources on one side, destinations on the other. © 1992.
Bibliographic Note
Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].
Citation Format(s)
The point-to-point delivery and connection problems: complexity and algorithms. / Li, Chung-Lun; McCormick, S.Thomas; Simchi-Levi, David.
In: Discrete Applied Mathematics, Vol. 36, No. 3, 28.05.1992, p. 267-292.
In: Discrete Applied Mathematics, Vol. 36, No. 3, 28.05.1992, p. 267-292.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review