Displaying similar documents to “Complexity of partial inverse assignment problem and partial inverse cut problem”

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 partial inverse minimum cut problem with -norm is strongly NP-hard

Elisabeth Gassner (2010)

RAIRO - Operations Research

Similarity:

The partial inverse minimum cut problem is to minimally modify the capacities of a digraph such that there exists a minimum cut with respect to the new capacities that contains all arcs of a prespecified set. Orlin showed that the problem is strongly NP-hard if the amount of modification is measured by the weighted -norm. We prove that the problem remains hard for the unweighted case and show that the NP-hardness proof of Yang [ (2001) 117–126]...

Towards optimal formwork pairing on construction sites

Thierry Benoist (2007)

RAIRO - Operations Research

Similarity:

Minimizing shutterings assembling time on construction sites can yield significant savings in labor costs and crane moves. It requires solving a pairing problem that optimizes the ability for the crane to move chains of shutterings as a whole when they can be later reused together to frame another wall of the site. In this paper, we show that this problem is NP-hard in the strong sense as well as both its multiflow and ordering aspects. We also introduce a linear relaxation that computes...

Note on the core matrix partial ordering

Jacek Mielniczuk (2011)

Discussiones Mathematicae Probability and Statistics

Similarity:

Complementing the work of Baksalary and Trenkler [2], we announce some results characterizing the core matrix partial ordering.