Back to Search
Start Over
Approximation and Computational Complexity of Some Hammock Variations of the Poset Cover Problem.
- Source :
-
INGENIARE - Revista Chilena de Ingeniería . Mar2020, Vol. 28 Issue 1, p227-237. 11p. - Publication Year :
- 2020
-
Abstract
- The Hammock(2, 2 ,..., 2/k)-Poset Cover Problem is a variation of the Poset Cover Problem with the same input - set {L1, L2, ..., Lm} of linear orders over the set {1, 2, ..., n}, but the solution is restricted to a set of simple hammock(2, 2 ,..., 2/k) 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(2, 2 ,..., 2/k)-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]
Details
- Language :
- Spanish
- ISSN :
- 07183291
- Volume :
- 28
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- INGENIARE - Revista Chilena de IngenierĂa
- Publication Type :
- Academic Journal
- Accession number :
- 143379501