Back to Search
Start Over
Approximation and Computational Complexity of Some Hammock Variations of the Poset Cover Problem.
- Source :
- Philippine Journal of Science; Mar2020, Vol. 149 Issue 1, p227-237, 11p
- Publication Year :
- 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 {L<subscript>1</subscript>, L<subscript>2</subscript>, ...,L<subscript>3</subscript>}, 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/2<superscript>k</superscript>)-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]
- Subjects :
- HAMMOCKS
NP-hard problems
LINEAR orderings
ORDERED sets
COMPUTATIONAL complexity
Subjects
Details
- Language :
- English
- ISSN :
- 00317683
- Volume :
- 149
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- Philippine Journal of Science
- Publication Type :
- Academic Journal
- Accession number :
- 143392984
- Full Text :
- https://doi.org/10.56899/149.01.20