Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: interval order

Sortuj według:

Ogranicz wyniki do:

Operational Semantics, Interval Orders and Sequences of Antichains

Janicki Ryszard, Koutny Maciej

Fundamenta Informaticae

2019

Vol. 169, nr 1-2

31--55

A representation of interval orders by sequences of antichains is discussed, and its relationship to the Fishburn’s representation by sequences of the beginnings and endings of domain elements is analysed in detail. Moreover, an operational semantics based on sequences of maximal antichains is proposed and investigated for a general class of safe Petri nets with context arcs.

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

Krysztowiak P.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

2011

Vol. 11, no. 1

15-22

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.