IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v14y2007i4d10.1007_s10878-007-9044-x.html
   My bibliography  Save this article

Approximation algorithms and hardness results for labeled connectivity problems

Author

Listed:
  • Refael Hassin

    (Tel-Aviv University)

  • Jérôme Monnot

    (CNRS LAMSADE, Université Paris-Dauphine)

  • Danny Segev

    (Tel-Aviv University)

Abstract

Let G=(V,E) be a connected multigraph, whose edges are associated with labels specified by an integer-valued function ℒ:E→ℕ. In addition, each label ℓ∈ℕ has a non-negative cost c(ℓ). The minimum label spanning tree problem (MinLST) asks to find a spanning tree in G that minimizes the overall cost of the labels used by its edges. Equivalently, we aim at finding a minimum cost subset of labels I⊆ℕ such that the edge set {e∈E:ℒ(e)∈I} forms a connected subgraph spanning all vertices. Similarly, in the minimum label s – t path problem (MinLP) the goal is to identify an s–t path minimizing the combined cost of its labels. The main contributions of this paper are improved approximation algorithms and hardness results for MinLST and MinLP.

Suggested Citation

  • Refael Hassin & Jérôme Monnot & Danny Segev, 2007. "Approximation algorithms and hardness results for labeled connectivity problems," Journal of Combinatorial Optimization, Springer, vol. 14(4), pages 437-453, November.
    • Handle: RePEc:spr:jcomop:v:14:y:2007:i:4:d:10.1007_s10878-007-9044-x
    DOI: 10.1007/s10878-007-9044-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-007-9044-x
    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-007-9044-x?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. Refael Hassin, 1992. "Approximation Schemes for the Restricted Shortest Path Problem," Mathematics of Operations Research, INFORMS, vol. 17(1), pages 36-42, February.
    2. 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)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Xianmin Liu & Jianzhong Li, 2015. "Algorithms and complexity results for labeled correlation clustering problem," Journal of Combinatorial Optimization, Springer, vol. 29(2), pages 488-501, February.
    2. Mehdy Roayaei & Mohammadreza Razzazi, 2017. "Augmenting weighted graphs to establish directed point-to-point connectivity," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 1030-1056, April.
    3. Peng Zhang & Jin-Yi Cai & Lin-Qing Tang & Wen-Bo Zhao, 2011. "Approximation and hardness results for label cut and related problems," Journal of Combinatorial Optimization, Springer, vol. 21(2), pages 192-208, February.

    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. 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.
    2. Esaignani Selvarajah & Rui Zhang, 2014. "Supply chain scheduling to minimize holding costs with outsourcing," Annals of Operations Research, Springer, vol. 217(1), pages 479-490, June.
    3. Randeep Bhatia & Sudipto Guha & Samir Khuller & Yoram J. Sussmann, 1998. "Facility Location with Dynamic Distance Functions," Journal of Combinatorial Optimization, Springer, vol. 2(3), pages 199-217, September.
    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. Geng, Zhichao & Yuan, Jinjiang, 2023. "Single-machine scheduling of multiple projects with controllable processing times," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1074-1090.
    6. Boaz Golany & Moshe Kress & Michal Penn & Uriel G. Rothblum, 2012. "Network Optimization Models for Resource Allocation in Developing Military Countermeasures," Operations Research, INFORMS, vol. 60(1), pages 48-63, February.
    7. Xie, Chi & Travis Waller, S., 2012. "Parametric search and problem decomposition for approximating Pareto-optimal paths," Transportation Research Part B: Methodological, Elsevier, vol. 46(8), pages 1043-1067.
    8. Paul Gölz & Dominik Peters & Ariel Procaccia, 2022. "In This Apportionment Lottery, the House Always Wins," Post-Print hal-03834513, HAL.
    9. Faramroze G. Engineer & George L. Nemhauser & Martin W. P. Savelsbergh, 2011. "Dynamic Programming-Based Column Generation on Time-Expanded Networks: Application to the Dial-a-Flight Problem," INFORMS Journal on Computing, INFORMS, vol. 23(1), pages 105-119, February.
    10. Buu-Chau Truong & Kim-Hung Pho & Van-Buol Nguyen & Bui Anh Tuan & Wing-Keung Wong, 2019. "Graph Theory And Environmental Algorithmic Solutions To Assign Vehicles Application To Garbage Collection In Vietnam," Advances in Decision Sciences, Asia University, Taiwan, vol. 23(3), pages 1-35, September.
    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. Michael Holzhauser & Sven O. Krumke, 2018. "A generalized approximation framework for fractional network flow and packing problems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 87(1), pages 19-50, February.
    13. Jason R. Marden & Adam Wierman, 2013. "Distributed Welfare Games," Operations Research, INFORMS, vol. 61(1), pages 155-168, February.
    14. Luigi Di Puglia Pugliese & Francesca Guerriero, 2013. "A Reference Point Approach for the Resource Constrained Shortest Path Problems," Transportation Science, INFORMS, vol. 47(2), pages 247-265, May.
    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. Chen, Xujin & Hu, Jie & Hu, Xiaodong, 2009. "A polynomial solvable minimum risk spanning tree problem with interval data," European Journal of Operational Research, Elsevier, vol. 198(1), pages 43-46, October.
    17. 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.
    18. Jenkins , Alan, 2005. "Performance Appraisal Research: A Critical Review of Work on “The Social Context and Politics of Appraisal”," ESSEC Working Papers DR 05004, ESSEC Research Center, ESSEC Business School.
    19. Junran Lichen & Jianping Li & Ko-Wei Lih & Xingxing Yu, 0. "Approximation algorithms for constructing required subgraphs using stock pieces of fixed length," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-22.
    20. Vittorio Bilò & Ioannis Caragiannis & Angelo Fanelli & Michele Flammini & Gianpiero Monaco, 2017. "Simple Greedy Algorithms for Fundamental Multidimensional Graph Problems," Post-Print hal-02089412, HAL.

    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:14:y:2007:i:4:d:10.1007_s10878-007-9044-x. 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.