Description
EGERVÁRY SZEMINÁRIUM
Absztrakt:
It is a fundamental result in combinatorial optimization
that submodular functions can be minimized in polynomial time. In this
talk, we consider the minimization problem for a more general class of
submodular functions. A set function is called 2/3-submodular if the
submodular inequality holds for at least two pairs formed from every
distinct three subsets. This talk provides a polynomial time algorithm
to minimize 2/3-submodular functions. This algorithm relies on a basic
property of 2/3-submodular functions, which implies that
2/3-submodular functions are somewhat close to submodular functions.