Please use this identifier to cite or link to this item:
http://dspace.mediu.edu.my:8181/xmlui/handle/1721.1/5158Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.creator | Wong, Richard T. | - |
| dc.date | 2004-05-28T19:25:44Z | - |
| dc.date | 2004-05-28T19:25:44Z | - |
| dc.date | 1978-12 | - |
| dc.date.accessioned | 2013-10-09T02:38:02Z | - |
| dc.date.available | 2013-10-09T02:38:02Z | - |
| dc.date.issued | 2013-10-09 | - |
| dc.identifier | http://hdl.handle.net/1721.1/5158 | - |
| dc.identifier.uri | http://koha.mediu.edu.my:8181/xmlui/handle/1721 | - |
| dc.description | The Optimal Network problem (as defined by Scott [16]) consists of selecting a subset of arcs that minimizes the sum of the shortest paths between all nodes subject to a budget constraint. This paper considers the worst-case behavior of heuristics for this prob'em. Let n be the number of nodes in the network and e be a constant between 0 and 1. For a general class of Optimal Network Problems, we show that the question of finding a solution which is always less than n times the optimal solution is NP-complete. This indicates that all polynomial-time heuristics for the problem most probably have poor worst-case performance. An upper bound for worst-case heuristic performance of 2n times the optimal solution is also derived. For a restricted version of the Optimal Network problem we describe a procedure whose maximum percentage of error is bounded by a constant. | - |
| dc.description | This research was supported, in part, by the U. S. Department of Transportation under Contract DOT-TSC-1058, Transportation Advanced Research Program (TARP). | - |
| dc.format | 1746 bytes | - |
| dc.format | 1324684 bytes | - |
| dc.format | application/pdf | - |
| dc.language | en_US | - |
| dc.publisher | Massachusetts Institute of Technology, Operations Research Center | - |
| dc.relation | Operations Research Center Working Paper;OR 085-78 | - |
| dc.title | Worst-Case Analysis of Network Design Problem Heuristics | - |
| dc.type | Working Paper | - |
| Appears in Collections: | MIT Items | |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.