Worst-Case Analysis of Network Design Problem Heuristics
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...
| Main Author: | |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5158 |
| _version_ | 1826204944398548992 |
|---|---|
| author | Wong, Richard T. |
| author_facet | Wong, Richard T. |
| author_sort | Wong, Richard T. |
| collection | MIT |
| 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. |
| first_indexed | 2024-09-23T13:03:31Z |
| format | Working Paper |
| id | mit-1721.1/5158 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:03:31Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/51582019-04-12T08:06:51Z Worst-Case Analysis of Network Design Problem Heuristics Wong, Richard T. 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. This research was supported, in part, by the U. S. Department of Transportation under Contract DOT-TSC-1058, Transportation Advanced Research Program (TARP). 2004-05-28T19:25:44Z 2004-05-28T19:25:44Z 1978-12 Working Paper http://hdl.handle.net/1721.1/5158 en_US Operations Research Center Working Paper;OR 085-78 1746 bytes 1324684 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Wong, Richard T. Worst-Case Analysis of Network Design Problem Heuristics |
| title | Worst-Case Analysis of Network Design Problem Heuristics |
| title_full | Worst-Case Analysis of Network Design Problem Heuristics |
| title_fullStr | Worst-Case Analysis of Network Design Problem Heuristics |
| title_full_unstemmed | Worst-Case Analysis of Network Design Problem Heuristics |
| title_short | Worst-Case Analysis of Network Design Problem Heuristics |
| title_sort | worst case analysis of network design problem heuristics |
| url | http://hdl.handle.net/1721.1/5158 |
| work_keys_str_mv | AT wongrichardt worstcaseanalysisofnetworkdesignproblemheuristics |