Some Heuristics for the 2-Poset Cover Problem
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 pro...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | text |
| Published: |
Archīum Ateneo
2014
|
| Subjects: | |
| Online Access: | https://archium.ateneo.edu/discs-faculty-pubs/82 https://www.researchgate.net/publication/282154675_Some_Heuristics_for_the_2-Poset_Cover_Problem |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Ateneo De Manila University |
| Summary: | 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. |
|---|