IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v22y2011i4d10.1007_s10878-010-9320-z.html
   My bibliography  Save this article

Geometric rounding: a dependent randomized rounding scheme

Author

Listed:
  • Dongdong Ge

    (Shanghai Jiao Tong University)

  • Simai He

    (The Chinese University of Hong Kong)

  • Yinyu Ye

    (Stanford University)

  • Jiawei Zhang

    (New York University)

Abstract

We develop a new dependent randomized rounding method for approximation of a number of optimization problems with integral assignment constraints. The core of the method is a simple, intuitive, and computationally efficient geometric rounding that simultaneously rounds multiple points in a multi-dimensional simplex to its vertices. Using this method we obtain in a systematic way known as well as new results for the hub location, metric labeling, winner determination and consistent labeling problems. A comprehensive comparison to the dependent randomized rounding method developed by Kleinberg and Tardos (J. ACM 49(5):616–639, 2002) and its variants is also conducted. Overall, our geometric rounding provides a simple and effective alternative for rounding various integer optimization problems.

Suggested Citation

  • Dongdong Ge & Simai He & Yinyu Ye & Jiawei Zhang, 2011. "Geometric rounding: a dependent randomized rounding scheme," Journal of Combinatorial Optimization, Springer, vol. 22(4), pages 699-725, November.
    • Handle: RePEc:spr:jcomop:v:22:y:2011:i:4:d:10.1007_s10878-010-9320-z
    DOI: 10.1007/s10878-010-9320-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-010-9320-z
    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/s10878-010-9320-z?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. Morton O'Kelly & Darko Skorin-Kapov & Jadranka Skorin-Kapov, 1995. "Lower Bounds for the Hub Location Problem," Management Science, INFORMS, vol. 41(4), pages 713-721, April.
    2. James F. Campbell, 1996. "Hub Location and the p -Hub Median Problem," Operations Research, INFORMS, vol. 44(6), pages 923-935, December.
    3. A.A. Ageev & M.I. Sviridenko, 2004. "Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee," Journal of Combinatorial Optimization, Springer, vol. 8(3), pages 307-328, September.
    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. Saberi, Meead & Mahmassani, Hani S., 2013. "Modeling the airline hub location and optimal market problems with continuous approximation techniques," Journal of Transport Geography, Elsevier, vol. 30(C), pages 68-76.
    2. Jairo Ortega & János Tóth & Tamás Péter & Sarbast Moslem, 2020. "An Integrated Model of Park-And-Ride Facilities for Sustainable Urban Mobility," Sustainability, MDPI, vol. 12(11), pages 1-15, June.
    3. Amitai Armon & Iftah Gamzu & Danny Segev, 2014. "Mobile facility location: combinatorial filtering via weighted occupancy," Journal of Combinatorial Optimization, Springer, vol. 28(2), pages 358-375, August.
    4. Bin Liu & Miaomiao Hu, 2022. "Fast algorithms for maximizing monotone nonsubmodular functions," Journal of Combinatorial Optimization, Springer, vol. 43(5), pages 1655-1670, July.
    5. Yu, Bin & Zhu, Hanbing & Cai, Wanjun & Ma, Ning & Kuang, Qiji & Yao, Baozhen, 2013. "Two-phase optimization approach to transit hub location – the case of Dalian," Journal of Transport Geography, Elsevier, vol. 33(C), pages 62-71.
    6. Nader Azizi & Navneet Vidyarthi & Satyaveer S. Chauhan, 2018. "Modelling and analysis of hub-and-spoke networks under stochastic demand and congestion," Annals of Operations Research, Springer, vol. 264(1), pages 1-40, May.
    7. Paul Gölz & Dominik Peters & Ariel Procaccia, 2022. "In This Apportionment Lottery, the House Always Wins," Post-Print hal-03834513, HAL.
    8. B Y Kara & B C Tansel, 2003. "The single-assignment hub covering problem: Models and linearizations," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(1), pages 59-64, January.
    9. Wang, Congke & Liu, Yankui & Yang, Guoqing, 2023. "Adaptive distributionally robust hub location and routing problem with a third-party logistics strategy," Socio-Economic Planning Sciences, Elsevier, vol. 87(PA).
    10. Matsubayashi, Nobuo & Umezawa, Masashi & Masuda, Yasushi & Nishino, Hisakazu, 2005. "A cost allocation problem arising in hub-spoke network systems," European Journal of Operational Research, Elsevier, vol. 160(3), pages 821-838, February.
    11. Simon Bruggmann & Rico Zenklusen, 2019. "Submodular Maximization Through the Lens of Linear Programming," Management Science, INFORMS, vol. 44(4), pages 1221-1244, November.
    12. Ivan Contreras & Elena Fernández, 2014. "Hub Location as the Minimization of a Supermodular Set Function," Operations Research, INFORMS, vol. 62(3), pages 557-570, June.
    13. Jason R. Marden & Adam Wierman, 2013. "Distributed Welfare Games," Operations Research, INFORMS, vol. 61(1), pages 155-168, February.
    14. Tofighian, Aliasghar & Arshadi khamseh, Alireza, 2021. "A Bi objective uncapacitated multiple allocation p-hub median problem in public administration considering economies of scales," Research in Transportation Economics, Elsevier, vol. 90(C).
    15. Ioannis Caragiannis & Gianpiero Monaco, 2013. "A 6/5-approximation algorithm for the maximum 3-cover problem," Journal of Combinatorial Optimization, Springer, vol. 25(1), pages 60-77, January.
    16. Jon Lee & Maxim Sviridenko & Jan Vondrák, 2010. "Submodular Maximization over Multiple Matroids via Generalized Exchange Properties," Mathematics of Operations Research, INFORMS, vol. 35(4), pages 795-806, November.
    17. Sabine Limbourg & Bart Jourquin, 2010. "Market area of intermodal rail‐road container terminals embedded in a hub‐and‐spoke network," Papers in Regional Science, Wiley Blackwell, vol. 89(1), pages 135-154, March.
    18. Tiwari, Richa & Jayaswal, Sachin & Sinha, Ankur, 2019. "Alternate Solution Approaches for Competitive Hub Location Problems," IIMA Working Papers WP 2019-12-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    19. Alumur, Sibel & Kara, Bahar Y., 2008. "Network hub location problems: The state of the art," European Journal of Operational Research, Elsevier, vol. 190(1), pages 1-21, October.
    20. Korhonen Kirsi & Kotavaara Ossi & Muilu Toivo & Rusanen Jarmo, 2017. "Accessibility of Local Food Production to Regional Markets – Case of Berry Production in Northern Ostrobothnia, Finland," European Countryside, Sciendo, vol. 9(4), pages 709-728, December.

    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:jcomop:v:22:y:2011:i:4:d:10.1007_s10878-010-9320-z. 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.