Duality between quasi-concave functions and monotone linkage functions

DOI10.1016/J.DISC.2009.09.001zbMATH Open1228.05280arXiv0808.3244OpenAlexW2142407692MaRDI QIDQ712240FDOQ712240

Authors: Yulia Kempner, Vadim E. Levit 

Publication date: 28 October 2010

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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 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)

Cites Work

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

Cited In (4)

• Monotone linkage clustering and quasi-concave set functions
• A relationship between quasimonotone and monotone bifunctions
• 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)