Finding submodularity hidden in symmetric difference

DOI10.1137/19M1243361MaRDI QIDQ5218436zbMATH OpenOpenAlexFDO

Authors Junpei Nakashima, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita

Publication date 4 March 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

submodular functionssymmetric difference

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Convexity of real functions of several variables, generalizations (26B25) Convex functions and convex programs in convex geometry (52A41)

Abstract: A set function $f$ on a finite set $V$ is submodular if $f(X)+f(Y)geqf(XcupY)+f(XcapY)$ for any pair $X,YsubseteqV$. The symmetric difference transformation (SD-transformation) of $f$ by a canonical set $SsubseteqV$ is a set function $g$ given by $g(X)=f(XvartriangleS)$ for $XsubseteqV$,where $XvartriangleS=(XsetminusS)cup(SsetminusX)$ denotes the symmetric difference between $X$ and $S$. Submodularity and SD-transformations are regarded as the counterparts of convexity and affine transformations in a discrete space, respectively. However, submodularity is not preserved under SD-transformations, in contrast to the fact that convexity is invariant under affine transformations. This paper presents a characterization of SD-stransformations preserving submodularity. Then, we are concerned with the problem of discovering a canonical set $S$, given the SD-transformation $g$ of a submodular function $f$ by $S$, provided that $g(X)$ is given by a function value oracle. A submodular function $f$ on $V$ is said to be strict if $f(X)+f(Y)>f(XcupY)+f(XcapY)$ holds whenever both $XsetminusY$ and $YsetminusX$ are nonempty. We show that the problem is solved by using $mO(|V|)$ oracle calls when $f$ is strictly submodular, although it requires exponentially many oracle calls in general.

Recommendations

• scientific article; zbMATH DE number 3904328
• A note on minimizing submodular functions
• Minimizing symmetric submodular functions
• Maximizing Non-monotone Submodular Functions
• scientific article; zbMATH DE number 4099306

Cites work

• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• scientific article; zbMATH DE number 7051222 (Why is no real title available?)
• scientific article; zbMATH DE number 7051294 (Why is no real title available?)
• scientific article; zbMATH DE number 3048077 (Why is no real title available?)
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A note on submodular function minimization by Chubanov's LP algorithm
• A note on submodular function minimization with covering type linear constraints
• An analysis of approximations for maximizing submodular set functions—I
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Convex Analysis
• Discrete Convex Analysis
• Learning with submodular functions: a convex optimization perspective
• Maximizing Non-monotone Submodular Functions
• Minimizing symmetric submodular functions
• Submodular functions and optimization.
• The Partial Order of a Polymatroid Extreme Point

Cited in

(1)

• Every finite distributive lattice is isomorphic to the minimizer set of an \(M^\natural \)-concave set function

This page was built for publication: Finding submodularity hidden in symmetric difference

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