Computer-Aided Way to Prove Theorems in Scheduling

Autor:	I. D. Tchernykh, Sergey V. Sevastianov
Rok vydání:	1998
Předmět:	Mathematical optimization Computer science Computer-aided Approximation algorithm Time complexity Scheduling (computing)
Zdroj:	Algorithms — ESA’ 98 ISBN: 9783540648482 ESA
DOI:	10.1007/3-540-68530-8_42
Popis:	For two scheduling problems (O3||Cmax and AL3||Cmax) tight bounds of the optima localization intervals are found in terms of lower bounds (C and C, respectively) computable in linear time. The main part of the proof was made with an aid of computer. As a by-product, we obtain linear-time approximation algorithms for solving these problems with worst-case performance ratios 4/3 and 5/3, respectively.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::83a89de5e707174255da4cba4fee4c62 https://doi.org/10.1007/3-540-68530-8_42 Zobrazit plný text záznamu