IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v55y2013i2p261-278.html
   My bibliography  Save this article

A dual algorithm for the minimum covering weighted ball problem in $${\mathbb{R}^n}$$

Author

Listed:
  • P. Dearing
  • Andrea Smith

Abstract

The nonlinear convex programming problem of finding the minimum covering weighted ball of a given finite set of points in $${\mathbb{R}^n}$$ is solved by generating a finite sequence of subsets of the points and by finding the minimum covering weighted ball of each subset in the sequence until all points are covered. Each subset has at most n + 1 points and is affinely independent. The radii of the covering weighted balls are strictly increasing. The minimum covering weighted ball of each subset is found by using a directional search along either a ray or a circular arc, starting at the solution to the previous subset. The step size is computed explicitly at each iteration. Copyright Springer Science+Business Media, LLC. 2013

Suggested Citation

  • P. Dearing & Andrea Smith, 2013. "A dual algorithm for the minimum covering weighted ball problem in $${\mathbb{R}^n}$$," Journal of Global Optimization, Springer, vol. 55(2), pages 261-278, February.
    • Handle: RePEc:spr:jglopt:v:55:y:2013:i:2:p:261-278
    DOI: 10.1007/s10898-011-9796-9
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10898-011-9796-9
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10898-011-9796-9?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Nimrod Megiddo, 1983. "The Weighted Euclidean 1-Center Problem," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 498-504, November.
    2. Donald W. Hearn & James Vijay, 1982. "Efficient Algorithms for the (Weighted) Minimum Circle Problem," Operations Research, INFORMS, vol. 30(4), pages 777-795, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Piyush Kumar & E. Alper Yıldırım, 2009. "An Algorithm and a Core Set Result for the Weighted Euclidean One-Center Problem," INFORMS Journal on Computing, INFORMS, vol. 21(4), pages 614-629, November.
    2. Mark E. Cawood & P. M. Dearing, 2024. "The weighted Euclidean one-center problem in $${\mathbb {R}}^n$$ R n," Computational Optimization and Applications, Springer, vol. 89(2), pages 553-574, November.
    3. M. Cera & J. A. Mesa & F. A. Ortega & F. Plastria, 2008. "Locating a Central Hunter on the Plane," Journal of Optimization Theory and Applications, Springer, vol. 136(2), pages 155-166, February.
    4. Blanco, Víctor & Puerto, Justo, 2021. "Covering problems with polyellipsoids: A location analysis perspective," European Journal of Operational Research, Elsevier, vol. 289(1), pages 44-58.
    5. Zvi Drezner & G. O. Wesolowsky, 1991. "Facility location when demand is time dependent," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(5), pages 763-777, October.
    6. Liu, Yulin & Hansen, Mark & Ball, Michael O. & Lovell, David J., 2021. "Causal analysis of flight en route inefficiency," Transportation Research Part B: Methodological, Elsevier, vol. 151(C), pages 91-115.
    7. Wei-jie Cong & Le Wang & Hui Sun, 2020. "Rank-two update algorithm versus Frank–Wolfe algorithm with away steps for the weighted Euclidean one-center problem," Computational Optimization and Applications, Springer, vol. 75(1), pages 237-262, January.
    8. P. M. Dearing & Pietro Belotti & Andrea M. Smith, 2016. "A primal algorithm for the weighted minimum covering ball problem in $$\mathbb {R}^n$$ R n," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 24(2), pages 466-492, July.
    9. O Berman & Z Drezner, 2003. "A probabilistic one-centre location problem on a network," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(8), pages 871-877, August.
    10. Gass, Saul I. & Roy, Pallabi Guha, 2003. "The compromise hypersphere for multiobjective linear programming," European Journal of Operational Research, Elsevier, vol. 144(3), pages 459-479, February.
    11. Drezner, Zvi & Guyse, Jeffery, 1999. "Application of decision analysis techniques to the Weber facility location problem," European Journal of Operational Research, Elsevier, vol. 116(1), pages 69-79, July.
    12. Minnie H. Patel & Deborah L. Nettles & Stuart J. Deutsch, 1993. "A linear‐programming‐based method for determining whether or not n demand points are on a hemisphere," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(4), pages 543-552, June.
    13. Sándor P. Fekete & Joseph S. B. Mitchell & Karin Beurer, 2005. "On the Continuous Fermat-Weber Problem," Operations Research, INFORMS, vol. 53(1), pages 61-76, February.
    14. P. M. Dearing & Mark E. Cawood, 2023. "The minimum covering Euclidean ball of a set of Euclidean balls in $$I\!\!R^n$$ I R n," Annals of Operations Research, Springer, vol. 322(2), pages 631-659, March.
    15. Nazlı Dolu & Umur Hastürk & Mustafa Kemal Tural, 2020. "Solution methods for a min–max facility location problem with regional customers considering closest Euclidean distances," Computational Optimization and Applications, Springer, vol. 75(2), pages 537-560, March.
    16. Zvi Drezner, 1987. "On the rectangular p‐center problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(2), pages 229-234, April.
    17. Okabe, Atsuyuki & Suzuki, Atsuo, 1997. "Locational optimization problems solved through Voronoi diagrams," European Journal of Operational Research, Elsevier, vol. 98(3), pages 445-456, May.
    18. Elshaikh, Abdalla & Salhi, Said & Nagy, Gábor, 2015. "The continuous p-centre problem: An investigation into variable neighbourhood search with memory," European Journal of Operational Research, Elsevier, vol. 241(3), pages 606-621.
    19. Nguyen Mau Nam & Maria Cristina Villalobos & Nguyen Thai An, 2012. "Minimal Time Functions and the Smallest Intersecting Ball Problem with Unbounded Dynamics," Journal of Optimization Theory and Applications, Springer, vol. 154(3), pages 768-791, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jglopt:v:55:y:2013:i:2:p:261-278. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.