[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

An approximation algorithm for the submodular multicut problem in trees with linear penalties

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

In this paper, we consider the submodular multicut problem in trees with linear penalties (SMCLP(T) problem). In the SMCLP(T) problem, we are given a tree \(T=(V,E)\) with a submodular function \(c(\cdot ): 2^{E}\rightarrow \mathbb {R}_{\ge 0}\), a set of k distinct pairs of vertices \(P=\{(s_1,t_1),(s_2,t_2),\ldots ,(s_k,t_k)\}\) with non-negative penalty costs \(\pi _{j}\) for the pairs \((s_j,t_j)\in P\). The goal is to find a partial multicut \(M\subseteq E\) such that the total cost, consisting of the submodular cost of M and the penalty cost of the pairs not cut by M, is minimized. Let \(P_j\) be the unique path from \(s_j\) to \(t_j\) in the tree, where \(1\le j\le k\) and let m be the maximal length of all \(P_j\). Our main work is to present an m-approximation algorithm for the SMCLP(T) problem via the primal-dual method.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18, 3–20 (1997)

    Article  MathSciNet  Google Scholar 

  2. Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi) cut theorems and their applications. SIAM J. Comput. 25(2), 235–251 (2006)

    Article  MathSciNet  Google Scholar 

  3. Fujishige, S.: Submodular Functions and Optimization, 2nd edn. Elsevier, Amsterdam (2005)

    MATH  Google Scholar 

  4. Iwata, S., Nagano, K.: Submodular function minimization under covering constraints, In: The 50th annual symposium on foundations of computer science, FOCS, pp. 671–680 (2009)

  5. Kamiyama, N.: A note on the submodular vertex cover problem with submodular penalties. Theor. Comput. Sci. 659, 95–97 (2017)

    Article  MathSciNet  Google Scholar 

  6. Levin, A., Segev, D.: Partial multicuts in trees. Theor. Comput. Sci. 369(1–3), 384–395 (2006)

    Article  MathSciNet  Google Scholar 

  7. Liu, X.F., Li, W.D.: A primal dual approximation algorithm for the multicut problem in trees with submodular penalties, In: International Conference on Algorithmic Applications in Management, pp. 203–211 (2019)

  8. Lovász, L.: Submodular Functions and Convexity. In: Bachm, A., Grtschel, M., Korte, B. (eds.) Mathematical Programing the State of the Art, pp. 235–237. Springer, Berlin (1983)

    Google Scholar 

  9. Xu, D.C., Wang, F.M., Du, D.L., Wu, C.C.: Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique. Theor. Comput. Sci. 630, 117–125 (2016)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors would like to thank the referee for giving this paper a careful reading and many valuable comments and useful suggestions. This work was supported by the NSF of China (No. 11971146), the NSF of Hebei Province of China (No. A2019205089, No. A2019205092), Hebei Province Foundation for Returnees (CL201714) and Overseas Expertise Introduction Program of Hebei Auspices (25305008).

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Hebei Normal University, Shijiazhuang, 050024, People’s Republic of China

    Chenfei Hou, Suogang Gao, Wen Liu & Bo Hou

  2. Department of Computer Science, University of Texas at Dallas, Richardson, TX, 75080, USA

    Weili Wu & Ding-Zhu Du

Authors
  1. Chenfei Hou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Suogang Gao
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Wen Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Weili Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Ding-Zhu Du
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Bo Hou
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bo Hou.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hou, C., Gao, S., Liu, W. et al. An approximation algorithm for the submodular multicut problem in trees with linear penalties. Optim Lett 15, 1105–1112 (2021). https://doi.org/10.1007/s11590-020-01665-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-020-01665-1

Keywords

Search

Navigation