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. 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.
    2. 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.
    3. 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.
    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. 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.
    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. Kadner-Graziano, Alessandro S., 2023. "Mergers of Complements: On the Absence of Consumer Benefits," International Journal of Industrial Organization, Elsevier, vol. 89(C).
    5. Pels, Eric, 2021. "Product differentiation and network optimality," Transport Policy, Elsevier, vol. 110(C), pages 415-429.
    6. 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.
    7. 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).
    8. 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.
    9. Yogesh Agarwal, 2013. "Design of Survivable Networks Using Three- and Four-Partition Facets," Operations Research, INFORMS, vol. 61(1), pages 199-213, February.
    10. 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.
    11. Á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.
    12. Clavijo López, Christian & Crama, Yves & Pironet, Thierry & Semet, Frédéric, 2024. "Multi-period distribution networks with purchase commitment contracts," European Journal of Operational Research, Elsevier, vol. 312(2), pages 556-572.
    13. Jiang, Changmin & Zhang, Anming, 2014. "Effects of high-speed rail and airline cooperation under hub airport capacity constraint," Transportation Research Part B: Methodological, Elsevier, vol. 60(C), pages 33-49.
    14. Vatsa, Amit Kumar & Jayaswal, Sachin, 2015. "A New Formulation and Benders' Decomposition for Multi-period facility Location Problem with Server Uncertainty," IIMA Working Papers WP2015-02-07, Indian Institute of Management Ahmedabad, Research and Publication Department.
    15. Brueckner, Jan K., 2001. "The economics of international codesharing: an analysis of airline alliances," International Journal of Industrial Organization, Elsevier, vol. 19(10), pages 1475-1498, December.
    16. Frederick Kaefer & June S. Park, 1998. "Interconnecting LANs and a FDDI Backbone Using Transparent Bridges: A Model and Solution Algorithms," INFORMS Journal on Computing, INFORMS, vol. 10(1), pages 25-39, February.
    17. Encaoua, David & Moreaux, Michel & Perrot, Anne, 1996. "Compatibility and competition in airlines demand side network effects," International Journal of Industrial Organization, Elsevier, vol. 14(6), pages 701-726, October.
    18. Ljubić, Ivana & Mutzel, Petra & Zey, Bernd, 2017. "Stochastic survivable network design problems: Theory and practice," European Journal of Operational Research, Elsevier, vol. 256(2), pages 333-348.
    19. Joseph A. Clougherty & Anming Zhang, 2009. "Domestic rivalry and export performance: theory and evidence from international airline markets," Canadian Journal of Economics, Canadian Economics Association, vol. 42(2), pages 440-468, May.
    20. Clougherty, Joseph A., 2004. "Integrating Industrial Organization and International Business to Explain the Cross-National Domestic Airline Merger Phenomenon," Discussion Paper Series of SFB/TR 15 Governance and the Efficiency of Economic Systems 19, Free University of Berlin, Humboldt University of Berlin, University of Bonn, University of Mannheim, University of Munich.

    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.