{"id":{"repo_id":"cape-town","oai_identifier":"oai:open.uct.ac.za:11427/17441"},"canonical_url":"https://search.dev.ndltd.org/etd/cape-town/oai:open.uct.ac.za:11427/17441","repository":{"repo_id":"cape-town","name":"University of Cape Town","base_url":"https://open.uct.ac.za/oai/request"},"display":{"title":"An algorithmic approach to continuous location","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Chiang, Y B"],"institution":"Department of Mathematics and Applied Mathematics","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Becker, Ronald I"],"committee_chairs":[],"committee_members":[],"year":1995,"date_issued":"1995","date_published":"1995","updated_at":"2026-07-22T22:22:51Z","subjects":[],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/11427/17441","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Becker, Ronald I"]},{"key":"dc:creator","label":"Author","values":["Chiang, Y B"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2016-03-04T16:34:13Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2016-03-04T16:34:13Z"]},{"key":"dc:date.issued","label":"Date","values":["1995"]},{"key":"dc:publisher.department","label":"Dc Publisher Department","values":["Department of Mathematics and Applied Mathematics"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Cape Town"]},{"key":"dc:type","label":"Dc Type","values":["Master Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["Masters"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["MSc"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/11427/17441"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Bibliography: pages 126-130."]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["An algorithmic approach to continuous location"]}]}],"canonical_facts":{"dc:contributor.advisor":["Becker, Ronald I"],"dc:creator":["Chiang, Y B"],"dc:date.accessioned":["2016-03-04T16:34:13Z"],"dc:date.available":["2016-03-04T16:34:13Z"],"dc:date.issued":["1995"],"dc:description":["Bibliography: pages 126-130."],"dc:description.abstract":["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."],"dc:identifier.uri":["http://hdl.handle.net/11427/17441"],"dc:language.iso":["eng"],"dc:publisher.department":["Department of Mathematics and Applied Mathematics"],"dc:publisher.institution":["University of Cape Town"],"dc:title":["An algorithmic approach to continuous location"],"dc:type":["Master Thesis"],"dc:type.qualificationlevel":["Masters"],"dc:type.qualificationname":["MSc"]},"updated_at":"2026-07-22T22:22:51Z"}