Approximations of arbitrary relations by partial orders

The problem of optimal quantitative approximation of an arbitrary binary relation by a partial order is discussed and some solutions are provided. It is shown that even for a very simple quantitative measure the problem is NP-hard. Some quantitative metrics are also applied for known property-driven approximations by partial orders. Some relationship to Rough Sets is discussed.