WIN algorithm for discrete online TSP

Article

Wu, Yonghua, Zhu, Guohun, Chen, Huaying and Qin, Jucun. 2011. "WIN algorithm for discrete online TSP ." Journal of Advanced Computational Intelligence and Intelligent Informatics. 15 (9), pp. 1199-1202.
Article Title

WIN algorithm for discrete online TSP

ERA Journal ID40120
Article CategoryArticle
AuthorsWu, Yonghua (Author), Zhu, Guohun (Author), Chen, Huaying (Author) and Qin, Jucun (Author)
Journal TitleJournal of Advanced Computational Intelligence and Intelligent Informatics
Journal Citation15 (9), pp. 1199-1202
Number of Pages4
Year2011
Place of PublicationTokyo, Japan
ISSN1343-0130
1883-8014
Web Address (URL)http://www.fujipress.jp/JACIII/JACII00150009.html#no_150901
Abstract

Traveling Salesman Problem (TSP) which is proved as an NP-Complete problem is solved by many algorithms. In this paper, we propose online TSP which is based on general discrete metric space. A Waiting- If-Necessary (WIN) algorithm is proposed that involves with increasing cost caused by zealous algorithms and unnecessary waiting caused by cautious algorithms. We measure the performance of the WIN algorithm using competitive analysis and found that it is a 2-competitive algorithm. The competitive ratio of theWIN algorithm can be improved by setting parameter T0.

Keywordscompetitive analysis; discrete metric space; metric TSP; online TSP; waiting-if-necessary
ANZSRC Field of Research 2020460699. Distributed computing and systems software not elsewhere classified
490304. Optimisation
490404. Combinatorics and discrete mathematics (excl. physical combinatorics)
Public Notes

Files associated with this item cannot be displayed due to copyright restrictions.

Byline AffiliationsGuilin University of Electronic Technology, China
Department of Mathematics and Computing
University of Melbourne
Institution of OriginUniversity of Southern Queensland
Permalink -

https://research.usq.edu.au/item/q1486/win-algorithm-for-discrete-online-tsp

Log in to edit
  • 1960
    total views
  • 11
    total downloads
  • 2
    views this month
  • 0
    downloads this month

Export as

Related outputs

Brain Injury Localization and Size Estimation Using Electromagnetic Symmetric Crossing Lines Method
Zhu, Guohun, Bialkowski, Alina, Crozier, Stuart, Guo, Lei, Nguyen, Phong Thanh, Stancombe, Anthony E. and Abbosh, Amin. 2023. "Brain Injury Localization and Size Estimation Using Electromagnetic Symmetric Crossing Lines Method." IEEE Transactions on Instrumentation and Measurement. 72. https://doi.org/10.1109/TIM.2023.3295014
Stroke Localization Using Multiple Ridge Regression Predictors Based on Electromagnetic Signals
Gao, Shang, Zhu, Guohun, Bialkowski, Alina and Zhou, Xujuan. 2023. "Stroke Localization Using Multiple Ridge Regression Predictors Based on Electromagnetic Signals." Mathematics. 11 (2), pp. 1-9. https://doi.org/10.3390/math11020464
Detecting Depression Using Single-Channel EEG and Graph Methods
Zhu, Guohun, Qiu, Tong, Ding, Yi, Gao, Shang, Zhao, Nan, Liu, Feng, Zhou, Xujuan and Gururajan, Raj. 2022. "Detecting Depression Using Single-Channel EEG and Graph Methods." Mathematics. 10 (22), pp. 1-10. https://doi.org/10.3390/math10224177
Predicting Women with Postpartum Depression Symptoms Using Machine Learning Techniques
Gopalakrishnan, Abinaya, Venkataraman, Revathi, Gururajan, Raj, Zhou, Xujuan and Zhu, Guohun. 2022. "Predicting Women with Postpartum Depression Symptoms Using Machine Learning Techniques." Mathematics. 10 (23). https://doi.org/10.3390/math10234570
Stroke Classification in Simulated Electromagnetic Imaging Using Graph Approaches
Zhu, Guohun, Bialkowski, Alina, Guo, Lei, Mohammed, Beadaa and Abbosh, Amin. 2021. "Stroke Classification in Simulated Electromagnetic Imaging Using Graph Approaches ." IEEE Journal of Electromagnetics, RF and Microwaves in Medicine and Biology. 5 (1), pp. 46-53. https://doi.org/10.1109/JERM.2020.2995329
Prevalence of Hepatitis B Virus Infection in Shenzhen, China, 2015–2018
Tao, Jian, Zhang, Weimin, Yue, Huakui, Zhu, Guohun, Wu, Wenyuan, Gong, Wenbo, Fang, Honghui, He, Guirong, Hu, Xiaoyun, Zhao, Hongyue and Liu, Aiqin. 2019. "Prevalence of Hepatitis B Virus Infection in Shenzhen, China, 2015–2018 ." Scientific Reports. 9. https://doi.org/10.1038/s41598-019-50173-5
Analysis and classification of sleep stages based on difference visibility graphs from a single-channel EEG signal
Zhu, Guohun, Li, Yan and Wen, Peng (Paul). 2014. "Analysis and classification of sleep stages based on difference visibility graphs from a single-channel EEG signal." IEEE Journal of Biomedical and Health Informatics. 18 (6), pp. 1813-1821. https://doi.org/10.1109/JBHI.2014.2303991
Classifying epileptic EEG signals with delay permutation entropy and multi-scale K-means
Zhu, Guohun, Li, Yan, Wen, Peng (Paul) and Wang, Shuaifang. 2015. "Classifying epileptic EEG signals with delay permutation entropy and multi-scale K-means." Sun, Changming, Bednarz, Tomasz, Pham, Tuan D., Vallotton, Pascal and Wang, Dadong (ed.) Signal and image analysis for biomedical and life sciences. United States. Springer. pp. 143-157
Analysis of alcoholic EEG signals based on horizontal visibility graph entropy
Zhu, Guohun, Li, Yan, Wen, Peng and Wang, Shuaifang. 2014. "Analysis of alcoholic EEG signals based on horizontal visibility graph entropy." Brain Informatics. 1, pp. 19-25. https://doi.org/10.1007/s40708-014-0003-x
Epileptic seizure detection in EEGs signals using a fast weighted horizontal visibility algorithm
Zhu, Guohun, Li, Yan and Wen, Peng (Paul). 2014. "Epileptic seizure detection in EEGs signals using a fast weighted horizontal visibility algorithm." Computer Methods and Programs in Biomedicine. 115 (2), pp. 64-75. https://doi.org/10.1016/j.cmpb.2014.04.001
Analyzing EEG signals using graph entropy based principle component analysis and J48 decision tree
Wang, Shuaifang, Li, Yan, Wen, Peng and Zhu, Guohun. 2014. "Analyzing EEG signals using graph entropy based principle component analysis and J48 decision tree." Zhang, Teresa (ed.) 6th International Conference on Signal Processing Systems (ICSPS 2014). Dubai, United Arab Emirates 08 - 10 Dec 2014 Rowland Heights, CA. United States. https://doi.org/10.12720/ijsps
Analysis of epileptic EEG signals with simple random sampling J48 algorithm
Wang, Shuaifang, Zhu, Guohun, Li, Yan, Wen, Peng and Song, Bo. 2014. "Analysis of epileptic EEG signals with simple random sampling J48 algorithm." International Journal of Bioscience, Biochemistry and Bioinformatics (IJBBB). 4 (2), pp. 78-81. https://doi.org/10.7763/IJBBB.2014.V4.314
Epileptogenic focus detection in intracranial EEG based on delay permutation entropy
Zhu, Guohun, Li, Yan, Wen, Peng (Paul), Wang, Shuaifang and Xi, Min. 2013. "Epileptogenic focus detection in intracranial EEG based on delay permutation entropy." Sun, Changming, Bednarz, Tomasz, Pham, Tuan D., Vallotton, Pascal and Wang, Dadong (ed.) International Symposium on Computational Models for Life Sciences (CMLS 2013). Sydney, Australia 27 - 29 Nov 2013 United States. AIP Publishing. https://doi.org/10.1063/1.4824993
Unsupervised classification of epileptic EEG signals with multi scale K-means algorithm
Zhu, Guohun, Li, Yan, Wen, Peng (Paul), Wang, Shuaifang and Zhong, Ning. 2013. "Unsupervised classification of epileptic EEG signals with multi scale K-means algorithm." Imamura, Kazayuki, Usui, Shiro, Shirao, Tomoaki, Kasamatsu, Takuji, Schwabe, Lars and Zhong, Ning (ed.) 2013 International Conference on Brain and Health Informatics (BHI 2013). Maebashi, Japan 29 - 31 Oct 2013 Germany. Springer. https://doi.org/10.1007/978-3-319-02753-1_16
Finding a weighted positive influence dominating set in e-learning social networks
Wang, Guangyuan, Wang, Hua, Tao, Xiaohui, Zhang, Ji and Zhu, Guohun. 2013. "Finding a weighted positive influence dominating set in e-learning social networks." International Journal of Computers and Technology. 10 (10), pp. 2136-2145.
Analysis of EEG signals using complex brain networks
Zhu, Guohun. 2014. Analysis of EEG signals using complex brain networks . PhD Thesis Doctor of Philosophy. University of Southern Queensland.
An efficient visibility graph similarity algorithm and its application for sleep stages classification
Zhu, Guohun, Li, Yan and Wen, Peng Paul. 2012. "An efficient visibility graph similarity algorithm and its application for sleep stages classification." Zanzotto, Fabio Massimo, Tsumoto, Shusaku, Taatgen, Niels and Yao, Yiyu (ed.) 2012 International Conference on Brain Informatics (BI 2012). Macau, China 04 - 07 Dec 2012 Heidelberg, Germany. Springer. https://doi.org/10.1007/978-3-642-35139-6_18
Analysing epileptic EEGs with a visibility graph algorithm
Zhu, Guohun, Li, Yan and Wen, Peng (Paul). 2012. "Analysing epileptic EEGs with a visibility graph algorithm." Chen, Qianbin, Huan, Jun (Luke), Xu, Yong, Zhang, Tianqi and Wang, Lipo (ed.) 5th International Conference on Biomedical Engineering and Informatics (BMEI 2012). Chongqing, China 16 - 18 Oct 2012 Piscataway, NJ. United States. https://doi.org/10.1109/BMEI.2012.6513212
Evaluating functional connectivity in alcoholics based on maximal weight matching
Zhu, Guohun, Li, Yan and Wen, Peng. 2011. "Evaluating functional connectivity in alcoholics based on maximal weight matching." Journal of Advanced Computational Intelligence and Intelligent Informatics. 15 (9), pp. 1221-1227.
Co-operative Monitor Web Page Based on MD5
Zhu, Guohun and Miao, YuQing. 2004. "Co-operative Monitor Web Page Based on MD5." GCC 2003: 2nd International Workshop on Grid and Cooperative Computing. Shanghai, China Germany. Springer.