An algorithmic approach to continuous location

Simple item page
dc.contributor.advisorBecker, Ronald Ien_ZA
dc.contributor.authorChiang, Y Ben_ZA
dc.date.accessioned2016-03-04T16:34:13Z
dc.date.available2016-03-04T16:34:13Z
dc.date.issued1995en_ZA
dc.descriptionBibliography: pages 126-130.en_ZA
dc.description.abstractWe 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.en_ZA
dc.identifier.apacitationChiang, Y. B. (1995). <i>An algorithmic approach to continuous location</i>. (Thesis). University of Cape Town ,Faculty of Science ,Department of Mathematics and Applied Mathematics. Retrieved from http://hdl.handle.net/11427/17441en_ZA
dc.identifier.chicagocitationChiang, Y B. <i>"An algorithmic approach to continuous location."</i> Thesis., University of Cape Town ,Faculty of Science ,Department of Mathematics and Applied Mathematics, 1995. http://hdl.handle.net/11427/17441en_ZA
dc.identifier.citationChiang, Y. 1995. An algorithmic approach to continuous location. University of Cape Town.en_ZA
dc.identifier.ris TY - Thesis / Dissertation AU - Chiang, Y B AB - 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. DA - 1995 DB - OpenUCT DP - University of Cape Town LK - https://open.uct.ac.za PB - University of Cape Town PY - 1995 T1 - An algorithmic approach to continuous location TI - An algorithmic approach to continuous location UR - http://hdl.handle.net/11427/17441 ER - en_ZA
dc.identifier.urihttp://hdl.handle.net/11427/17441
dc.identifier.vancouvercitationChiang YB. An algorithmic approach to continuous location. [Thesis]. University of Cape Town ,Faculty of Science ,Department of Mathematics and Applied Mathematics, 1995 [cited yyyy month dd]. Available from: http://hdl.handle.net/11427/17441en_ZA
dc.language.isoengen_ZA
dc.publisher.departmentDepartment of Mathematics and Applied Mathematicsen_ZA
dc.publisher.facultyFaculty of Scienceen_ZA
dc.publisher.institutionUniversity of Cape Town
dc.subject.otherMathematicsen_ZA
dc.titleAn algorithmic approach to continuous locationen_ZA
dc.typeMaster Thesis
dc.type.qualificationlevelMasters
dc.type.qualificationnameMScen_ZA
uct.type.filetypeText
uct.type.filetypeImage
uct.type.publicationResearchen_ZA
uct.type.resourceThesisen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
thesis_sci_1995_chiang_y_b.pdf
Size:
2.26 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Masters