The database of interval orders difficult for the jump number minimizing algorithms

• Autorzy: Krysztowiak P.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

database; interval order; interface; posets; approximation algorithms

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2011
• Tom: Vol. 11, no. 1
• Strony: 15--22
• Opis fizyczny: Bibliogr. 7 poz., rys.

Twórcy

autor

Krysztowiak P.

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, 87-100 Toruń, Poland

Bibliografia

• [1] Felsner S., A 3/2-approximation algorithm for the jump number of interval orders, Order 6 (1990): 325.
• [2] Sysło M.M., The jump number problem on interval orders: A 3/2 approximation algorithm, Discrete Mathematics 144 (1995): 119.
• [3] Mitas J., Tackling the jump number of interval orders, Order 8 (1991): 115.
• [4] Arnim A., Higuera C., Computing the jump number on semi-orders is polynomial, Discrete Applied Mathematics 51 (1994): 219.
• [5] Fishburn P.C., Interval orders and interval graphs. A study of partially ordered sets, Wiley, New York (1985).
• [6] Sysło M.M., An algorithm for solving the jump number problem, Discrete Mathematics 72 (1988): 337.
• [7] Krysztowiak P., http://www.mat.umk.pl/~nb/