Finding submodularity hidden in symmetric difference

DOI10.1137/19M1243361zbMATH Open1431.90136arXiv1712.08721OpenAlexW3010283297MaRDI QIDQ5218436FDOQ5218436

Junpei Nakashima, Yukiko Yamauchi, Masafumi Yamashita, Shuji Kijima

Publication date: 4 March 2020

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

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.

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

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

Cites Work

• Convex Analysis
• Discrete Convex Analysis
• Title not available (Why is that?)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Submodular functions and optimization.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Minimizing symmetric submodular functions
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• An analysis of approximations for maximizing submodular set functions—I
• Maximizing Non-monotone Submodular Functions
• Title not available (Why is that?)
• Learning with Submodular Functions: A Convex Optimization Perspective
• A note on submodular function minimization with covering type linear constraints
• The Partial Order of a Polymatroid Extreme Point
• A note on submodular function minimization by Chubanov's LP algorithm

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)