IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v11y2023i9p2000-d1130925.html
   My bibliography  Save this article

Estimations of Covering Functionals of Convex Bodies Based on Relaxation Algorithm

Author

Listed:
  • Man Yu

    (School of Mathematics, North University of China, Taiyuan 030051, China)

  • Yafang Lv

    (School of Navigation, Wuhan University of Technology, Wuhan 430063, China)

  • Yanping Zhao

    (School of Mathematics, North University of China, Taiyuan 030051, China)

  • Chan He

    (School of Mathematics, North University of China, Taiyuan 030051, China)

  • Senlin Wu

    (School of Mathematics, North University of China, Taiyuan 030051, China)

Abstract

Estimating covering functionals of convex bodies is an important part of Chuanming Zong’s program to attack Hadwiger’s covering conjecture, which is a long-standing open problem from convex and discrete geometry. In this paper, we transform this problem into a vertex p -center problem (VPCP). An exact iterative algorithm is introduced to solve the VPCP by making adjustments to the relaxation-based algorithm mentioned by Chen and Chen in 2009. The accuracy of this algorithm is tested by comparing numerical and exact values of covering functionals of convex bodies including the Euclidean disc, simplices, and the regular octahedron. A better lower bound of the covering functional with respect to 7 of 3-simplices is presented.

Suggested Citation

  • Man Yu & Yafang Lv & Yanping Zhao & Chan He & Senlin Wu, 2023. "Estimations of Covering Functionals of Convex Bodies Based on Relaxation Algorithm," Mathematics, MDPI, vol. 11(9), pages 1-15, April.
    • Handle: RePEc:gam:jmathe:v:11:y:2023:i:9:p:2000-:d:1130925
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/11/9/2000/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/11/9/2000/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Chan He & Yafang Lv & Horst Martini & Senlin Wu, 2023. "A Branch-and-Bound Approach for Estimating Covering Functionals of Convex Bodies," Journal of Optimization Theory and Applications, Springer, vol. 196(3), pages 1036-1055, March.
    2. R. Chen & G. Y. Handler, 1987. "Relaxation method for the solution of the minimax location‐allocation problem in euclidean space," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(6), pages 775-788, December.
    3. S. L. Hakimi, 1964. "Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph," Operations Research, INFORMS, vol. 12(3), pages 450-459, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Yunfang Lyu & Feifei Chen & Senlin Wu, 2025. "Homothetic Covering of Crosspolytopes," Mathematics, MDPI, vol. 13(4), pages 1-23, February.

    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. Alfandari, Laurent, 2004. "Choice Rules with Size Constraints for Multiple Criteria Decision Making," ESSEC Working Papers DR 04002, ESSEC Research Center, ESSEC Business School.
    2. S Salhi & A Al-Khedhairi, 2010. "Integrating heuristic information into exact methods: The case of the vertex p-centre problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(11), pages 1619-1631, November.
    3. M Horn, 1996. "Analysis and Computational Schemes for p-Median Heuristics," Environment and Planning A, , vol. 28(9), pages 1699-1708, September.
    4. Daoqin Tong & Alan T. Murray, 2009. "Maximising coverage of spatial demand for service," Papers in Regional Science, Wiley Blackwell, vol. 88(1), pages 85-97, March.
    5. Schnepper, Teresa & Klamroth, Kathrin & Stiglmayr, Michael & Puerto, Justo, 2019. "Exact algorithms for handling outliers in center location problems on networks using k-max functions," European Journal of Operational Research, Elsevier, vol. 273(2), pages 441-451.
    6. Davood Shishebori & Lawrence Snyder & Mohammad Jabalameli, 2014. "A Reliable Budget-Constrained FL/ND Problem with Unreliable Facilities," Networks and Spatial Economics, Springer, vol. 14(3), pages 549-580, December.
    7. P. Daniel Wright & Matthew J. Liberatore & Robert L. Nydick, 2006. "A Survey of Operations Research Models and Applications in Homeland Security," Interfaces, INFORMS, vol. 36(6), pages 514-529, December.
    8. Behrens, Kristian, 2007. "On the location and lock-in of cities: Geography vs transportation technology," Regional Science and Urban Economics, Elsevier, vol. 37(1), pages 22-45, January.
    9. Jiwon Baik & Alan T. Murray, 2022. "Locating a facility to simultaneously address access and coverage goals," Papers in Regional Science, Wiley Blackwell, vol. 101(5), pages 1199-1217, October.
    10. Csiszár, Csaba & Csonka, Bálint & Földes, Dávid & Wirth, Ervin & Lovas, Tamás, 2020. "Location optimisation method for fast-charging stations along national roads," Journal of Transport Geography, Elsevier, vol. 88(C).
    11. Ashraf Abd El Karim & Mohsen M. Awawdeh, 2020. "Integrating GIS Accessibility and Location-Allocation Models with Multicriteria Decision Analysis for Evaluating Quality of Life in Buraidah City, KSA," Sustainability, MDPI, vol. 12(4), pages 1-28, February.
    12. 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.
    13. Zhizhu Lai & Qun Yue & Zheng Wang & Dongmei Ge & Yulong Chen & Zhihong Zhou, 2022. "The min-p robust optimization approach for facility location problem under uncertainty," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1134-1160, September.
    14. Stephanie A. Snyder & Robert G. Haight, 2016. "Application of the Maximal Covering Location Problem to Habitat Reserve Site Selection," International Regional Science Review, , vol. 39(1), pages 28-47, January.
    15. Robichet, Antoine & Nierat, Patrick, 2021. "Consequences of logistics sprawl: Order or chaos? - the case of a parcel service company in Paris metropolitan area," Journal of Transport Geography, Elsevier, vol. 90(C).
    16. Höhn, J. & Lehtonen, E. & Rasi, S. & Rintala, J., 2014. "A Geographical Information System (GIS) based methodology for determination of potential biomasses and sites for biogas plants in southern Finland," Applied Energy, Elsevier, vol. 113(C), pages 1-10.
    17. Averbakh, Igor & Berman, Oded, 1996. "Locating flow-capturing units on a network with multi-counting and diminishing returns to scale," European Journal of Operational Research, Elsevier, vol. 91(3), pages 495-506, June.
    18. Zhang, Tong & Zeng, Zhe & Jia, Tao & Li, Jing, 2016. "Examining the amenability of urban street networks for locating facilities," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 457(C), pages 469-479.
    19. Berman, Oded & Krass, Dmitry & Menezes, Mozart B.C., 2016. "Directed assignment vs. customer choice in location inventory models," International Journal of Production Economics, Elsevier, vol. 179(C), pages 179-191.
    20. Shulin Wang & Shanhua Wu, 2023. "Optimizing the Location of Virtual-Shopping-Experience Stores Based on the Minimum Impact on Urban Traffic," Sustainability, MDPI, vol. 15(13), pages 1-25, June.

    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:gam:jmathe:v:11:y:2023:i:9:p:2000-:d:1130925. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.