We investigate the approximability of minimum and maximum linear ordering problems (MIN-LOP and MAX-LOP) and related feedback set problems such as maximum weight acyclic subdiagraph (MAX-W-SUBDAG), minimum weight feedback arc/vertex set (MIN-W-FAS/ MIN-W-FVS) and a generalization of the latter called MIN-Subset-FAS/MIN-Subset-FVS. MAX-LOP and the other problems have been studied by many researchers but, though MIN-LOP arises in many practical contexts, it appears that it has not been studied before. In this paper, we ΓΏrst note that these minimization (respectively, maximization) problems are equivalent with respect to strict reduction and so have the same approximability properties. While MAX-LOP is APX-complete, MIN-LOP is only APX-hard. We conjecture that MIN-LOP is not in APX, unless P = NP. We obtain a result connecting extreme points of linear ordering polytope with approximability of MIN-LOP via LP-relaxation which seems to suggest that constant factor approximability of MIN-LOP may not be obtainable via this method. We also prove that (a) MIN-Subset-FAS cannot be approximated within a factor (1 -) log n, for any ΒΏ 0, unless NP β DTIME(n log log n ), and (b) MIN-W-k-FAS, a generalization of MIN-LOP, is NPO-complete. We then show that t -MIN-LOP (respectively, t -MAX-LOP), in which the weight matrix satisΓΏes a parametrized version of a stronger form of triangle inequality, with parameter t β (0; 2], is approximable within a factor (2 + t)=2t (respectively, 4=(2 + t)). We also show that these restricted versions are in PO i t = 2 and are not in PTAS for t β (0; 2), unless P = NP.