article · 2007

A Simple Extreme Subsets Algorithm for Submodular and Posi-modular Set Functions

Cited by 1Abstract and details only

Abstract

Abstract: Let f be a set function on a finite set V.Apair{u, v} ⊆V is called flat in f if f(X) ≥ minx∈X f({x}) holds for all subsets X ⊆ V with |X ∩{u, v} | =1. A subset X ⊆ V is called an extreme subset of f if f(Y)&gt;f(X) holds for all nonempty and proper subsets Y of X. In this paper, we first define a minimum degree ordering (MD ordering) of V, and show that the last two elements in an MD ordering give a flat pair of f if f is symmetric and crossing submodular. Based on this, we then give a simple O(|V | 3)-oracle time algorithm for computing all extreme subsets of a set function g if g is symmetric and crossing submodular or intersecting submodular and posi-modular.

Cite this paper

APA 7

Nagamochi, H. (2007). A Simple Extreme Subsets Algorithm for Submodular and Posi-modular Set Functions.

MLA 9

Nagamochi, Hiroshi. “A Simple Extreme Subsets Algorithm for Submodular and Posi-modular Set Functions.” 2007.

Chicago

Nagamochi, Hiroshi. 2007. “A Simple Extreme Subsets Algorithm for Submodular and Posi-modular Set Functions.”

Harvard

Nagamochi, H. (2007) ‘A Simple Extreme Subsets Algorithm for Submodular and Posi-modular Set Functions’.

BibTeX

@article{nagamochi2007simple,
  title = {{A Simple Extreme Subsets Algorithm for Submodular and Posi-modular Set Functions}},
  author = {Nagamochi, Hiroshi},
  year = {2007}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.