IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v74y2019i4d10.1007_s10898-018-0714-2.html
   My bibliography  Save this article

On the chance-constrained minimum spanning k-core problem

Author

Listed:
  • Juan Ma

    (Turner Broadcasting System, Inc.)

  • Balabhaskar Balasundaram

    (Oklahoma State University)

Abstract

A graph is called a k-core if every vertex has at least k neighbors. If the parameter k is sufficiently large relative to the number of vertices, a k-core is guaranteed to possess 2-hop reachability between all pairs of vertices. Furthermore, it is guaranteed to preserve those pairwise distances under arbitrary single-vertex deletion. Hence, the concept of a k-core can be used to produce 2-hop survivable network designs, specifically to design inter-hub networks. Formally, given an edge-weighted graph, the minimum spanningk-core problem seeks a spanning subgraph of the given graph that is a k-core with minimum total edge weight. For any fixed k, this problem is equivalent to a generalized graph matching problem and can be solved in polynomial time. This article focuses on a chance-constrained version of the minimum spanning k-core problem under probabilistic edge failures. We first show that this probabilistic version is NP-hard, and we conduct a polyhedral study to strengthen the formulation. The quality of bounds produced by the strengthened formulation is demonstrated through a computational study.

Suggested Citation

  • Juan Ma & Balabhaskar Balasundaram, 2019. "On the chance-constrained minimum spanning k-core problem," Journal of Global Optimization, Springer, vol. 74(4), pages 783-801, August.
    • Handle: RePEc:spr:jglopt:v:74:y:2019:i:4:d:10.1007_s10898-018-0714-2
    DOI: 10.1007/s10898-018-0714-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-018-0714-2
    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/s10898-018-0714-2?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. April K. Andreas & J. Cole Smith, 2008. "Mathematical Programming Algorithms for Two-Path Routing Problems with Reliability Considerations," INFORMS Journal on Computing, INFORMS, vol. 20(4), pages 553-564, November.
    2. Grigory Pastukhov & Alexander Veremyev & Vladimir Boginski & Eduardo L. Pasiliao, 2014. "Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks," Journal of Combinatorial Optimization, Springer, vol. 27(3), pages 462-486, April.
    3. Alexey Sorokin & Vladimir Boginski & Artyom Nahapetyan & Panos M. Pardalos, 2013. "Computational risk management techniques for fixed charge network flow problems with uncertain arc failures," Journal of Combinatorial Optimization, Springer, vol. 25(1), pages 99-122, January.
    4. Brueckner, Jan K. & Spiller, Pablo T., 1991. "Competition and mergers in airline networks," International Journal of Industrial Organization, Elsevier, vol. 9(3), pages 323-342, September.
    5. Quentin Botton & Bernard Fortz & Luis Gouveia & Michael Poss, 2013. "Benders Decomposition for the Hop-Constrained Survivable Network Design Problem," INFORMS Journal on Computing, INFORMS, vol. 25(1), pages 13-26, February.
    6. Qipeng P. Zheng & Siqian Shen & Yuhui Shi, 2015. "Loss-constrained minimum cost flow under arc failure uncertainty with applications in risk-aware kidney exchange," IISE Transactions, Taylor & Francis Journals, vol. 47(9), pages 961-977, September.
    7. Juan Ma & Foad Mahdavi Pajouh & Balabhaskar Balasundaram & Vladimir Boginski, 2016. "The Minimum Spanning k -Core Problem with Bounded CVaR Under Probabilistic Edge Failures," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 295-307, May.
    8. Clyde L. Monma & David F. Shallcross, 1989. "Methods for Designing Communications Networks with Certain Two-Connected Survivability Constraints," Operations Research, INFORMS, vol. 37(4), pages 531-541, 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. Juan Ma & Foad Mahdavi Pajouh & Balabhaskar Balasundaram & Vladimir Boginski, 2016. "The Minimum Spanning k -Core Problem with Bounded CVaR Under Probabilistic Edge Failures," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 295-307, May.
    2. Víctor Blanco & Elena Fernández & Yolanda Hinojosa, 2023. "Hub Location with Protection Under Interhub Link Failures," INFORMS Journal on Computing, INFORMS, vol. 35(5), pages 966-985, September.
    3. Naga V. C. Gudapati & Enrico Malaguti & Michele Monaci, 2022. "Network Design with Service Requirements: Scaling-up the Size of Solvable Problems," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2571-2582, September.
    4. Morimoto, Yu & Takeda, Kohei, 2015. "Policy of airline competition ~monopoly or duopoly~," MPRA Paper 63258, University Library of Munich, Germany.
    5. Lin, Ming Hsin & Zhang, Anming, 2016. "Hub congestion pricing: Discriminatory passenger charges," Economics of Transportation, Elsevier, vol. 5(C), pages 37-48.
    6. Desai, Jitamitra & Sen, Suvrajeet, 2010. "A global optimization algorithm for reliable network design," European Journal of Operational Research, Elsevier, vol. 200(1), pages 1-8, January.
    7. Damien J. Neven & Lars-Hendrik Röller & Zhentang Zhang, 1997. "Union Power and Product Market Competition: Evidence from the Airline Industry," CIG Working Papers FS IV 97-38, Wissenschaftszentrum Berlin (WZB), Research Unit: Competition and Innovation (CIG).
    8. Yang, Lixing & Zhou, Xuesong, 2017. "Optimizing on-time arrival probability and percentile travel time for elementary path finding in time-dependent transportation networks: Linear mixed integer programming reformulations," Transportation Research Part B: Methodological, Elsevier, vol. 96(C), pages 68-91.
    9. Pels, Eric, 2021. "Product differentiation and network optimality," Transport Policy, Elsevier, vol. 110(C), pages 415-429.
    10. Xia, Wenyi & Zhang, Anming, 2016. "High-speed rail and air transport competition and cooperation: A vertical differentiation approach," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 456-481.
    11. Anming Zhang & Yimin Zhang & Joseph A. Clougherty, 2011. "Competition and Regulation in Air Transport," Chapters, in: André de Palma & Robin Lindsey & Emile Quinet & Roger Vickerman (ed.), A Handbook of Transport Economics, chapter 35, Edward Elgar Publishing.
    12. Flores-Fillol, Ricardo, 2009. "Airline competition and network structure," Transportation Research Part B: Methodological, Elsevier, vol. 43(10), pages 966-983, December.
    13. Brueckner, Jan K. & Pels, Eric, 2005. "European airline mergers, alliance consolidation, and consumer welfare," Journal of Air Transport Management, Elsevier, vol. 11(1), pages 27-41.
    14. Rafael Moner Colonques & Ricardo Flores Fillol, 2006. "Strategic Effects Of Airline Alliances," Working Papers. Serie AD 2006-06, Instituto Valenciano de Investigaciones Económicas, S.A. (Ivie).
    15. Brueckner, Jan K & Whalen, W Tom, 2000. "The Price Effects of International Airline Alliances," Journal of Law and Economics, University of Chicago Press, vol. 43(2), pages 503-545, October.
    16. Yogesh Agarwal, 2013. "Design of Survivable Networks Using Three- and Four-Partition Facets," Operations Research, INFORMS, vol. 61(1), pages 199-213, February.
    17. Okan Arslan & Ola Jabali & Gilbert Laporte, 2020. "A Flexible, Natural Formulation for the Network Design Problem with Vulnerability Constraints," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 120-134, January.
    18. Maher, Stephen J., 2021. "Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework," European Journal of Operational Research, Elsevier, vol. 290(2), pages 479-498.
    19. Álvarez-SanJaime, Óscar & Cantos-Sánchez, Pedro & Moner-Colonques, Rafael & Sempere-Monerris, José J., 2013. "Competition and horizontal integration in maritime freight transport," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 51(C), pages 67-81.
    20. Brueckner, Jan K. & Goebel, Anton & Niskanen, Esko, 1997. "Airline Deregulation: The American Experience and Prospects for Europe," Discussion Papers 149, VATT Institute for Economic Research.

    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:74:y:2019:i:4:d:10.1007_s10898-018-0714-2. 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.