Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ https://www.research...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
https://www.research-collectio...
Part of book or chapter of book
Data sources: UnpayWall
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
https://doi.org/10.1007/978-3-...
Part of book or chapter of book . 2015 . Peer-reviewed
Data sources: Crossref
versions View all 3 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Online Makespan Scheduling with Sublinear Advice

Authors: Dohrau, Jérôme;

Online Makespan Scheduling with Sublinear Advice

Abstract

Online algorithms are of importance for many practical applications. Typical examples involve scheduling and routing algorithms employed in operating systems and computer networks. Beside their practical signicance, online algorithms are extensively studied from a theoretical point of view. Due to the nature of online problems, these algorithms fail to be optimal in general. The quality of their output is usually measured by the so called competitive ratio. A few years ago, another measure, the advice complexity, has been introduced to give a deeper insight into the nature of an online problem and to capture the essential information contained in the instances of the problem.The makespan scheduling problem is a generic scheduling problem where the task is to schedule jobs with dierent processing times on identical machines. The objective is to distribute the processing times as evenly as possible among the machines. This is why this problem is sometimes referred to as the load balancing problem. When considering the online version of the problem, the jobs arrive gradually and have to be assigned to a machine immediately at their arrival. In the work at hand, we study the advice complexity of the online makespan scheduling problem restricted to two machines.For this problem it proves to be that already little advice helps a great deal to improve the competitive ratio in comparison to purely deterministic online algorithms. Therefore, this work mainly focuses on upper bounds. First, we give linear upper and lower bounds on the advice complexity for optimal algorithms with advice, with the bounds being tight up to one bit. Afterwards, we introduce a very simple online algorithm with logarithmic advice complexity and a competitive ratio of 4 3 . We also show that with a more involved strategy an online algorithm can get arbitrarily close to this competitive ratio using only a constant number of advice bits. As the main result we prove that even a constant number of advice bits is sucient to achieve an almost optimal solution.

Related Organizations
Keywords

Data processing, computer science, PROZESSVERWALTUNG + PROZESSMANAGEMENT (BETRIEBSSYSTEME), SCHEDULING (BETRIEBSSYSTEME), SCHEDULING (OPERATING SYSTEMS), SCHEDULING (OPERATING SYSTEMS); PROCESS MANAGEMENT (OPERATING SYSTEMS); SCHEDULING (BETRIEBSSYSTEME); PROGRAMS AND ALGORITHMS FOR THE SOLUTION OF SPECIAL PROBLEMS; PROZESSVERWALTUNG + PROZESSMANAGEMENT (BETRIEBSSYSTEME); PROGRAMME UND ALGORITHMEN ZUR LÖSUNG SPEZIELLER PROBLEME, PROGRAMS AND ALGORITHMS FOR THE SOLUTION OF SPECIAL PROBLEMS, PROCESS MANAGEMENT (OPERATING SYSTEMS), PROGRAMME UND ALGORITHMEN ZUR LÖSUNG SPEZIELLER PROBLEME, info:eu-repo/classification/ddc/004

  • BIP!
    Impact byBIP!
    citations
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    11
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Top 10%
Powered by OpenAIRE graph
Found an issue? Give us feedback
citations
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
11
Top 10%
Average
Top 10%
Green