TR-2007-02

Lambda-supermodular functions

Zoltán Király



Abstract

The main usage of supermodular functions is to cross out tight sets, that is to use only the following important property. The intersection and the union of two sets with a maximal function value also have maximal function value. But for this purpose we do not need the full strength of supermodularity, some weaker concept suffices. We introduce here a new property, the so called $\lambda$-supermodularity. A set function $f$ is $\lambda$-supermodular if for any sets $X$ and $Y$ there is number $0<\lambda \le 2$ such that \[f(X)+f(Y)\le \lambda\cdot f(X\cap Y)+ (2-\lambda)\cdot f(X\cup Y).\] Function $f$ is strongly $\lambda$-supermodular if we always find a $\lambda<2$ and weakly if sometimes $\lambda=2$ is needed. Clearly, if $f$ is strongly $\lambda$-supermodular and $X$ and $Y$ are sets with $f(X)=f(Y)=$maximum (called usually tight sets), then $X\cap Y$ and $X\cup Y$ are also tight. If $f$ is weakly $\lambda$-supermodular then we may only conclude that the intersection is tight, however, for many purposes, this fact is enough.
 
We show several examples on how to use $\lambda$-supermodularity related to duals of packings (called barriers). The first and simplest example specializes to the case of star-packings, induced-star packings and long path packing. More and more complicated versions are developed for propeller packings, $f$-factors and ``even factors''.


Bibtex entry:

@techreport{egres-07-02,
AUTHOR = {Kir{\'a}ly, Zolt{\'a}n},
TITLE = {Lambda-supermodular functions},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2007},
NUMBER = {TR-2007-02}
}


Last modification: 5.12.2018. Please email your comments to Tamás Király!