𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A vertex-closing approach to the p-center problem

✍ Scribed by Joseph S. Martinich

Publisher
John Wiley and Sons
Year
1988
Tongue
English
Weight
980 KB
Volume
35
Category
Article
ISSN
0894-069X

No coin nor oath required. For personal study only.

✦ Synopsis

This article uses a vertex-closing approach to investigate the p-center problem. The optimal set of vertices to close are found in imbedded subgraphs of the original graph. Properties of these subgraphs are presented and then used to characterize the optimal solution, to establish a priori upper and lower bounds, to establish refined lower bounds, and to verify the optimality of solutions. These subgraphs form the foundation of two polynomial algorithms of complexity O(lEl log IEI) and O(IEl*). The algorithms are proven to converge to an optimum for special cases, and computational evidence is provided which suggests that they produce very good solutions more generally. Both algorithms perform very well on problems where p is large relative to the number of vertices n, specifically, when p l n 5 0.30. One of the algorithms is especially efficient for solving a sequence of problems on the same graph.

πŸ“œ SIMILAR VOLUMES

Large-scale local search heuristics for
Large-scale local search heuristics for the capacitated vertex p-center problem
✍ Maria Paola Scaparra; Stefano Pallottino; Maria Grazia ScutellΓ  πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 296 KB

## Abstract This article investigates the application of very large neighborhood search techniques for solving the capacitated vertex __p__‐center problem. We characterize a local search neighborhood in terms of path and cyclic exchanges of customers among facilities, and exploit principles borrowe

A Ring Closing Metathesis Approach to th
A Ring Closing Metathesis Approach to the Indole Alkaloid Mitralactonine.
✍ Subhash P. Chavan; Pallavi Sharma; R. Sivappa; Uttam R. Kalkote πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons βš– 19 KB πŸ‘ 2 views

## Abstract ChemInform is a weekly Abstracting Service, delivering concise information at a glance that was extracted from about 200 leading journals. To access a ChemInform Abstract, please click on HTML or PDF.