1. Approximation and Computational Complexity of Some Hammock Variations of the Poset Cover Problem.
- Author
-
Ordanel, Ivy D., Fernandez Jr., Proceso L., Juayong, Richelle Ann B., and Adorna, Henry N.
- Subjects
- *
HAMMOCKS , *NP-hard problems , *LINEAR orderings , *ORDERED sets , *COMPUTATIONAL complexity - 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 {L1, L2, ...,L3}, but the solution is restricted to a set of simple hammock (...) posets. The problem is NP-Hard when K ≥ 3 but is in P when k = 1. The computational complexity of the problem when k = 2 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, (1 + 1/2k)-approximable, for k ≥ 3. On the other hand, we also explore the computational complexity for the case where k = 2 [Hammock(2,2)-Poset Cover Problem]. We show that it is in P when the transposition graph of the input set of linear orders is rectangular. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF