On the P-coverage Problem on the Real Line
Abstract: In this paper we consider the p-coverage problem on the real line. We first give a detailed description of an algorithm to solve the coverage problem without the upper bound p on the number of open facilities. Then we analyze how the structure of the optimal solution changes if the setup c...
| Main Authors: | , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5221 |
| _version_ | 1811093446284279808 |
|---|---|
| author | Hoesel, Stan Van Wagelmans, Albert |
| author_facet | Hoesel, Stan Van Wagelmans, Albert |
| author_sort | Hoesel, Stan Van |
| collection | MIT |
| description | Abstract: In this paper we consider the p-coverage problem on the real line. We first give a detailed description of an algorithm to solve the coverage problem without the upper bound p on the number of open facilities. Then we analyze how the structure of the optimal solution changes if the setup costs of the facilities are all decreased by the same amount. This result is used to develop a parametric approach to the p-coverage problem which runs in O(pnlogn) time, n being the number of clients. OR/MS subject classification: Analysis of algorithms, computational complexity: parametric application of dynamic programming; Dynamic programming/optimal control, applications: parametric approach to p-coverage problem on the real line; Facilities/equipment planning, location, discrete: p-coverage problem on the real line. |
| first_indexed | 2024-09-23T15:45:11Z |
| format | Working Paper |
| id | mit-1721.1/5221 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:45:11Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/52212019-04-12T08:16:08Z On the P-coverage Problem on the Real Line Hoesel, Stan Van Wagelmans, Albert Abstract: In this paper we consider the p-coverage problem on the real line. We first give a detailed description of an algorithm to solve the coverage problem without the upper bound p on the number of open facilities. Then we analyze how the structure of the optimal solution changes if the setup costs of the facilities are all decreased by the same amount. This result is used to develop a parametric approach to the p-coverage problem which runs in O(pnlogn) time, n being the number of clients. OR/MS subject classification: Analysis of algorithms, computational complexity: parametric application of dynamic programming; Dynamic programming/optimal control, applications: parametric approach to p-coverage problem on the real line; Facilities/equipment planning, location, discrete: p-coverage problem on the real line. 2004-05-28T19:28:46Z 2004-05-28T19:28:46Z 1991-06 Working Paper http://hdl.handle.net/1721.1/5221 en_US Operations Research Center Working Paper;OR 251-91 1344665 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Hoesel, Stan Van Wagelmans, Albert On the P-coverage Problem on the Real Line |
| title | On the P-coverage Problem on the Real Line |
| title_full | On the P-coverage Problem on the Real Line |
| title_fullStr | On the P-coverage Problem on the Real Line |
| title_full_unstemmed | On the P-coverage Problem on the Real Line |
| title_short | On the P-coverage Problem on the Real Line |
| title_sort | on the p coverage problem on the real line |
| url | http://hdl.handle.net/1721.1/5221 |
| work_keys_str_mv | AT hoeselstanvan onthepcoverageproblemontherealline AT wagelmansalbert onthepcoverageproblemontherealline |