{"id":2906,"date":"2016-07-18T03:32:50","date_gmt":"2016-07-18T03:32:50","guid":{"rendered":"http:\/\/network.ee.tsinghua.edu.cn\/niulab\/?p=2906"},"modified":"2016-07-18T03:37:28","modified_gmt":"2016-07-18T03:37:28","slug":"on-the-online-minimization-of-completion-time-in-an-energy-harvesting-system","status":"publish","type":"post","link":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/?p=2906","title":{"rendered":"On the Online Minimization of Completion Time in an Energy Harvesting System"},"content":{"rendered":"<p><span class=\"paper_subtitle\">LANGUAGE<\/span> English<\/p>\n<p><span class=\"paper_subtitle\">SOURCE<\/span> <strong><em>WiOpt 2016, <\/em><\/strong>Phoenix, May 9-13, 2016<\/p>\n<p><span class=\"paper_subtitle\">Published Date<\/span>:2016-5<\/p>\n<p><span class=\"paper_subtitle\">ABSTRACT<\/span><\/p>\n<p>This paper considers a single-transmitter energy<br \/>\nharvesting system and looks into the problem of completion<br \/>\ntime minimization from the worst-case point of view. In offline<br \/>\nstudy, an optimal algorithm [1] is given to yield the minimum<br \/>\ncompletion time of transmission. However, for online algorithms,<br \/>\nthe randomness of future energy arrivals adds to the difficulty<br \/>\nof scheduling, thus the offline minimum completion time cannot<br \/>\nalways be reached. This leads to the question \u201cWhat is the<br \/>\ndeterministic performance bound of online algorithms compared<br \/>\nto the offline optimum\u201d. By a game-theoretic method, this paper<br \/>\nshows that with an infinite-sized battery, there exist several<br \/>\nalgorithms that guarantee a completion time no more than the<br \/>\ntwice of its offline counterpart for all possible energy arrivals,<br \/>\nand more importantly that the ratio of two cannot be further<br \/>\nreduced. This property is of great significance especially when<br \/>\nreliability is valued in the system.<\/p>\n","protected":false},"excerpt":{"rendered":"<p><a href=\"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/wp-content\/uploads\/2016\/07\/\u90d1\u7199WiOpt2016.pdf\" target=\"_blank\"><img loading=\"lazy\" decoding=\"async\" class=\"alignleft size-full wp-image-117\" title=\"pdf\" src=\"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/wp-content\/uploads\/2010\/08\/pdf.gif\"alt=\"\" width=\"95\" height=\"50\" \/><\/a>\tXi Zheng, Sheng Zhou and Zhisheng Niu, <span class=\"papertitle\">On the Online Minimization of Completion Time in an Energy Harvesting System\uff0c<\/span>, <span class=\"papersource\">WiOpt 2016, Phoenix, May 9-13, 2016<\/span><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[7],"tags":[99],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=\/wp\/v2\/posts\/2906"}],"collection":[{"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2906"}],"version-history":[{"count":4,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=\/wp\/v2\/posts\/2906\/revisions"}],"predecessor-version":[{"id":2915,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=\/wp\/v2\/posts\/2906\/revisions\/2915"}],"wp:attachment":[{"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2906"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2906"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2906"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}