IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v238y2016i1d10.1007_s10479-015-2093-0.html
   My bibliography  Save this article

Geometric partitioning and robust ad-hoc network design

Author

Listed:
  • John Gunnar Carlsson

    (University of Southern California)

  • Mehdi Behroozi

    (University of Southern California
    University of Minnesota)

  • Xiang Li

    (University of Minnesota)

Abstract

We present fast approximation algorithms for the problem of dividing a given convex geographic region into smaller sub-regions so as to distribute the workloads of a set of vehicles. Our objective is to partition the region in such a fashion as to ensure that vehicles are capable of communicating with one another under limited communication radii. We consider variations of this problem in which sub-regions are constrained to have equal area or be convex, and as a side consequence, our approach yields a factor 1.99 approximation algorithm for the continuous k-centers problem on a convex polygon.

Suggested Citation

  • John Gunnar Carlsson & Mehdi Behroozi & Xiang Li, 2016. "Geometric partitioning and robust ad-hoc network design," Annals of Operations Research, Springer, vol. 238(1), pages 41-68, March.
    • Handle: RePEc:spr:annopr:v:238:y:2016:i:1:d:10.1007_s10479-015-2093-0
    DOI: 10.1007/s10479-015-2093-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-015-2093-0
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-015-2093-0?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. J. Brimberg & S. Salhi, 2005. "A Continuous Location-Allocation Problem with Zone-Dependent Fixed Cost," Annals of Operations Research, Springer, vol. 136(1), pages 99-115, April.
    2. Oded Berman & Zvi Drezner & Arie Tamir & George Wesolowsky, 2009. "Optimal location with equitable loads," Annals of Operations Research, Springer, vol. 167(1), pages 307-325, March.
    3. Haugland, Dag & Ho, Sin C. & Laporte, Gilbert, 2007. "Designing delivery districts for the vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 180(3), pages 997-1010, August.
    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. Mehdi Behroozi, 2024. "Largest Volume Inscribed Rectangles in Convex Sets Defined by Finite Number of Inequalities," INFORMS Journal on Computing, INFORMS, vol. 36(3), pages 787-819, May.

    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. John Carlsson & Mehdi Behroozi & Xiang Li, 2016. "Geometric partitioning and robust ad-hoc network design," Annals of Operations Research, Springer, vol. 238(1), pages 41-68, March.
    2. Faiz, Tasnim Ibn & Noor-E-Alam, Md, 2019. "Data center supply chain configuration design: A two-stage decision approach," Socio-Economic Planning Sciences, Elsevier, vol. 66(C), pages 119-135.
    3. Liu, Yanchao, 2023. "An elliptical cover problem in drone delivery network design and its solution algorithms," European Journal of Operational Research, Elsevier, vol. 304(3), pages 912-925.
    4. John Gunnar Carlsson, 2012. "Dividing a Territory Among Several Vehicles," INFORMS Journal on Computing, INFORMS, vol. 24(4), pages 565-577, November.
    5. Xin Tang & Ameur Soukhal & Vincent T’kindt, 2014. "Preprocessing for a map sectorization problem by means of mathematical programming," Annals of Operations Research, Springer, vol. 222(1), pages 551-569, November.
    6. Steiner, Maria Teresinha Arns & Datta, Dilip & Steiner Neto, Pedro José & Scarpin, Cassius Tadeu & Rui Figueira, José, 2015. "Multi-objective optimization in partitioning the healthcare system of Parana State in Brazil," Omega, Elsevier, vol. 52(C), pages 53-64.
    7. Rongbing Huang, 2016. "A short note on locating facilities on a path to minimize load range equity measure," Annals of Operations Research, Springer, vol. 246(1), pages 363-369, November.
    8. Jorge Oyola & Halvard Arntzen & David L. Woodruff, 2017. "The stochastic vehicle routing problem, a literature review, Part II: solution methods," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 349-388, December.
    9. Haase, Knut & Hoppe, Mirko, 2008. "Standortplanung unter Wettbewerb - Teil 1: Grundlagen," Discussion Papers 2/2008, Technische Universität Dresden, "Friedrich List" Faculty of Transport and Traffic Sciences, Institute of Transport and Economics.
    10. Drezner, Tammy & Drezner, Zvi & Hulliger, Beat, 2014. "The Quintile Share Ratio in location analysis," European Journal of Operational Research, Elsevier, vol. 238(1), pages 166-174.
    11. Zhen, Lu & Gao, Jiajing & Tan, Zheyi & Laporte, Gilbert & Baldacci, Roberto, 2023. "Territorial design for customers with demand frequency," European Journal of Operational Research, Elsevier, vol. 309(1), pages 82-101.
    12. Lin, Yun Hui & Tian, Qingyun, 2023. "Facility location and pricing problem: Discretized mill price and exact algorithms," European Journal of Operational Research, Elsevier, vol. 308(2), pages 568-580.
    13. Diglio, Antonio & Peiró, Juanjo & Piccolo, Carmela & Saldanha-da-Gama, Francisco, 2021. "Solutions for districting problems with chance-constrained balancing requirements," Omega, Elsevier, vol. 103(C).
    14. Reusken, Meike & Laporte, Gilbert & Rohmer, Sonja U.K. & Cruijssen, Frans, 2024. "Vehicle routing with stochastic demand, service and waiting times — The case of food bank collection problems," European Journal of Operational Research, Elsevier, vol. 317(1), pages 111-127.
    15. Epaminondas G. Kyriakidis & Theodosis D. Dimitrakos & Constantinos C. Karamatsoukis, 2020. "A Stochastic Single Vehicle Routing Problem with a Predefined Sequence of Customers and Collection of Two Similar Materials," Methodology and Computing in Applied Probability, Springer, vol. 22(4), pages 1559-1582, December.
    16. Chandra Ade Irawan & Said Salhi & Kusmaningrum Soemadi, 2020. "The continuous single-source capacitated multi-facility Weber problem with setup costs: formulation and solution methods," Journal of Global Optimization, Springer, vol. 78(2), pages 271-294, October.
    17. Sardar Ansari & Laura Albert McLay & Maria E. Mayorga, 2017. "A Maximum Expected Covering Problem for District Design," Transportation Science, INFORMS, vol. 51(1), pages 376-390, February.
    18. Brimberg, Jack & Drezner, Zvi & Mladenović, Nenad & Salhi, Said, 2014. "A new local search for continuous location problems," European Journal of Operational Research, Elsevier, vol. 232(2), pages 256-265.
    19. Kyriakidis, Epaminondas G. & Dimitrakos, Theodosis D. & Karamatsoukis, Constantinos C., 2019. "Optimal delivery of two similar products to N ordered customers with product preferences," International Journal of Production Economics, Elsevier, vol. 209(C), pages 194-204.
    20. Antonio Diglio & Stefan Nickel & Francisco Saldanha-da-Gama, 2020. "Towards a stochastic programming modeling framework for districting," Annals of Operations Research, Springer, vol. 292(1), pages 249-285, 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:annopr:v:238:y:2016:i:1:d:10.1007_s10479-015-2093-0. 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.