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