The University of Arizona Campus Repository
>
UA Graduate and Undergraduate Research
>
UA Theses and Dissertations
>
Dissertations
>

# An algorithmic approach to center location and related problems.

- Persistent Link:
- http://hdl.handle.net/10150/185767
- Title:
- An algorithmic approach to center location and related problems.
- Author:
- Issue Date:
- 1992
- Publisher:
- Rights:
- Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
- Abstract:
- Center location on cactus graphs. The p-center problem has been shown to be NP-hard for case of a general graph, yet polynomial algorithms exist for the case of a tree graph. Specifically, we consider "cactus graphs" where each edge is contained in at most one cycle. We show that the p-center problem on this class can be solved in polynomial time using a decomposition algorithm. We partition the graph into a set of subgraphs which are then solved sequentially. The solutions to the subgraphs are linked by a single parameter. The algorithm runs in polynomial time. Locating capacity limited centers on trees. The uncapacitated p-center problem on trees is solvable in polynomial time. We extend this result to include the case where each center can serve a limited number of customers and show that the capacitated p-center on trees can be solved in polynomial time when the capacities are identical. The algorithm consists of solving a capacitated covering problem and then using search routines to find the optimal domination radius. Center location on spheres. We discuss the unweighted center location problem. The following results are presented: (i) An O(n) time algorithm to solve the 1-center problem if the vertices are on one half of the sphere, and an O(n) time algorithm to check whether this condition holds. Both algorithms are based on presenting the problems as 3-dimensional convex programming problems with linear constraints and applying a pruning technique to find the optimum in O(n) time. (ii) An O(n$\sp3$ log n) time algorithm for the 2-center problem on the whole sphere. (iii) A reduction to show that the general p-center problem on a sphere is NP-hard. Locating hyperplanes on hypercubes. In linear regression models we are interested in locating a (d-1) dimensional hyperplane that will be as "close" as possible to existing vertices in the d-dimensional hypercube. The least squares criterion is usually applied for the linear fitting problem; while fitting according to the least absolute value ("minisum") seems to be "complicated". We solve fitting problems with the minisum criterion and present linear time algorithms when the dimension d is fixed. (Abstract shortened with permission of author.)
- Type:
- text; Dissertation-Reproduction (electronic)
- Keywords:
- Degree Name:
- Ph.D.
- Degree Level:
- doctoral
- Degree Program:
- Degree Grantor:
- University of Arizona
- Advisor:

# Full metadata record

DC Field | Value | Language |
---|---|---|

dc.language.iso | en | en_US |

dc.title | An algorithmic approach to center location and related problems. | en_US |

dc.creator | Jaeger, Mordechai. | en_US |

dc.contributor.author | Jaeger, Mordechai. | en_US |

dc.date.issued | 1992 | en_US |

dc.publisher | The University of Arizona. | en_US |

dc.rights | Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author. | en_US |

dc.description.abstract | Center location on cactus graphs. The p-center problem has been shown to be NP-hard for case of a general graph, yet polynomial algorithms exist for the case of a tree graph. Specifically, we consider "cactus graphs" where each edge is contained in at most one cycle. We show that the p-center problem on this class can be solved in polynomial time using a decomposition algorithm. We partition the graph into a set of subgraphs which are then solved sequentially. The solutions to the subgraphs are linked by a single parameter. The algorithm runs in polynomial time. Locating capacity limited centers on trees. The uncapacitated p-center problem on trees is solvable in polynomial time. We extend this result to include the case where each center can serve a limited number of customers and show that the capacitated p-center on trees can be solved in polynomial time when the capacities are identical. The algorithm consists of solving a capacitated covering problem and then using search routines to find the optimal domination radius. Center location on spheres. We discuss the unweighted center location problem. The following results are presented: (i) An O(n) time algorithm to solve the 1-center problem if the vertices are on one half of the sphere, and an O(n) time algorithm to check whether this condition holds. Both algorithms are based on presenting the problems as 3-dimensional convex programming problems with linear constraints and applying a pruning technique to find the optimum in O(n) time. (ii) An O(n$\sp3$ log n) time algorithm for the 2-center problem on the whole sphere. (iii) A reduction to show that the general p-center problem on a sphere is NP-hard. Locating hyperplanes on hypercubes. In linear regression models we are interested in locating a (d-1) dimensional hyperplane that will be as "close" as possible to existing vertices in the d-dimensional hypercube. The least squares criterion is usually applied for the linear fitting problem; while fitting according to the least absolute value ("minisum") seems to be "complicated". We solve fitting problems with the minisum criterion and present linear time algorithms when the dimension d is fixed. (Abstract shortened with permission of author.) | en_US |

dc.type | text | en_US |

dc.type | Dissertation-Reproduction (electronic) | en_US |

dc.subject | Dissertations, Academic. | en_US |

dc.subject | Graph theory. | en_US |

dc.subject | Graph algorithms. | en_US |

thesis.degree.name | Ph.D. | en_US |

thesis.degree.level | doctoral | en_US |

thesis.degree.discipline | Systems and Industrial Engineering | en_US |

thesis.degree.discipline | Graduate College | en_US |

thesis.degree.grantor | University of Arizona | en_US |

dc.contributor.advisor | Goldberg, Jeffrey | en_US |

dc.contributor.committeemember | Mirchandani, P.B. | en_US |

dc.contributor.committeemember | Dror, Moshe | en_US |

dc.contributor.committeemember | Wright, Arthur Larry | en_US |

dc.contributor.committeemember | Denny, John L. | en_US |

dc.identifier.proquest | 9220694 | en_US |

dc.identifier.oclc | 712295583 | en_US |

All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.