An colleague recently came to me with a problem concerning the scheduling of tasks in the presence of constraints (of the kind: task $x$ can't begin until task $y$ has been completed). It turned out that the problem was equivalent to that of computing the width (cardinality of maximum antichain) of a poset.

I know that the problem of computing the width of a poset can be translated into that of finding the size of a maximum matching in a certain bipartite graph, which in turn can be found using the Hopcroft–Karp algorithm, in time $O(n^{5/2})$ (where $n$ is the number of elements in the poset).

To me, that's ``polynomial time; end of story''; but to my colleague, who is working with actual data sets, the degree of the polynomial is very important.

My question: what is the current state-of-that art in terms of algorithms for computing the width of a general poset?