Skip to main content
Erschienen in:
Buchtitelbild

2017 | OriginalPaper | Buchkapitel

Algorithms for the Ring Star Problem

verfasst von : Xujin Chen, Xiaodong Hu, Zhongzheng Tang, Chenhao Wang, Ying Zhang

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

We address the Ring Star Problem (RSP) on a complete graph \(G=(V,E)\) whose edges are associated with both a nonnegative ring cost and a nonnegative assignment cost. The RSP is to locate a simple ring (cycle) R in G with the objective of minimizing the sum of two costs: the ring cost of (all edges in) R and the assignment cost for attaching nodes in \(V\setminus V(R)\) to their closest ring nodes (in R). We focus on the metric RSP with fixed edge-cost ratio, in which both ring cost function and assignment cost function defined on E satisfy triangle inequalities, and the ratios between the ring cost and assignment cost are the same value \(M\ge 1\) for all edges.
We show that the star structure is an optimal solution of the RSP when \(M\ge (|V|-1)/2\). This particularly implies a \(\sqrt{|V|-1}\)-approximation algorithm for the general RSP. Heuristics based on some natural strategies are proposed. Simulation results demonstrate that the proposed approximation and heuristic algorithms have very good practical performances. We also consider the capacitated RSP which puts an upper limit k on the number of leaf nodes that a ring node can serve. We present a \((10+6M/k)\)-approximation algorithm for the capacitated generalization.

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!

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!

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!

Literatur
1.
Zurück zum Zitat Baldacci, R., DellAmico, M.: Heuristic algorithms for the multi-depot ring-star problem. Eur. J. Oper. Res. 203(1), 270–281 (2010)CrossRefMATH Baldacci, R., DellAmico, M.: Heuristic algorithms for the multi-depot ring-star problem. Eur. J. Oper. Res. 203(1), 270–281 (2010)CrossRefMATH
2.
3.
Zurück zum Zitat Calvete, H.I., Gale, C., Iranzo, J.A.: An efficient evolutionary algorithm for the ring star problem. Eur. J. Oper. Res. 231(1), 22–33 (2013)CrossRefMATHMathSciNet Calvete, H.I., Gale, C., Iranzo, J.A.: An efficient evolutionary algorithm for the ring star problem. Eur. J. Oper. Res. 231(1), 22–33 (2013)CrossRefMATHMathSciNet
5.
Zurück zum Zitat Dias, T.C.S., de Sousa Filho, G.F., Macambira, E.M., dos Anjos F. Cabral, L., Fampa, M.H.C.: An efficient heuristic for the ring star problem. In: Àlvarez, C., Serna, M. (eds.) WEA 2006. LNCS, vol. 4007, pp. 24–35. Springer, Heidelberg (2006). https://doi.org/10.1007/11764298_3 CrossRef Dias, T.C.S., de Sousa Filho, G.F., Macambira, E.M., dos Anjos F. Cabral, L., Fampa, M.H.C.: An efficient heuristic for the ring star problem. In: Àlvarez, C., Serna, M. (eds.) WEA 2006. LNCS, vol. 4007, pp. 24–35. Springer, Heidelberg (2006). https://​doi.​org/​10.​1007/​11764298_​3 CrossRef
6.
Zurück zum Zitat Fekete, S.P., Khuller, S., Klemmstein, M., Raghavachari, B., Young, N.: A network-flow technique for finding low-weight bounded-degree spanning trees. J. Algorithms 24(2), 310–324 (1997)CrossRefMATHMathSciNet Fekete, S.P., Khuller, S., Klemmstein, M., Raghavachari, B., Young, N.: A network-flow technique for finding low-weight bounded-degree spanning trees. J. Algorithms 24(2), 310–324 (1997)CrossRefMATHMathSciNet
7.
Zurück zum Zitat Gupta, A., Kleinberg, J., Kumar, A., Rastogi, R., Yener, B.: Provisioning a virtual private network: a network design problem for multicommodity flow. In: Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, STOC 2001, pp. 389–398. ACM, New York, NY, USA (2001) Gupta, A., Kleinberg, J., Kumar, A., Rastogi, R., Yener, B.: Provisioning a virtual private network: a network design problem for multicommodity flow. In: Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, STOC 2001, pp. 389–398. ACM, New York, NY, USA (2001)
8.
Zurück zum Zitat Labbe, M., Laporte, G., Martin, I.R., Gonzalez, J.J.S.: The ring star problem: polyhedral analysis and exact algorithm. Networks 43(3), 177–189 (2004)CrossRefMATHMathSciNet Labbe, M., Laporte, G., Martin, I.R., Gonzalez, J.J.S.: The ring star problem: polyhedral analysis and exact algorithm. Networks 43(3), 177–189 (2004)CrossRefMATHMathSciNet
9.
Zurück zum Zitat Perez, J.A.M., Moreno-Vega, J.M., Martin, I.R.: Variable neighborhood tabu search and its application to the median cycle problem. Eur. J. Oper. Res. 151(2), 365–378 (2003)CrossRefMATHMathSciNet Perez, J.A.M., Moreno-Vega, J.M., Martin, I.R.: Variable neighborhood tabu search and its application to the median cycle problem. Eur. J. Oper. Res. 151(2), 365–378 (2003)CrossRefMATHMathSciNet
12.
Zurück zum Zitat Simonetti, L., Frota, Y., de Souza, C.C.: The ring-star problem: a new integer programming formulation and a branch-and-cut algorithm. Discrete Appl. Math. 159(16), 1901–1914 (2011)CrossRefMATHMathSciNet Simonetti, L., Frota, Y., de Souza, C.C.: The ring-star problem: a new integer programming formulation and a branch-and-cut algorithm. Discrete Appl. Math. 159(16), 1901–1914 (2011)CrossRefMATHMathSciNet
13.
14.
Zurück zum Zitat Vazirani, V.: Approximation Algorithms, p. 31 (2013) Vazirani, V.: Approximation Algorithms, p. 31 (2013)
Metadaten
Titel
Algorithms for the Ring Star Problem
verfasst von
Xujin Chen
Xiaodong Hu
Zhongzheng Tang
Chenhao Wang
Ying Zhang
Copyright-Jahr
2017
DOI
https://doi.org/10.1007/978-3-319-71147-8_1