On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem
Sounaka Mishra, Kripasindhu Sikdar (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
We study hardness of approximating several minimaximal and maximinimal NP-optimization problems related to the minimum linear ordering problem (MINLOP). MINLOP is to find a minimum weight acyclic tournament in a given arc-weighted complete digraph. MINLOP is APX-hard but its unweighted version is polynomial time solvable. We prove that MIN-MAX-SUBDAG problem, which is a generalization of MINLOP and requires to find a minimum cardinality maximal acyclic subdigraph of a given digraph,...