Duality between quasi-concave functions and monotone linkage functions

DOI10.1016/J.DISC.2009.09.001MaRDI QIDQ712240zbMATH OpenOpenAlexFDO

Authors Yulia Kempner, Vadim E. Levit

Publication date 28 October 2010

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0808.3244

zbMATH Keywords

greedy algorithmconvex geometryquasi-concave functionmonotone linkage function

Mathematics Subject Classification ID

Combinatorial aspects of finite geometries (05B25) General theory of linear incidence geometry and projective geometries (51A05) Fundamental topics (basic mathematics, methodology; applicable to economics in general) (91B02) Extremal set theory (05D05)

Abstract: A function $F$ defined on all subsets of a finite ground set $E$ is quasi-concave if $F(XcupY)geqminF(X),F(Y)$ for all $X,YsubsetE$. 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.

Recommendations

• Quasilinearity of some functionals associated with monotonic convex functions
• A relationship between quasimonotone and monotone bifunctions
• Quasimonotonicity and functional inequalities
• scientific article; zbMATH DE number 823378
• Complete monotone quasiconcave duality
• Duality theorems for convex and quasiconvex set functions
• scientific article; zbMATH DE number 1822202
• Quasimonotonicity as a Tool for Differential and Functional Inequalities
• Dual representation of monotone convex functions on 𝐿⁰
• scientific article; zbMATH DE number 5781369

Cites work

• scientific article; zbMATH DE number 5287125 (Why is no real title available?)
• scientific article; zbMATH DE number 1275270 (Why is no real title available?)
• An axiomatization of entropy of capacities on set systems
• Choice Functions and Revealed Preference
• Correspondence between two antimatroid algorithmic characterizations
• Entropy of capacities on lattices and set systems
• Extremal subsystems of monotonic systems. I
• Greedoids
• Incomplete classifications of a finite set of objects using monotone systems
• Induced layered clusters, hereditary mappings, and convex geometries
• Layered clusters of tightness set functions
• Matroids and the greedy algorithm
• Monotone linkage clustering and quasi-concave set functions
• Nuclei of monotonic systems on a semilattice of sets
• Quasi-concave functions on meet-semilattices
• Rational Selection of Decision Functions
• The duality between the anti-exchange closure operators and the path independent choice operators on a finite set
• The theory of convex geometries

Cited in

(4)

• A relationship between quasimonotone and monotone bifunctions
• Monotone linkage clustering and quasi-concave set functions
• Quasi-concave functions on meet-semilattices
• Diverse data selection via combinatorial quasi-concavity of distance covariance: a polynomial time global minimax algorithm

This page was built for publication: Duality between quasi-concave functions and monotone linkage functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q712240)