The problem of counting the linear extensions of a given partial order consists of finding (counting) all the possible ways that we can extend the partial order to a total order that preserves the original partial order. It is an important problem with various applications in Artificial Intelligence and Machine Learning, for example in partial-order plans and in learning graphical models. It is a well known #P-complete problem; the fastest known algorithms are based on dynamic programming and require exponential time and space. Nevertheless, if we only need an approximate counting attained with a probability of success, then the problem admits a polynomial-time solution for all posets using Markov chain Monte Carlo (MCMC) methods. This project aims to implement new randomized methods to approximate the number of linear extensions based on volume approximation.

Organization

Student

Vaibhav Thakkar

Mentors

  • Apostolos Chalkis
  • Vissarion Fisikopoulos
  • Elias
close

2021