Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
One-Dimensional r-Gathering Under Uncertainty Kapitel lesen Erstes Kapitel lesen

2019 | OriginalPaper | Buchkapitel

A Primal Dual Approximation Algorithm for the Multicut Problem in Trees with Submodular Penalties

verfasst von : Xiaofei Liu, Weidong Li

Erschienen in: Algorithmic Aspects in Information and Management

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this paper, we introduce the multicut problem in trees with submodular penalties, which generalizes the prize-collecting multicut problem in trees and vertex cover with submodular penalties. We present a combinatorial 3-approximation algorithm, based on the primal-dual scheme for the multicut problem in trees.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel On Approximations for Constructing Required Subgraphs Using Stock Pieces of Fixed Length
Nächstes Kapitel Algorithmic Aspect on the Minimum (Weighted) Doubly Resolving Set Problem of Graphs
Literatur
1.
Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864–894 (1994)MathSciNetCrossRef
2.
Du, D., Lu, R., Xu, D.: A primal-dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica 63, 191–200 (2012)MathSciNetCrossRef
3.
Fujishige, S.: Submodular Functions and Optimization, 2nd edn. Elsevier, Amsterdam (2005)MATH
4.
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)MathSciNetCrossRef
5.
Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3–20 (1997)MathSciNetCrossRef
6.
Hayrapetyan, A., Swamy, C., Tardos, E.: Network design for information networks. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 933–942 (2005)
7.
Hu, T.C.: Integer Programming and Network Flows. Addison-Wesley, Reading (1969)MATH
8.
Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48(4), 761–777 (2001)MathSciNetCrossRef
9.
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)
10.
Kamiyama, N.: A note on the submodular vertex cover problem withsubmodular penalties. Theor. Comput. Sci. 659, 95–97 (2017)CrossRef
11.
Kanj, I., et al.: Improved parameterized and exact algorithms for cut problems on trees. Theor. Comput. Sci. 607, 455–470 (2015)MathSciNetCrossRef
12.
Khot, S., Regev, O.: Vertex cover might be hard to approximateto with \(2-\epsilon \). J. Comput. Syst. Sci. 74(3), 335–349 (2008)CrossRef
13.
14.
Li, Y., Du, D., Xiu, N., Xu, D.: Improved approximation algorithms for the facility location problems with linear/submodular penalties. Algorithmica 73(2), 460–482 (2015)MathSciNetCrossRef
15.
16.
Xu, D., Wang, F., Du, D., Wu, C.: Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique. Theor. Comput. Sci. 630, 117–125 (2016)MathSciNetCrossRef
17.
Zhang, P., Zhu, D., Luan, J.: An approximation algorithm for the generalized k-multicut problem. Discrete Appl. Math. 160(7–8), 1240–1247 (2012)MathSciNetCrossRef
Metadaten
Titel
A Primal Dual Approximation Algorithm for the Multicut Problem in Trees with Submodular Penalties
verfasst von
Xiaofei Liu
Weidong Li
Copyright-Jahr
2019
Buch
Algorithmic Aspects in Information and Management

Print ISBN: 978-3-030-27194-7

Electronic ISBN: 978-3-030-27195-4

Copyright-Jahr: 2019

DOI
https://doi.org/10.1007/978-3-030-27195-4_19