Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
An algorithmic approach to continuous location
Bibliography: pages 126-130.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
Department of Mathematics and Applied Mathematics
2016
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613208839192576 |
|---|---|
| access_status_str | Open Access |
| author | Chiang, Y B |
| author2 | Becker, Ronald I |
| author_browse | Becker, Ronald I Chiang, Y B |
| author_facet | Becker, Ronald I Chiang, Y B |
| author_sort | Chiang, Y B |
| collection | Thesis |
| description | Bibliography: pages 126-130. |
| format | Thesis |
| id | oai:open.uct.ac.za:11427/17441 |
| institution | University of Cape Town (South Africa) |
| language | eng |
| last_indexed | 2026-06-10T12:32:29.432Z |
| license_str | Not specified — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from UCTD — University of Cape Town Open Access Repository |
| publishDate | 2016 |
| publishDateRange | 2016 |
| publishDateSort | 2016 |
| publisher | Department of Mathematics and Applied Mathematics |
| publisherStr | Department of Mathematics and Applied Mathematics |
| record_format | dspace |
| source_str | UCTD — University of Cape Town Open Access Repository |
| spelling | oai:open.uct.ac.za:11427/17441 An algorithmic approach to continuous location Chiang, Y B Becker, Ronald I Mathematics Bibliography: pages 126-130. We survey the p-median problem and the p-centre problem. Then we investigate two new techniques for continuous optimal partitioning of a tree T with n - 1 edges, where a nonnegative rational valued weight is associated with each edge. The continuous Max-Min tree partition problem (the continuous Min-Max tree partition problem) is to cut the edges in p - 1 places, so as to maximize (respectively minimize) the weight of the lightest (respectively heaviest) resulting subtree. Thus the tree is partitioned into approximately equal components. For each optimization problem, an inefficient implementation of the algorithm is given, which runs in pseudo-polynomial time, using a previously developed algorithm and a construction. We then derive from it a much faster algorithm using a top-down greedy technique, which runs in polynomial time. The algorithms have a variety of applications among others to highway and pipeline maintenance. 2016-03-04T16:34:13Z 2016-03-04T16:34:13Z 1995 Master Thesis Masters MSc http://hdl.handle.net/11427/17441 eng application/pdf Department of Mathematics and Applied Mathematics Faculty of Science University of Cape Town |
| spellingShingle | Mathematics Chiang, Y B An algorithmic approach to continuous location |
| thesis_degree_str | Master's |
| title | An algorithmic approach to continuous location |
| title_full | An algorithmic approach to continuous location |
| title_fullStr | An algorithmic approach to continuous location |
| title_full_unstemmed | An algorithmic approach to continuous location |
| title_short | An algorithmic approach to continuous location |
| title_sort | algorithmic approach to continuous location |
| topic | Mathematics |
| url | http://hdl.handle.net/11427/17441 |
| work_keys_str_mv | AT chiangyb analgorithmicapproachtocontinuouslocation AT chiangyb algorithmicapproachtocontinuouslocation |