Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Approximation guarantees of evolutionary optimization on the minimum crossing spanning tree problem

  • Published:
Cluster Computing Aims and scope Submit manuscript

Abstract

The minimum crossing spanning tree (MCST) problem is to find a spanning tree in a given graph G and a family of subsets of vertices S such that the maximum number of edges crossing any set in S reaches minimum value. Evolutionary algorithms (EAs) have been widely used in variety of fields due to its simple and powerful search ability. However, the performance analysis of EAs on the NP-hard MCST problem is still rare. In this paper, we investigate the approximation ability of EAs on the MCST problem from a theoretical point of view. For a special case of the MCST problem where the sets in S are pairwise disjoint, we reveal that a simple EA called (1 + 1) EA can efficiently obtain a spanning tree with crossing at most \(2OPT+2\) in expected runtime \(O(n^7)\), where OPT is the maximum crossing for a minimum crossing spanning tree. Moreover, we also find that for the MCST problem a simple multi-objective evolutionary algorithm called GSEMO can achieve an approximation ratio of \(4r\log n\) in expected polynomial runtime \(O(4rm^3\log n)\). The analysis and results further illustrate that EAs are efficient approximation algorithms for some NP-hard problems.

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Bilò, V., Flammini, M.: On the IP routing tables minimization with addresses reassignments. In: Proceedings, 18th International Parallel and Distributed Processing Symposium (IPDPS), pp. 19–26 (2004)

  2. Bilò, V., Goyal, V., Ravi, R., Singh, M.: On the crossing spanning tree problem. Proceedings. In: International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 51–60. Springer, Berlin (2004)

  3. Fürer, M., Raghavachari, B.: Approximating the minimum degree spanning tree to within one from the optimal degree. In: Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, pp. 317–324 (1992)

  4. Witt, C.: Worst-case and average-case approximations by simple randomized search heuristics. In: Proceedings of the 22th Symposium on Theoretical Aspects of Computer Science Proceedings (STACS05). Lecture Notes on Computer Science, vol. 3404, pp. 44–56. Springer, Heidelberg (2005)

  5. Zhou, Y., Zhang, J., Wang, Y.: Performance analysis of the (1 + 1) evolutionary algorithm for the multiprocessor scheduling problem. Algorithmica 73(1), 21–41 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  6. Friedrich, T., Neumann, F.: Maximizing submodular functions under Matroid constraints by evolutionary algorithms. Evolut. Comput. 23(4), 543–558 (2015)

    Article  Google Scholar 

  7. Xia, X., Lai, X., Yi, C.: The analysis of evolutionary optimization on the TSP(1,2) problem. Int. J. Comput. Sci. Eng. (2017). https://doi.org/10.1504/IJCSE.2016.10007955

  8. Friedrich, T., He, J., Hebbinghaus, N., Neumann, F., Witt, C.: Analyses of simple hybrid algorithms for the vertex cover problem. Evolut. Comput. 17(1), 3–19 (2009)

    Article  Google Scholar 

  9. Yu, Y., Yao, X., Zhou, Z.H.: On the approximation ability of evolutionary optimizationwith application to minimum set cover. Artif. Intell. 180, 20–33 (2012)

    Article  MATH  Google Scholar 

  10. Sutton, A.M., Neumann, F., Nallaperuma, S.: Parameterized runtime analyses of evolutionary algorithms for the planar Euclidean traveling salesperson problem. Evolut. Comput. 22(4), 595–628 (2014)

    Article  Google Scholar 

  11. Xia, X., Zhou, Y.: Performance analysis of ACO on the quadratic assignment problem. Chin. J. Electron. 27(1), 26–34 (2018)

    Article  Google Scholar 

  12. Xia, X., Zhang, G., Fan, D.: Performance analysis of evolutionary optimization on the minimum degree spanning tree problem. J. Comput. Theor. Nanosci. 13(6), 3611–3618 (2016)

    Article  Google Scholar 

  13. Garey, M.R., Johnson, D.S.: Computers and Intractibility: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)

    MATH  Google Scholar 

  14. Greenberg, D.S., Istrail, S.: Physical mapping by STS Hybridization: algorithmic strategies and the challenges of software evaluation. J. Comput. Biol. 2(2), 219–273 (1995)

    Article  Google Scholar 

  15. Roh, P.: Minimum crossing problems on graphs. UWSpace. http://hdl.handle.net/10012/2658 (2007)

  16. Raidl, G.R., Julstrom, B.A.: Edge sets: an effective evolutionary coding of spanning tree. IEEE Trans. Evolut. Comput. 7(3), 225–239 (2003)

    Article  Google Scholar 

  17. Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1 + 1)-evolutionary algorithm. Theor. Comput. Sci. 276(1–2), 51–81 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  18. Laumanns, M., Thiele, L., Zitzler, E.: Running time analysis of multiobjective evolutionary algorithms on pseudo-Boolean functions. IEEE Trans. Evolut. Comput. 8(2), 170–182 (2004)

    Article  MATH  Google Scholar 

  19. Brockhoff, D., Friedrich, T., Hebbinghaus, N., Klein, C., Neumann, F., Zitzler, E.: On the effects of adding objectives to plateau functions. IEEE Trans. Circuits Syst Video Technol. 13(3), 591–603 (2009)

    Google Scholar 

  20. Neumann, F., Wegener, I.: Minimum spanning trees made easier via multi-objective optimization. Nat. Comput. 5(3), 305–319 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  21. Neumann, F.: Expected runtimes of a simple evolutionary algorithm for the multiobjective minimum spanning tree problem. Eur. J. Oper. Res. 181(3), 1620–1629 (2007)

    Article  MATH  Google Scholar 

  22. Friedrich, T., He, J., Hebbinghaus, N., Neumann, F., Witt, C.: Approximating covering problems by randomized search heuristics using multi-objective models. Evolut. Comput. 18(4), 617–633 (2010)

    Article  Google Scholar 

  23. Neumann. F., Reichel, J.: Approximating minimum multicuts by evolutionary multi-objective algorithms. In: Proceedings of the 10th International Conference on Parallel Problem Solving from Nature X, PPSN 2008, LNCS 5199, Springer, Dortmund, pp. 72–81 (2008)

  24. Greiner, G.: Single- and multi-objective evolutionary algorithms for graph bisectioning. In: Proceedings of Foundation of Genetic Algorithms (FOGA 2009), ACM Press, pp. 29–38 (2009)

  25. Lai, X., Zhou, Y., He, J., Zhang, J.: Performance analysis on evolutionary algorithms for the minimum label spanning tree problem. IEEE Trans. Evolut. Comput. 18(6), 860–872 (2014)

    Article  Google Scholar 

  26. He, J., Wang, Y., Zhoum, Y.: Analysis of solution quality of a multiobjective optimization-based evolutionary algorithm for Knapsack problem. In: Ochoa, G., Chicano, F. (eds.) Evolutionary Computation in Combinatorial Optimization. Lecture Notes in Computer Science, vol. 9026. Springer, Cham (2015)

    Google Scholar 

  27. Jensen, M.T.: Helper-objectives: using multi-objective evolutionary algorithms for single-objective optimisation. J. Math. Modell. Algorithms 3(4), 323–347 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  28. Xia, X., Zhou, Y.: On the effectiveness of immune inspired mutation operators in some discrete optimization problems. Inform. Sci. 426, 87–100 (2018)

    Article  MathSciNet  Google Scholar 

  29. Xia, X., Tang, L., Peng, X.: When is the immune inspired B-Cell algorithm superior to the (1 + 1) evolutionary algorithm. Int. J. High Perform. Comput. Network. (2017). https://doi.org/10.1504/IJHPCN.2016.10007954

  30. Gupta, B.B., Agrawal, D.P., Yamaguchi, S.: Handbook of Research on Modern Cryptographic Solutions for Computer and Cyber Security (2016)

  31. Kim, M., Gupta, B.B., Rho, S.: Crowd sourcing based scientific issue tracking with topic analysis. Appl. Soft Comput. 66, 506–511 (2017)

    Article  Google Scholar 

  32. Plageras, A.P., Stergiou, C., Psannis, K.E.: Efficient IoT-based sensor BIG data collectioncprocessing and analysis in smart buildings. Future Gener. Comput. Syst. 82, 349–357 (2018)

    Article  Google Scholar 

  33. Wang, Y., Jiang, F., Gupta, B.B.: Variable selection and optimization in rapid detection of soybean straw biomass based on CARS. IEEE Access. 6, 5290–5299 (2018)

    Article  Google Scholar 

  34. Wang, H., Wang, W., Cui, Z.: A new dynamic firefly algorithm for demand estimation of water resources. Inform. Sci. 438, 95–106 (2018)

    Article  MathSciNet  Google Scholar 

  35. Xia, X., Peng, X., Deng, L.: Performance analysis of evolutionary optimization for the bank account location problem. IEEE Access. 6, 17756–17767 (2018)

    Article  Google Scholar 

  36. He, P., Deng, Z., Wang, H.: Model approach to grammatical evolution: theory and case study. Soft Comput. 20(9), 3537–3548 (2016)

    Article  MATH  Google Scholar 

  37. He, P., Deng, Z., Gao, C.: Model approach to grammatical evolution: deep-structured analyzing of model and representation. Soft Comput. 21(18), 5413–5423 (2017)

    Article  MATH  Google Scholar 

Download references

Acknowledgements

This work is supported by the National Nature Science Foundation of China (Grant No. 71471007), and Zhejiang Provincial Natural Science Foundation of China (Grant No. LY15F030021).

Author information

Authors and Affiliations

  1. School of Economics and Management, Beihang University, Beijing, 100191, People’s Republic of China

    Jianping Zhang & Hong Zhou

  2. School of Mechanical and Electrical Engineering, Jiaxing University, Jiaxing, 314001, People’s Republic of China

    Huimin Gao

Authors
  1. Jianping Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hong Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Huimin Gao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hong Zhou.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Ethical standards

All procedures performed in studies involving human participants were in accordance with the ethical standards of the institutional and/or national research committee and with the 1964 Helsinki Declaration and its later amendments or comparable ethical standards.

Human and animal rights statement

This article does not contain any studies with animals performed by any of the authors.

Informed consent

Informed consent was obtained from all individual participants included in the study.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhang, J., Zhou, H. & Gao, H. Approximation guarantees of evolutionary optimization on the minimum crossing spanning tree problem. Cluster Comput 22, 409–417 (2019). https://doi.org/10.1007/s10586-018-2838-z

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10586-018-2838-z

Keywords

Search

Navigation