|
|||||
|
|
| Three Open On- line CombinatorialOptimization Problems | |
| 作者姓名： | ZHANG Yu zhong LI Shu jin DENG Xiao tie .Institute of Operations Research Qufu Normal University .Shandong Educational College Jinan .Deptartment of CS City University of Hong Kong Kowloon HK |
| 作者单位： | ZHANG Yu zhong1，LI Shu jin 2，DENG Xiao tie3 1.Institute of Operations Research，Qufu Normal University，273165 2.Shandong Educational College，Jinan 250013 3.Deptartment of CS，City University of Hong Kong，Kowloon，HK |
| 基金项目： | This work is supported by NSF of China and Shandong Province and The Grant of Young and Middle-age Scientists in Shandong Provi |
| 摘 要： | 1 IntroductionReal life decisions are often made in advance of knowing complete information.Introducedby Sleator and Tarjan 1 6] ,the competitive analysis of on-line algorithms has beensuccessfully applied to more and more problems in various areas.The main idea here is toevaluate strategies by the worstcase ratio oftheir performance againstthe optimal solutionunder complete information.More precisely,let CA(J) be the costfunction obtained by anon-line strategy A (that operates under avai… |
Three Open On-line Combinatorial Optimization Problems |
|
| ZHANG Yu zhong,LI Shu jin ,DENG Xiao tie .Institute of Operations Research,Qufu Normal University, .Shandong Educational College,Jinan .Deptartment of CS,City University of Hong Kong,Kowloon,HK.Three Open On- line CombinatorialOptimization Problems[J].Journal of Systems Science and Systems Engineering,2001,10(1). | |
| Authors: | ZHANG Yu-zhong LI Shu-jin DENG Xiao-tie |
| Institution: | 1. Institute of Operations Research, Qufu Normal University, 273165 2. Shandong Educational College, Jinan 250013 3. Deptartment of CS, City University of Hong Kong, Kowloon, HK |
| Abstract: | We present three open combinatorial optimization problems from the standpoint of competitive analysis, in the case that there is no complete information. |
| Keywords: | Competitive analysis k\|server problem on\|line algorithm scheduling |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |