liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Submodular functions on diamonds
Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
2008 (English)Conference paper (Refereed)
Abstract [en]

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.
National Category
Computer Science
URN: urn:nbn:se:liu:diva-44308Local ID: 76221OAI: diva2:265170
InternationalSymposium on Combinatorial Optimization, 16-19 March 2008, University of Warwick, Coventry, UK
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2009-11-13Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Kuivinen, Fredrik
By organisation
The Institute of TechnologyTCSLAB - Theoretical Computer Science Laboratory
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 12 hits
ReferencesLink to record
Permanent link

Direct link