Duality between quasi-concave functions and monotone linkage functions

Details Duality between quasi-concave functions and monotone linkage functions Duality between quasi-concave functions and monotone linkage functions

2008-08-24

arxiv.org/abs/0808.3244v1

Mathematics

Combinatorics

12 pages, 2 figures

Scientific paper

A function $F$ defined on all subsets of a finite ground set $E$ is quasi-concave if $F(X\cup Y)\geq\min\{F(X),F(Y)\}$ for all $X,Y\subset E$. Quasi-concave functions arise in many fields of mathematics and computer science such as social choice, theory of graph, data mining, clustering and other fields. The maximization of quasi-concave function takes, in general, exponential time. However, if a quasi-concave function is defined by associated monotone linkage function then it can be optimized by the greedy type algorithm in a polynomial time. Quasi-concave functions defined as minimum values of monotone linkage functions were considered on antimatroids, where the correspondence between quasi-concave and bottleneck functions was shown (Kempner & Levit, 2003). The goal of this paper is to analyze quasi-concave functions on different families of sets and to investigate their relationships with monotone linkage functions.

Affiliated with

Also associated with

No associations

Rating

Duality between quasi-concave functions and monotone linkage functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Duality between quasi-concave functions and monotone linkage functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Duality between quasi-concave functions and monotone linkage functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-535604