Minimizing the sum cost in linear extensions of a poset

A linear extension problem is defined as follows: Given a poset P=(E,≤), we want to find a linear order L such that x≤y in L whenever x≤yin P. In this paper, we assign each pair of elements x,y∈E with a cost, and to find a linear extension of P with the minimum sum cost. For the general case, it is NP‐complete and we present a greedy approximation algorithm which can be finished in polynomial time. Also we consider a special case which can be solved in polynomial time.