A historical note on the complexity of scheduling problems

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10456176" target="_blank" >RIV/00216208:11320/23:10456176 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Wohd4kNAq6" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Wohd4kNAq6</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.orl.2022.11.006" target="_blank" >10.1016/j.orl.2022.11.006</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A historical note on the complexity of scheduling problems

Popis výsledku v původním jazyce

In 1972 E.M. Livshits and V.I. Rublinetsky published a paper in Russian, in which they presented lineartime reductions of the partition problem to a number of scheduling problems. Unaware of complexity theory, they argued that, since partition is not known to have a simple algorithm, one cannot expect to find simple algorithms for these scheduling problems either. Their work did not go completely unnoticed, but it received little recognition. We describe the approach and review the results.(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).

Název v anglickém jazyce

A historical note on the complexity of scheduling problems

Popis výsledku anglicky

In 1972 E.M. Livshits and V.I. Rublinetsky published a paper in Russian, in which they presented lineartime reductions of the partition problem to a number of scheduling problems. Unaware of complexity theory, they argued that, since partition is not known to have a simple algorithm, one cannot expect to find simple algorithms for these scheduling problems either. Their work did not go completely unnoticed, but it received little recognition. We describe the approach and review the results.(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2023

Kód důvěrnosti údajů

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

Název periodika

Operations Research Letters

ISSN

0167-6377

e-ISSN

1872-7468

Svazek periodika

51

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

2

Strana od-do

1-2

Kód UT WoS článku

000908041000001

EID výsledku v databázi Scopus

2-s2.0-85142904061