Displaying similar documents to “The partial inverse minimum cut problem with L1-norm is strongly NP-hard”

Complexity of partial inverse assignment problem and partial inverse cut problem

Xiaoguang Yang (2001)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

For a given partial solution, the partial inverse problem is to modify the coefficients such that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum. In this paper, we show that the partial inverse assignment problem and the partial inverse minimum cut problem are NP-hard if there are bound constraints on the changes of coefficients.

Complexity of Partial Inverse Assignment Problem and Partial Inverse Cut Problem

Xiaoguang Yang (2010)

RAIRO - Operations Research

Similarity:

For a given partial solution, the partial inverse problem is to modify the coefficients such that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum. In this paper, we show that the partial inverse assignment problem and the partial inverse minimum cut problem are NP-hard if there are bound constraints on the changes of coefficients.

The inverse maximum flow problem considering norm

Adrian Deaconu (2008)

RAIRO - Operations Research

Similarity:

The problem is to modify the capacities of the arcs from a network so that a given feasible flow becomes a maximum flow and the maximum change of the capacities on arcs is minimum. A very fast ⋅log()) time complexity algorithm for solving this problem is presented, where is the number of arcs and is the number of nodes of the network. The case when both, lower and upper bounds of the flow can be modified so that the given feasible flow becomes a maximum flow is also discussed. The...

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,...