Some Heuristics for the 2-Poset Cover Problem

• Main Authors: Fernandez, Proceso L, Jr, Sanchez, Gabriel Alberto A, Vergara, John Paul
• Format: text
• Published: Archīum Ateneo 2014
• Subjects: Poset Cover; Heuristics; Computer Sciences; Theory and Algorithms
• Online Access: https://archium.ateneo.edu/discs-faculty-pubs/82; https://www.researchgate.net/publication/282154675_Some_Heuristics_for_the_2-Poset_Cover_Problem
• Institution: Ateneo De Manila University

Posets are abstract models that may be considered as generating a set of linear orders, which are permutations on some base set. The problem of determining a minimum set of posets that can exactly generate a specified input set of linear orders is referred to as the Poset Cover Problem, and this problem is NP-Hard in the general case. In this study, we investigate a constrained version of the problem, the 2-Poset Cover Problem, where there are exactly 2 posets that can generate a given input. We develop some heuristics for this and examine some properties related to the problem. Our heuristics are able to provide the correct solutions for a significant majority of the tested random instances. From the instances where the heuristics have failed, some insights were derived which may be helpful in determining the correct complexity class to which the 2-Poset Cover Problem belongs.