A short proof for stronger version of DS decomposition in set function optimization
- PDF / 229,109 Bytes
- 6 Pages / 439.37 x 666.142 pts Page_size
- 35 Downloads / 187 Views
A short proof for stronger version of DS decomposition in set function optimization Xiang Li1
· H. George Du2
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Using a short proof, we show that every set function f can be decomposed into the difference of two monotone increasing and strictly submodular functions g and h, i.e., f = g − h, and every set function f can also be decomposed into the difference of two monotone increasing and strictly supermodular functions g and h, i.e., f = g − h. Keywords Set function · DS decomposition · Monotone nondecreasing · Submodular · Supermodular
1 Introduction Consider a real function f over subsets of a finite set X . f is said to be submodular if for any two subsets A and B of X , f (A) + f (B) ≥ f (A ∪ B) + f (A ∩ B). f is said to be monotone nondecreasing if for any two subsets A and B of X A ⊂ B ⇒ f (A) ≤ f (B). In study of wireless sensor networks, social networks, cloud computing, data science, and machine learning, a lot of problems can be formulated into set function
B
Xiang Li [email protected] H. George Du [email protected]
1
Department of Computer Science and Engineering, Santa CLara University, Santa Clara CA 95053, USA
2
Department of Mathematics, University of Texas at Austin, Austin TX 78712, USA
123
Journal of Combinatorial Optimization
optimizations (Weili et al. 2019). The following theorem plays an important role in the set function optimization. Theorem 1 (1st DS Decomposition) Every set function f : 2 X → R can be decomposed into the difference of two monotone nondecreasing submodular functions g and h, i.e., f = g − h. This theorem is proved by Iyer and Bilmes (Iyer and Bilmes 2012). They first proved that every set function f : 2 X → R can be decomposed into the difference of two submodular functions g and h, i.e., f = g − h. (This weak version of DS deposition is first proposed by Narasimhan and Bilmes (Narasimhan and Bilmes 2005) with a nonrigorous proof.) Then they prove Theorem 1 by using a fact that every submodular function can be decomposed into the sum of a polymatroid function and a modular function, where a polymatroid function is a monotone nondecreasing submodular function with zero function value at empty set, and a set function f : 2 X → R is modular if for any two subsets A and B of X , f (A) + f (B) = f (A ∪ B) + f (A ∩ B). Note that a set function f : 2 X → R is supermodular if for any two subsets A and B of X , f (A) + f (B) ≤ f (A ∪ B) + f (A ∩ B). Li, Du, and Pardalos (Xiang Li 2020) showed a variation of Theorem 1 as follows. Theorem 2 (2nd DS Decomposition) Every set function f : 2 X → R can be decomposed into the difference of two monotone nondecreasing supermodular functions g and h, i.e., f = g − h. In this paper, we will give a short proof for Theorems 1 and 2. Meanwhile, we will make them stronger by replacing monotone nondecreasing, submodular, and supermodular properties by monotone increasing, strictly submodular, and strictly supermodular properties, respectively, which are defined a
Data Loading...
