- Tytuł:
- The database of interval orders difficult for the jump number minimizing algorithms
- Autorzy:
- Krysztowiak, P.
- Powiązania:
- https://bibliotekanauki.pl/articles/106212.pdf
- Data publikacji:
- 2011
- Wydawca:
- Uniwersytet Marii Curie-Skłodowskiej. Wydawnictwo Uniwersytetu Marii Curie-Skłodowskiej
- Tematy:
-
database
interval order
interface
posets
approximation algorithms - Opis:
- The problems of scheduling jobs on a single machine subject to precedence constraints can often be modelled as the jump number problem for posets, where a linear extension of a given partial order is to be found which minimizes the number of noncomparabilities. In this paper, we are investigating a restricted class of posets, called interval orders, admitting approximation algorithms for the jump number problem, in which the problem remains NP-complete. We have implemented three known approximation algorithms for this problem, all of which are guaranteed to produce solutions that are at most 50% worse than the optimal ones. More importantly, we have performed an exhaustive search for particularly hard interval orders, which enforce the algorithms to generate orderings which are exactly 50% worse than the optimal linear extensions. The main purpose of this paper is to present the database of those problematic posets.
- Źródło:
-
Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica; 2011, 11, 1; 15-22
1732-1360
2083-3628 - Pojawia się w:
- Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
- Dostawca treści:
- Biblioteka Nauki
Artykuł