A lower bound on deterministic online algorithms for scheduling on related machines without preemption

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F12%3A00386905" target="_blank" >RIV/67985840:_____/12:00386905 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1007/978-3-642-29116-6_9" target="_blank" >http://dx.doi.org/10.1007/978-3-642-29116-6_9</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-642-29116-6_9" target="_blank" >10.1007/978-3-642-29116-6_9</a>

Result language

angličtina

Original language name

A lower bound on deterministic online algorithms for scheduling on related machines without preemption

Original language description

We prove a new lower bound of 2.564 on deterministic online algorithms for makespan scheduling on related machines (without preemptions). Previous lower bound was 2.438 by Berman et al. We use an analytical bound on maximal frequency of scheduling jobs instead of the combinatorial bound obtained by computer based search through the graph of possible states of an algorithm in the previous work.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2012

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Approximation and online algorithms

ISBN

978-3-642-29115-9

ISSN

—

e-ISSN

—

Number of pages

7

Pages from-to

102-108

Publisher name

Springer

Place of publication

Heidelberg

Event location

Saarbrücken

Event date

Sep 8, 2011

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—