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)

    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. James F. Campbell & Morton E. O'Kelly, 2012. "Twenty-Five Years of Hub Location Research," Transportation Science, INFORMS, vol. 46(2), pages 153-169, May.
    3. 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.
    4. M Horn, 1996. "Analysis and Computational Schemes for p-Median Heuristics," Environment and Planning A, , vol. 28(9), pages 1699-1708, September.
    5. Marilène Cherkesly & Claudio Contardo, 2021. "The conditional p-dispersion problem," Journal of Global Optimization, Springer, vol. 81(1), pages 23-83, September.
    6. Eliş, Haluk & Tansel, Barbaros & Oğuz, Osman & Güney, Mesut & Kian, Ramez, 2021. "On guarding real terrains: The terrain guarding and the blocking path problems," Omega, Elsevier, vol. 102(C).
    7. 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.
    8. Ortiz-Astorquiza, Camilo & Contreras, Ivan & Laporte, Gilbert, 2018. "Multi-level facility location problems," European Journal of Operational Research, Elsevier, vol. 267(3), pages 791-805.
    9. Fredriksson, Anders, 2017. "Location-allocation of public services – Citizen access, transparency and measurement. A method and evidence from Brazil and Sweden," Socio-Economic Planning Sciences, Elsevier, vol. 59(C), pages 1-12.
    10. Gianmarco I P Ottaviano & Jacques-François Thisse, 2005. "New Economic Geography: What about the N?," Environment and Planning A, , vol. 37(10), pages 1707-1725, October.
    11. 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.
    12. Michael Brusco & J Dennis Cradit & Douglas Steinley, 2021. "A comparison of 71 binary similarity coefficients: The effect of base rates," PLOS ONE, Public Library of Science, vol. 16(4), pages 1-19, April.
    13. Wen, Meilin & Iwamura, Kakuzo, 2008. "Fuzzy facility location-allocation problem under the Hurwicz criterion," European Journal of Operational Research, Elsevier, vol. 184(2), pages 627-635, January.
    14. Hong Gao & Kai Liu & Xinchao Peng & Cheng Li, 2020. "Optimal Location of Fast Charging Stations for Mixed Traffic of Electric Vehicles and Gasoline Vehicles Subject to Elastic Demands," Energies, MDPI, vol. 13(8), pages 1-16, April.
    15. 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.
    16. 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.
    17. 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.
    18. Kenneth Carling & Mengjie Han & Johan Håkansson, 2012. "Does Euclidean distance work well when the p-median model is applied in rural areas?," Annals of Operations Research, Springer, vol. 201(1), pages 83-97, December.
    19. Holzapfel, Andreas & Potoczki, Tobias & Kuhn, Heinrich, 2023. "Designing the breadth and depth of distribution networks in the retail trade," International Journal of Production Economics, Elsevier, vol. 257(C).
    20. 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.

    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.