Contributor
reyan_ahmed

Counting linear extensions with volume computation


Mentors
Vissarion Fisikopoulos, Apostolos Chalkis, Vangelis Anagnostopoulos
Organization
GeomScale
Technologies
c++
Topics
linear programming, approximation algorithms
In this project, we will implement different algorithms to count linear extensions approximately. In the problem of counting the linear extensions, we are given an initial partial order $P$. The objective of this problem is to generate all orders (linear extensions) that preserve $P$. However, there can be an exponential number of such orders. Hence the running time to count the number of total orders that preserves $P$ will be exponential. To get rid of exponential computation, we will approximate the number of linear extensions using volume computation. We will develop different approximation algorithms and compare their performance.