00000caa a22000003i 4500 UP-1685594773862408697 Buklod 20210408103836.0 m | | ta 210408s2020 xx r |||| u|eng d (iLib)UPBAG-00039679858 STII-DOST BAG rda eng ARTICLE-3027 Ordanel, Ivy D. author. Approximation and computational complexity of some hammock variations of the poset cover problem by Ivy D. Ordanel, Proceso L. Fernandez Jr., Richelle Ann B. Juayong, and Henry N. Adorna. 2020. pages 201-211 illustrations 26 cm text rdacontent unmediated rdamedia volume rdacarrier Includes bibliographical references (page 211) 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 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. (Author's abstract) Algorithm. Approximation. Complexity. Poset. Fernandez Jr., Proceso L. author. Juayong, Richelle Ann B. author. Adorna, Henry N. author. The Philippine Journal of Science Vol. 149, no. 1, March 2020. Request full-text access via UPB University Library through https://forms.gle/KZjBv7aRtY6jiL5E9 (viewed 08 April 2021) FI UPBAG UPBAG-MAIN ARTICLE-3027 Analytics