Value of foreknowledge in the online k-taxi problem

Xin Zheng1, Ke Wang2, Weimin Ma1
1School of Economics and Management, Tongji University, Shanghai, China
2School of Management, Shanghai University, Shanghai, China

Tóm tắt

Từ khóa


Tài liệu tham khảo

El-Yaniv R, Fiat A, Karp RM, Turpin G (1992) Competitive analysis of financial games. In: Proceedings of 33rd annual symposium on foundations of computer science, pp 327–333

El-Yaniv R, Fiat A, Karp RM, Turpin G (2001) Optimal search and one-way trading online algorithms. Algorithmica 30:101–139

Jaillet P, Wagner MR (2006) Online routing problems: value of advanced information as improved competitive ratios. Transp Sci 40(2):200–210

Jaillet P, Wagner MR (2008) Generalized online routing: new competitive ratios, resource augmentation, and asymptotic analyses. Oper Res 56(3):745–757

Ma WM, Wang K (2010) Optimal online risk-tolerant ordering policy for the newsvendor with forecast. J Converg Inf Technol 5(4):54–65

Ma WM, Wang K (2010) Robust solutions to the newsvendor problem under the perspective of competitive analysis. In: Proceedings of the 4th international conference on new trends in information science and service science (NISS 2010), pp 424–429

Wang XZ, Dong LC, Yan JH (2012) Maximum ambiguity based sample selection in fuzzy decision tree induction. IEEE Trans Knowl Data Eng 24(8):1491–1505

Wang XZ, Aamir R, Fu AM (2015) Fuzziness based sample categorization for classifier performance improvement. J Intell Fuzzy Syst 29:1185–1196

Wang XZ, Xing HJ, Li Y, Hua Q, Dong CR, Pedrycz W (2015) A study on relationship between generalization abilities and fuzziness of base classifiers in ensemble learning. IEEE Trans Fuzzy Syst 23(5):1638–1654

Sleator DD, Tarjan RE (1985) Amortized efficiency of list update and paging rules. Commun ACM 28:202–208

Borodin A, El-Yaniv R (1998) Online computation and competitive analysis. Cambridge University Press, Cambridge

Albers S (2003) Online algorithms: a survey. Math Program 97(1–2):3–26

Xu YF, Wang KL, Zhu B (1999) On the k-taxi problem. Information 2(4):429–434

Manasse MS, McGeoch LA, Sleator DD (1990) Competitive algorithms for server problems. J Algorithms 11:208–230

Koutsoupias E, Papadimitriou C (1995) On the k-server conjecture. J ACM 42(5):971–983

Alon N, Karp RM, Peleg D, West D (1995) A graph-theoretic game and its application to the k-server problem. SIAM J Comput 24(1):78–100

Chrobak M, Sgall J (2004) The weighted 2-server problem. Theor Comput Sci 324:289–312

Rudec T, Baumgartner A, Manger R (2013) A fast work function algorithm for solving the k-server problem. CEJOR 21(1):187–205

Xin CL, Ma WM (2004) Scheduling for on-line taxi problem on a real line and competitive algorithms. In: Proceedings of the third international conference on machine learning and cybernetics (ICMLC 2004), pp 3078–3084

Ma WM, Wang K (2006) On-line taxi problem on the benefit-cost graphs. In: Proceeding of 2006 international conference on machine learning and cybernetics (ICMLC 2006), pp 900–905

Ma W, Wang K (2007) On the on-line weighted k-taxi problem. In: Proceedings of the first international symposium on combinatorics, algorithms, probabilistic and experimental methodologies (ESCAPE 2007), (lecture notes in computer science, vol 4614), pp 152–162

Ma W, Gao T, Wang K (2007) On the on-line k-taxi problem with limited look ahead. In: Proceedings of the first international conference on combinatorial optimization and applications (COCOA 2007), (lecture notes in computer science, vol 4616), pp 72–80

Ma W, Xu Y, Wang K (2001) On-line k-truck problem and its competitive algorithms. J Glob Optim 21(1):15–25

Xu Y, Li H, He C, Luo L (2015) The online k-server problem with max-distance objective. J Comb Optim 29(4):836–846

Wang XZ, Dong CR (2009) Improving generalization of fuzzy if-then rules by maximizing fuzzy entropy. IEEE Trans Fuzzy Syst 17(3):556–567

He YL, Liu JNK, Wang XZ, Hu YX (2012) Optimal bandwidth selection for resubstitution entropy estimation. Appl Math Comput 219(8):3425–3460

Wang XZ (2015) Learning from big data with uncertainty—editorial. J Intell Fuzzy Syst 28(5):2329–2330