Anzeige
Erschienen in:
1998 | OriginalPaper | Buchkapitel
Computer-Aided Way to Prove Theorems in Scheduling
verfasst von : S. V. Sevastianov, I. D. Tchernykh
Erschienen in: Algorithms — ESA’ 98
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
For two scheduling problems (O3∥Cmax and AL3∥Cmax) tight bounds of the optima localization intervals are found in terms of lower bounds ($$ \tilde C $$ and $$ \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{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.