Submodular functions on diamonds
2008 (English)Conference paper (Refereed)
Let V be a finite set. A set function f : 2V → R is said to be submodular if for all A,B ⊆ V we have f(A∪B)+f(A∩B) ≤ f(A)+f(B). Submodular set functions have been studied extensively and examples of such functions include the cut function of graphs and the rank function of matroids. Given an oracle which computes f, it is known that the minimum of f can be found in time polynomialin |V |. This was first established by Gr ¨otschel et al. [Combinatorica, 1 (1989), pp. 169–197]. We are interested in a generalised notion of submodular functions. The main motivation for us to do this is because the generalised concept seems to play an important role in the complexity of the maximumconstraint satisfaction problem (see, Cohen et al. [Discrete Appl. Math., 149 (2005), pp. 53–72]).
Place, publisher, year, edition, pages
Coventry: U. Warwick , 2008. , 53-54 p.53-54 p.
IdentifiersURN: urn:nbn:se:liu:diva-44308Local ID: 76221OAI: oai:DiVA.org:liu-44308DiVA: diva2:265170
InternationalSymposium on Combinatorial Optimization, 16-19 March 2008, University of Warwick, Coventry, UK