On approximability of linear ordering and related NP-optimization problems on graphs
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 first 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 , for any ?>0, unless , 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 satisfies 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 iff t=2 and are not in PTAS for t?(0,2), unless P=NP.
linear ordering problem feedback set problem parametrized triangle inequality npo problem apx-completeness approximation algorithm