Figure 6: Partition of the square whose vertices coincide with the diagonal.
We can repeat this argument k times until getting a rectangle whose length is
not bigger than α. Once again we apply assumption A1 and Lemma 8.1 to show
that submodularity holds for this rectangle as well and we can conclude that,
F(x, z) - F(z, z) ≥ F (x, x) - F (x, z) .
Hence submodularity is satisfied for any square with vertices coinciding with
the diagonal. ■
The following Lemma establishes that the analysis of submodularity of any
rectangle formed by four points of the domain [0, c]2 can be reduced to the
analysis of submodularity for points placed in such a way that they form a
square with vertices coinciding with the diagonal.
Lemma 8.3 If A1 and A2 hold, then F and G are submodular on [0, c]2 .
Proof. (Lemma 8.3) Due to the kink along the diagonal, one cannot invoke
Topkis’s simple cross-partial test (Topkis’s Characterization Theorem in the
Appendix) to verify submodularity of F and G. Instead, we use definition of
submodularity for any configuration of four points in the domain, constituting
a rectangle. If the rectangle is completely contained in either ∆U or ∆L ,the
submodularity condition follows from A1. Every other situation can be reduced
by adding subrectangles, each of which lying fully in either ∆U or ∆L ,tothe
36
More intriguing information
1. The name is absent2. The technological mediation of mathematics and its learning
3. The name is absent
4. A Study of Adult 'Non-Singers' In Newfoundland
5. The name is absent
6. Structural Breakpoints in Volatility in International Markets
7. The name is absent
8. Life is an Adventure! An agent-based reconciliation of narrative and scientific worldviews
9. Ongoing Emergence: A Core Concept in Epigenetic Robotics
10. TWENTY-FIVE YEARS OF RESEARCH ON WOMEN FARMERS IN AFRICA: LESSONS AND IMPLICATIONS FOR AGRICULTURAL RESEARCH INSTITUTIONS; WITH AN ANNOTATED BIBLIOGRAPHY