Complexity of Partial Inverse Assignment Problem and Partial Inverse Cut Problem

DOI10.1051/ro:2001106zbMath0993.90068OpenAlexW2131390263MaRDI QIDQ2765604

Xiao-guang Yang

Publication date: 2001

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=RO_2001__35_1_117_0

zbMATH Keywords

NP-hardpartial inverse assignment problempartial inverse minimum cut problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (13)

Algorithm for constraint partial inverse matroid problem with weight increase forbidden ⋮ Algorithms for the partial inverse matroid problem in which weights can only be increased ⋮ Capacitated partial inverse maximum spanning tree under the weighted \(l_{\infty }\)-norm ⋮ Partial inverse assignment problems under \(l_{1}\) norm ⋮ Approximation algorithms for capacitated partial inverse maximum spanning tree problem ⋮ Partial inverse min-max spanning tree problem under the weighted bottleneck Hamming distance ⋮ A branch-and-bound algorithm for instrumental variable quantile regression ⋮ Branch-and-bound algorithms for the partial inverse mixed integer linear programming problem ⋮ Partial inverse maximum spanning tree in which weight can only be decreased under \(l_p\)-norm ⋮ The partial inverse minimum cut problem withL₁-norm is strongly NP-hard ⋮ Capacitated partial inverse maximum spanning tree under the weighted Hamming distance ⋮ General restricted inverse assignment problems under \(l_1\) and \(l_{\infty}\) norms ⋮ Partial inverse maximum spanning tree problem under the Chebyshev norm

Cites Work

• Inverse problem of minimum cuts
• Inverse polymatroidal flow problem
• Inverse problems of submodular functions on digraphs
• Inverse maximum flow and minimum cut problems
• Combinatorial algorithms for inverse network flow problems
• A network flow method for solving some inverse combinatorial optimization problems
• Unnamed Item

This page was built for publication: Complexity of Partial Inverse Assignment Problem and Partial Inverse Cut Problem