Proceedings of the Workshop on Computation: Theory and Practice (WCTP 2023)

<Previous Article In Volume
Next Article In Volume>

Two Heuristics for the Tree Poset Cover Problem

Authors
Willie N. Coronel1, *, Joshua Relucio1, Ivy D. Ordanel1, Richelle Ann B. Juayong2
1Algorithms and Complexity Laboratory, Department of Computer Science, University of the Philippines Diliman, Quezon City, Philippines
2Service Science and Software Engineering Laboratory, Department of Computer Science, University of the Philippines Diliman, Quezon City, Philippines
*Corresponding author. Email: wncoronel@up.edu.ph
Corresponding Author
Willie N. Coronel
Available Online 29 February 2024.
DOI
10.2991/978-94-6463-388-7_2How to use a DOI?
Keywords
optimization problem; partially ordered sets; heuristics; approximation
Abstract

The Poset Cover Problem aims to find a minimum set of posets that cover a given input set of linear orders. This problem has practical applications in data mining, particularly in constructing directed networks from sequential data. The decision version of the problem is known to be NP-hard. In this study, we focus on a variant called the Tree Poset Cover Problem, which requires identifying a minimum set of tree posets needed to cover a given input set of linear orders. We propose two polynomial-time heuristics, namely Heuristic 1 and Heuristic 2. Our investigation demonstrates that both heuristics consistently produce feasible solutions and can be classified as approximation algorithms. Furthermore, we empirically evaluate the performance of Heuristic 1 and Heuristic 2 using four datasets.

Copyright
© 2024 The Author(s)
Open Access
Open Access This chapter is licensed under the terms of the Creative Commons Attribution-NonCommercial 4.0 International License (http://creativecommons.org/licenses/by-nc/4.0/), which permits any noncommercial use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

Download article (PDF)

<Previous Article In Volume
Next Article In Volume>
Volume Title
Proceedings of the Workshop on Computation: Theory and Practice (WCTP 2023)
Series
Atlantis Highlights in Computer Sciences
Publication Date
29 February 2024
ISBN
10.2991/978-94-6463-388-7_2
ISSN
2589-4900
DOI
10.2991/978-94-6463-388-7_2How to use a DOI?
Copyright
© 2024 The Author(s)
Open Access
Open Access This chapter is licensed under the terms of the Creative Commons Attribution-NonCommercial 4.0 International License (http://creativecommons.org/licenses/by-nc/4.0/), which permits any noncommercial use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

Cite this article

risenwbib
TY  - CONF
AU  - Willie N. Coronel
AU  - Joshua Relucio
AU  - Ivy D. Ordanel
AU  - Richelle Ann B. Juayong
PY  - 2024
DA  - 2024/02/29
TI  - Two Heuristics for the Tree Poset Cover Problem
BT  - Proceedings of the Workshop on Computation: Theory and Practice (WCTP 2023)
PB  - Atlantis Press
SP  - 7
EP  - 23
SN  - 2589-4900
UR  - https://doi.org/10.2991/978-94-6463-388-7_2
DO  - 10.2991/978-94-6463-388-7_2
ID  - Coronel2024
ER  -