Narrow Results

The Poset Cover Problem is the problem where the input is a set of linear orders and the goal is to find a minimum set of posets that generates exactly all the given linear orders. The computational complexity of the decision version of the problem is already known; it is NP-Complete. However, the approximation complexity or approximability of the problem is not yet known.

In this paper, we show the approximability of two simple variations of the problem where the poset being considered are Hammock posets having hammocks of size 2. The first is Hammock(2, 2, 2)-Poset Cover Problem where the solution is a set of Hammock posets with 3 hammocks of size 2. This problem has been shown to be NP-Complete and in this paper we show that it is 2.7-approximable. The second variation which is more general than the first one considers Hammock posets with any number of hammocks of size 2 and we show that it is $H(n)-\frac{196}{300}-\text{approximable}$.