%0 Journal Article
%T A NOVEL WAY TO ANALYZE COMPETITIVE PERFORMANCE OF ONLINE ALGORITHMS-INSTANCE TRANSFORMATION BASED METHOD<br>一种新的在线调度算法竞争比分析方法——基于实例转换的方法
%A TAO Jiping
%A XI Yugeng
%A <br>陶继平
%A 席裕庚
%J 系统科学与数学
%D 2009
%I 
%X A competitive analysis method for online algorithms is developed based on the idea of instance transformation. The method begins with an arbitrary instance, and transforms the instance along the direction of its performance ratio increasing, moreover the eventual instance after transformation shows a more special structure of which we can take advantage to analyze its performance ratio. This presented method is applied on a single machine online scheduling problem of minimizing the total weighted completion time. We give an alternative proof of an existing conclusion about the competitive performance.
%K Instance transformation
%K online algorithm
%K competitive analysis
%K single machine scheduling
%K total weighted completion time<br>实例转换
%K 在线调度
%K 竞争分析
%K 单机调度
%K 总加权完工时间.
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=6E709DC38FA1D09A4B578DD0906875B5B44D4D294832BB8E&cid=37F46C35E03B4B86&jid=0CD45CC5E994895A7F41A783D4235EC2&aid=F80BA00CFAAD4265A878180C8DEE3049&yid=DE12191FBD62783C&vid=771469D9D58C34FF&iid=F3090AE9B60B7ED1&sid=196B965FCC00ED31&eid=79D108842269596A&journal_id=1000-0577&journal_name=系统科学与数学&referenced_num=0&reference_num=18