Submodular containment is hard, even for networks

Submodular containment is hard, even for networks

0.00 Avg rating0 Votes
Article ID: iaor2001965
Volume: 19
Issue: 2
Start Page Number: 95
End Page Number: 99
Publication Date: Aug 1996
Journal: Operations Research Letters
Authors:
Abstract:

Suppose that we have two submodular base polyhedra in the same space. What is the complexity of deciding if one is contained in the other? This paper shows that this is strongly co-NP-complete even in the case that the two base polyhedra are defined by cut capacity functions coming from two networks on the same set of nodes. This implies that (unless P = NP) there can be no polynomial algorithm for a problem in dynamic games that asks for a min-cost network that can ‘counter’ any move in a given network.

Reviews

Required fields are marked *. Your email address will not be published.