Document Type
Article
Publication Date
3-2020
Abstract
The Hammock(βπ, π , β¦ , π / π )-Poset Cover Problem is a variation of the Poset Cover Problem with the same input β set {π³π, π³π, β¦ , π³π} of linear orders over the set {π, π, β¦ ,π}, but the solution is restricted to a set of simple hammock(πβ, π , β¦ , π / π ) posets. The problem is NP-Hard when π β₯ π but is in π· when π = π. The computational complexity of the problem when π = π is not yet known. In this paper, we determine the approximation complexity of the cases that have been shown to be NP-Hard. We show that the Hammock(πβ, π , β¦ , π / π )-Poset Cover Problem is in APX and, in particular, (π + π/π π )-approximable, for π β₯ π. On the other hand, we also explore the computational complexity for the case where π = π [Hammock(2,2)-Poset Cover Problem]. We show that it is in π· when the transposition graph of the input set of linear orders is rectangular
Recommended Citation
Ordanel, I. D., Fernandez, P. L. Jr., Juayong, R. A. B., & Adorna, H. N. (2020). Approximation and computational complexity of some Hammock variations of the Poset Cover Problem. Philippine Journal of Science, 149(1), 201β211. https://philjournalsci.dost.gov.ph/publication/regular-issues/past-issues/57-next-issue/1152-philippine-journal-of-science-vol-149-no-1-march-2020
