{'fraction_non_alphanumeric': 0.0702467637540453, 'fraction_numerical': 0.014320388349514563, 'mean_word_length': 3.5812638991845813, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 51, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Rank axiom of modular supermatroids: A connection with directional DR submodular functions

A matroid has been one of the most important combinatorial structures since it was introduced by Whitney as an abstraction of linear independence. As an important property of a matroid, it can be characterized by several different (but equivalent) axioms, such as the augmentation, the base exchange, or the rank axiom. A supermatroid is a generalization of a matroid defined on lattices. Here, the central question is whether a supermatroid can be characterized by several equivalent axioms similar to a matroid. Barnabei, Nicoletti, and Pezzoli characterized supermatroids on distributive lattices, and Fujishige, Koshevoy, and Sano generalized the results for cg-matroids (supermatroids on lower locally distributive lattices). In this study, we focus on modular lattices, which are an important superclass of distributive lattices, and provide equivalent characterizations of supermatroids on modular lattices. We characterize supermatroids on modular lattices using the rank axiom in which the rank function is a directional DR-submodular function, which is a generalization of a submodular function introduced by the authors. Using a characterization based on rank functions, we further prove the strong exchange property of a supermatroid, which has application in optimization. We also reveal the relation between the axioms of a supermatroid on lower semimodular lattices, which is a common superclass of a lower locally distributive lattice and a modular lattice.


Background and Motivation
A matroid is a combinatorial structure first introduced by Whitney [16] as an abstraction of linear independence. A matroid is now regarded as one of the most important combinatorial structures and has been studied in various fields such as combinatorics, geometry, and optimization.
Several generalizations of matroid have been proposed. Here, we focus on a supermatroid on lattices as introduced by Dunstan, Ingleton, and Welsh [6]. Let L be a finite lattice. A supermatroid I on L is an ideal of L such that for all X ∈ L, the maximal elements in I X = {I ∈ I | I ≤ X} have the same height (i.e., distance from the bottom of L). If L is a boolean lattice, the supermatroids coincide with the classical matroids. The classical matroids are characterized by several different (but equivalent) axioms, such as the augmentation, the base exchange, and the rank axioms. Here, the rank function r of a (super)matroid I is defined by r(X) = max{|I| : I ∈ I}. (1) Thus, it is natural to ask whether supermatroids have similar equivalent axioms (see [17]). Barnabei, Nicoletti, and Pezzoli [2] answered this question for supermatroids on distributive lattices, and Fujishige, Koshevoy, and Sano [8] and Sano [14] generalized the results for supermatroids on convex geometries (i.e., lattices of convex sets), where the convex geometries are equivalent to the lower locally distributive lattices. Our aim is to extend this line of study. In particular, we are interested in supermatroids on modular lattices (also called modular supermatroids [12]). Modular lattices are a superclass of distributive lattices and are incomparable with lower locally distributive lattices (see Figure 1). Modular lattices naturally occur in algebra. For example, the set of subspaces of a vector space forms a modular lattice. In addition, the set of normal subgroups of a group form a modular lattice. Modular lattices are also important in optimization and machine learning. The authors formulated a subspace selection problem, including principal component analysis, as a maximization problem over modular lattices, and showed that if the objective function satisfies a submodular-like property, called directional DR-submodularity, the height and the knapsack constrained problems can be solved within provable approximation factors [13].

Our Contributions
The contributions of this study are two-fold. First, we provide several equivalent axioms for supermatroids on modular lattices. Second, we show that a further generalization for a supermatroid on lower-locally modular lattices, which is a common superclass of lower-locally distributive lattices (studied in [8,14]) and modular lattices (see Figure 1) is not straight-forward.
Supermatroids on Modular Lattices. We defined supermatroids via the height axiom. Here, we show that supermatroids on modular lattices can be equivalently characterized by the independence (augmentation) axiom (Theorem 5), the middle base axiom (Theorem 15), the rank axiom (Theorem 8), and the dependence axiom (Theorem 17). Here, the most interesting result is the rank axiom.
In the case of distributive lattices, the rank function must be a submodular function [2], i.e., the rank function r : L → R satisfies the following latticesubmodularity: More precisely, it satisfies the following DR-submodularity [15,9]: where X, Y ∈ L; a ∈ adm(X); and b ∈ adm(Y ) such that X ≤ Y and a ≤ b.
Here, a ∈ adm(X) intuitively indicates that a is safely added to X (see Section 2.1 for a precise definition). We can see that the DR-submodularity implies the lattice-submodularity when the lattice is distributive (see Remark 10). However, this is not the case in modular lattice, where the rank function does not satisfy the DR-submodular inequality (Proposition 12). Thus, we relax the DR-submodularity as follows: A function r : L → R is a downward DR-submodular function if it satisfies the following inequality: where X, Y ∈ L; a ∈ adm(X); and b ∈ adm(Y ) such that X ≤ Y and a ≤ b. This function class was introduced by Nakashima and Maehara [13] as a generalization of the DR-submodular function to characterize tractable subspace selection problems (see Section 2.2). Our rank axiom requires the rank function to be a downward DR-submodular function. Our rank axiom allows us to derive the strong exchange property of supermatroids on modular lattices (Theorem 19), which has applications in optimization problems (see Section 3.6.1 and Section 3.6.2).
Supermatroids on Lower Locally Modular Lattices. It is a natural question whether the relation between the axioms remains true on a class of lattices that is more general than the modular lattices. Here, we consider lower-locally modular lattices, which is a common generalization of modular lattices and lower-locally distributive lattices.
We show that the independence axiom characterizes the matroids; however, all other axioms do not (Section 4).

Related Studies
Matroids on Lattices. Most studies on supermatroids have focused on supermatroids on a distributive lattice [1,2,11], which are also called poset matroids. A further generalization was been conducted. A matroid is a generalization of an arrangement of geometric objects. In this direction, acg-matroid [8] has also been studied. Cg-matroids are equivalent to supermatroids over lower locally distributive lattices [7]. Fujishige, Koshevoy, and Sano [8] studied supermatroids on lower locally distributive lattices, and proved the equivalence of some axioms. Sano [14] characterized supermatroids on lower locally distributive lattices in terms of their rank function. Another study was been conducted on modular lattices. Li and Liu [12] showed the base axiom for supermatroids on modular lattices.
One of the purposes of this study is to complete the characterization of supermatroids on modular lattices. Another is to unify the theory of lower locally distributive and modular lattices. We consider lower locally modular lattices, which contain both lower locally distributive lattices and modular lattices as proper subclasses.
DR-Submodular Function. In the machine-learning community, submodular functions (on the set lattices) have been widely studied. Soma and Yoshida [15] introduced a class of functions on an integer lattice (Z n ), called DR-submodular functions, as a generalization of the submodular functions on set lattices. The authors generalized this concept for a modular lattice and derived an approximation algorithm [13] for maximization problems of the functions.

Lattice
Let (P, ≤) be a poset. A subset I ⊆ P is an ideal if p ∈ I for any p, p ′ ∈ P with p ≤ p ′ and p ′ ∈ I. A subset F ⊆ P is a filter if the complementary set I = P \ F is an ideal. A subset I ⊆ P is proper if I = P . By P * , we denote the order-reversal of P .
A lattice (L, ≤) is a partially ordered set closed under the least upper bound To avoid confusion, we use upper-case letters for general lattice elements and lower-case letters for joinirreducible elements. The set of join-irreducible elements is denoted by J . A lattice L is atomic if any pair of J is incomparable. A join-irreducible element a ∈ J is admissible with respect to X if X ∧ a ≺ a. We denote by adm(X) the set of admissible elements with respect to X.
is modular if it is both lower-and upper-semimodular. A lattice L is distributive if for any X, Y, Z ∈ L, the following identity holds: Note that any distributive lattice is also a modular lattice.
The lattice is said to be a lower locally modular lattice if for each X ∈ L, the interval [X − , X] is a modular lattice, and lower locally distributive if [X − , X] is a distributive lattice. Any lower locally distributive lattice has a geometric realization called a convex geometry [7]. The relations of the lattices are summarized in Figure 1.
For X, Y ∈ L with X ≤ Y , a chain is a sequence of the form X = X 0 ≤ X 1 ≤ · · · ≤ X m = Y . In a lower-or upper-semimodular lattice, for any two elements X, Y with X ≤ Y , the length of the maximal chain, X = X 0 ≺ X 1 ≺ · · · ≺ X m = Y , is the same [3], which is called the Jordan-Dedekind property. In lower-semimodular lattices, the height |X| is the length of the maximal chain from ⊥ to X. The height of a lattice L is |⊤|.
A lattice is a finite length if the maximum length of the chains is bounded. This study only considers the lattices of a finite length. A finite length lattice is bounded, i.e., it has the top ⊤, which is greater than any other elements, and the bottom ⊥, which is smaller than any other elements. For X ∈ L, the height |X| is the length of the maximal ascending chain from the bottom to X.
A fundamental example of a modular lattice is a vector lattice. A vector lattice L(R n ) consists of all linear subspaces of R n equipped with the inclusion order ≤:=⊆. For X, Y ∈ L(R 2 ), we have X ∧ Y = X ∩ Y , and X ∨ Y equals the direct sum of X and Y . We can easily see that L(R n ) is an atomic modular lattice and that join-irreducible elements are of the form span(v) for a certain v ∈ R n \ {0}.

Directional DR-submodular Functions
Definition 1 (directional DR-submodularity [13]). Let L be a lattice. A function f : L → R is downward DR-submodular if for all X, Y ∈ L with X ≤ Y and b ∈ adm(Y ), there exists b ′ = b mod Y such that, for all a ∈ adm(X) with a ≤ b ′ , the following holds: A function f is upward DR-submodular if f is downward DR-submodular on L * . If a function f is both downward DR-submodular and upward DRsubmodular, we state that f is bidirectional DR-submodular.
Remark 2. The definition of the upward DR-submodularity is different from the original [13]. We introduced a weaker definition to investigate the dualistic nature of the modular supermatroids. See Section 3.7.

Supermatroids on Modular Lattices
In this section, we reveal the relationship between directional DR-submodularity and modular supermatroids: Directional DR-submodularity naturally arises as a property of the rank function of a modular supermatroid. We also introduce some new characterizations of modular supermatroids. In this section, L is a modular lattice and I ⊆ L if there are no futher specifications. All proofs are given in Section 5.

Height Axiom
Let P = (P, ≤) be a poset. A subset I ⊆ P is a supermatroid if it satisfies the following height axiom.

Definition 3 (Height Axiom). (H1) I is a non-empty ideal;
(H2) For all X ∈ P , the maximal elements in the intersection of I and I X := {X ′ ∈ P | X ′ ≤ X} have the same height.
The rank of a modular supermatroid I is the height of the maximal elments of I, which is uniquely determined by (H2). A supermatroid over a modular lattice is called a modular supermatroid. A supermatroid over a distributive lattice is called a distributive supermatroid or a poset matroid.

Independence Axiom
Modular supermatroid I is alternatively defined by the following augumentation axiom: Consider the following condition on I.
We can weaken the independence axiom. The "localized" augmentation (Figure 2) is sufficiently strong to characterize the modular supematroids.

Rank Axiom
We characterize modular supermatroids in terms of their rank function. Let r : L → R. Consider the following condition on r.
(2) Conversely, let r be a function over a modular lattice satisfying the rank axiom. Then, I := {X ∈ L | r(X) = |X|} is a modular supermatroid.
The condition (R3) appears to lack symmetry. Thus, it would be natural to consider the upward and the bidirectional versions as follows: (R3u) r is a upward DR-submodular function; (R3b) r is a bidirectional DR-submodular function.
Proposition 9. Let L be a lattice and r : L → R be a function that satisfies (R1) and (R2). Then, r satisfies (R3) if and only if r satisfies (R3u).
Remark 10. Theorem 8 implies that the rank function of a supermatroid on a distributive lattice is a DR-submodular function. The downward DRsubmodular function coincides with the DR-submodular function [13].
Remark 11. We remark that (R3) cannot be replaced with "r is a latticesubmodular function." Proposition 12 (The lattice submodularity is insufficient). There exists a modular lattice L and a supermatroid I on L such that the rank function r(X) = max{|I| | I ∈ I, I ≤ X} is not lattice-submodular.
Proof. Let L = {⊥, a, b, c, ⊤} be a diamond lattice and I = {⊥, a} ⊆ L as shown in Figure 3, where the elements in I are indicated by the black points. The subset I is a supermatroid. However, the rank function does not satisfy the lattice submodularity because Note that the rank function of a cg-matroid satisfies the submodularity [14]. Thus, the directional DR-submodularity is required to handle the modularity of the lattice.
This result indicates the naturality of our directional DR-submodularities. Directional DR-submodularities are originally introduced to characterize the maximization problems solved by a greedy algorithm over the lattices [13]. Surprisingly, directional DR-submodularties are indespensable concepts in a different subject, i.e., modular supermatroids.

Middle Axiom (Base Axiom)
In this section, we derive a middle axiom for base, maximal elemets of I, of modular supermatroids. Consider the following conditions on B ⊆ L:

Dependence Axiom
In this section, we introduce an axiom for D := L \ I. This is a substitute for the standard axiom for circuits (minimal elements of D). Introducing an axiom for the circuits of the modular supermatroids is an unsolved problem raised in [12]. Here, we only consider D because the axiom for the circuits of modular supermatroids is not simple and has almost the same form as that of D. Consider the following conditions for D ⊆ L.
We note that (D2) is called the elimination axiom and (D3) the replacement axiom in [2].

Strong Basis Exchange Theorem
We prove the strong exchange property of modular supermatroids.
Remark 18. As a difficulty in generalizing the strong exchange property to modular supermatroids, we cannot uniquely define the "minus" operation X − a := X \ {a} for a set X and an element a ∈ X for modular lattices, which is used in the statement of the usual strong exchange property. More precisely, there might be multiple values ofX ≺ X such thatX ∨ a = X forX ≺ X and a ∈ adm(X). Let us consider a vector lattice L(R 2 ). Let a = span((1, 0) ⊤ ) and X = ⊤. In this setting, all one-dimensional spaces of the formX = span(v) for v = (1, 0) ⊤ satisfy X := ⊤ =X ∨ a. We overcome this difficulty by formulating a strong exchange property through Theorem 19. The formulation is natural in that it implies a usual strong exchange property for Boolean lattices (Remark 22) and the base axiom (Proposition 20). In addition, it can be applied to an optimization (Sections 3.6.1 and 3.6.2). Figure 4 shows the relationship among the elements appearing in this theorem.
We can use a strong exchange property as the base Axiom: Proposition 20. The strong exchange property implies (B3). Remark 21. In the proof of the strong exchange property, the directional DRsubmodularity of the rank function plays an important role (Lemma 65 and its application to the proof of Theorem 19). This is an application of the rank axiom and directional DR-submodularity.
Remark 22. In a Boolean lattice, Theorem 19 implies the usual strong exchange property. In Boolean lattice, w is uniquely determined as X \X. Because all join-irreducible elements are incomparable in the Boolean lattices, Using a similar argument, we can prove that Theorem 19 implies a strong exchange property of the distributive lattices [2].
For atomic modular lattices, we can simplify the statement of the strong exchange property.
Here, w and v are join-irreducible elements.
Proof. Because all join-irreducible elements are incomparable, w = w and y = y. The latter and In the following sections, we provide applications of strong exchange property for mathematical optimization.

Application 1: Valuated Supermatroid
Valuated matroids [5] are a quantitative generalization of a matroid (on the Boolean lattices) defined by extending the strong exchange property of the matroids. Based on our strong exchange property on the supermatroids on atomic modular lattices, we can generalize the valuated matroids to valuated supermatroids on atomic modular lattices.
Let L be a modular lattice, and let L k = {X ∈ L | |X| = k} for integer k. A function ω : L → R is a valuated supermatroid if it satisfies the following: For all X, Y ∈ L k andX ≺ X with X ∧ Y ≤X, there exists w ∈ adm(X) withX ∨ w = X that satisfies the following. For all w ≤ w with w ∈ adm(Y ), Algorithm 1 Greedy algorithm for maximization problem of valuated supermatroid. for Theorem 24. Let ω be a valuated supermatroid on an atomic modular lattice L. Algorithm 1 finds a maximizer of ω.
A rank function of a supermatroid on an atomic modular lattice is a valuated supermatroid. A non-trivial example of this is the objective function of principal component analysis with a single data point: where Π X is the projection into subspace X, and d is a vector in R n . Then, ω PCA is a valuated modular supermatroid.
We conjecture that the objective function of principal component analysis is a valuated supermatroid even if there is more than a single data point. If this conjecture is true, we can explain the fact that the greedy algorithm finds the optimal solution of w PCA from the perspective of a matroid.

Application 2: DR-submodular maximization on supermatroid
The authors considered a maximization problem of a monotone downward DR-submodular function over a modular lattice L under the height and the knapsack constraints [13]. We proved that the greedy algorithm has approximation guarantees by generalizing the standard results for Boolean lattices. It seems natural to consider a modular supermatroid constraint, i.e., maximize f (X) subject to X ∈ I, Algorithm 2 Greedy algorithm for modular supermatroid constrained problem. 4: X ← X ∨ a i 5: end for 6: return X where f : L → R is a downward DR-submodular function and I ⊆ L is a modular supermatroid. However, we lacked the strong exchange property for supermatroids, which is a key technique of the optimization problem. Therefore, it was unknown whether the greedy algorithm has an approximation guarantee for a downward DR-submodular function maximization under a modular supermatroid constraint. Here, using the strong exchange property, we give a partial answer: The greedy algorithm has a 1/2-approximation gurantee for a strong DR-submodular maximization problem over atomic modular lattices under a modular supermatroid constraint.
The strong DR-submodularity is another generalization of DR-submodularity and stronger than downward DR-submodularity [13].
Definition 26 (Strong DR-submodularity). Let L be a modular lattice. A function f : for all X, Y ∈ L with X ≤ Y , a ∈ adm(Y ), and a ≤ a with a ∈ adm(X).
Two facts regarding a strong DR-submodularity should be noted [13]. First, a strong DR-submodularity implies a bidirectional DR-submodularity, however, the converse is not true. In addition, a strong DR-submodularity is equivalent to downward directional DR-submodularity on a distribuitve lattice.
Theorem 27. Consider a maximization problem of a monotone strong DRsubmodular function f over atomic modular lattice L under a modular supermatroid constraint I ⊆ L. Let k be the rank of I. Algorithm 2 then has an approximation ratio of 1/2.
We describe the difficulties generalizing to general modular lattices and directional DR-submodular functions in Remark 69. Such generalizations are left as for future studies.
When the "linearity" of the objective function is characterized by the curvature as in a Boolean lattice case [4], we can guarantee a refined approximation.
Definition 28 ( [13]). A monotone bidirectional DR-submodular function f has a curvature c if, for all X ∈ L, a ∈ adm(X), and minimal a ≤ a, Theorem 29. Consider a maximization problem of a monotone bidirectional DR-submodular function over a (possibly non-atomic) modular lattice L with curvature c under modular supermatroid constraint I ⊆ L. Algorithm 2 has an approximation ratio of 1 − c.

Dual Matroids
In this section, we define a dual matroid of a modular supermatroid. This duality is used to prove Proposition 9, and will have an independent interest. Let(·) : L → L * be an order-reversing isomorphism. Let B be the set of bases on L. Then, the corresponding dual matroid is a modular supermatroid on L * whose set of bases B * is The dual matroid is indeed a modular supermatroid because the base Axiom is self-dual (i.e., invariant for an order-reversal) and(·) is an order-reversing isomorphism.
Remark 30. We can always define(·) byX = X for all X. For some special classes of lattices, we can take a natural(·). For a set lattice over finite set E (i.e., finite boolean lattice), L ∼ = L * , and we can defineX = E \ X. Similarly, for a vector lattice L(R d ), we have L(R n ) ∼ = L(R n ) * and can define a mapX = X ⊥ . For a distributive lattice, we can define(·) as the complement operation on a Birkhoff's representation.
Example 31. Let L be a set lattice over a finite set E andX = E \ X. Then, B * defines the usual dual matroid.
Example 32. LetX = X. In this setting, an element X ∈ L * is an independent set of the dual matroid if X ≥ B for some base B of the primal modular supermatroid.
We characterize the rank function of the dual matroid as follows: Proposition 33. Let r be the rank function of a modular supermatroid. Let r * be the rank function of the dual matroid. Then, where | · | is the height of L.

Examples
Here, we give examples of modular supermatroids. We use our rank axiom to show the structure is in fact modular supermatroid.
Example 34 (Uniform Matorid). Let L be a modular lattice. For an integer k, the set I = {I ∈ L : |I| ≤ k} of the lattice elements whose height is at most k forms a modular supermatroid because the rank function of I is h(I) = min{|I|, k} and satisfies the rank axiom.
Example 36 (Linear Matroid). Let L be a sublattice of L(R d ) such that for all X ∈ L, the height of X in L is the same as that of in L(R d ). A function A : R d → R k is said to be collinear-preserving if A(x), A(y), and A(z) are collinear (i.e., three points are on a certain straight line) for all collinear x, y, and z in R d . A linear supermatroid I A ⊆ L represented by a collinear-preserving map A is defined by where dim X is the dimension of vector space X, and span(Y ) is the linear span of Y ⊆ R d . Later, we see this definition generalizes the usual linear matroid. The rank function r A of I A is given by We prove that r A satisfies (R1), (R2), and (R3). The condition (R1) trivially holds. The condition (R2) follows from the collinear-preserving property of A. We finally prove (R3). Let X, Y ∈ L with X ⊆ Y and v ∈ adm(Y ). If r A (Y ∨v) = r A (Y ), the downward DR-submodularity trivially holds. Otherwise, Then, the linear supermatroid I A is identified as a linear matroid represented by A ′ over 2 V .

Supermatroids on Lower Locally Modular Lattices
It is a natural question whether the relation between the axioms remains true on a class of lattices that is more general than the modular lattices. Here, we consider lower-locally modular lattice, which is a common generalization of modular lattice and lower-locally distributive lattice.
We show that the independence axiom characterizes the matroids; however, all other axioms do not. All proofs are given in Section 5.

Independence Axiom
A supermatroid on lower locally modular lattices is also characterized by the independence axiom. More generally, a supermatroid on arbitrary lattices is characterized by the independence axiom.
Theorem 37 (Height Axiom ⇔ Independence Axiom). Let L be a lattice.
In a modular lattice, the independence axiom can be replaced with a local version (I2l) as shown in Proposition 6. However, (I2l) is too weak to characterize supermatroids on lower locally modular, and even worse, lower locally distributive lattices [8]. We consider the lattice in Figure 5, where I is indicated by the black points in the figure. This lattice is lower locally distributive, and satisfies (I1) and (I2l). However, it does not satisfy (H1); thus, it is not a supermatroid.
Fujishige, Koshevoy, and Sano [8] called the structure satisfying (I1) and (I2) (applied to the lattice of convex sets) a strict cg-matroid, and then defined the following weaker version of the independence axiom to define a matroid on the lattice of convex sets.
(I2w) For any I 1 , I 2 ∈ I such that I 2 is maximal in I and |I 1 | < |I 2 |, there exists J such that I 1 < J ≤ I 1 ∨ I 2 .
Clearly (I2) implies (I2w), but the converse does not hold in general. Here, we show that the converse holds when the lattice is modular.

Middle Axiom (Base Axiom)
If the underlying lattice is a lower-locally distributive lattice, the middle axiom does not characterize matroids. More precisely, we prove that the middle axiom is equivalent to the weak independence axiom in general lattices.

Rank Axiom
The rank axiom does not characterize matroids if an underlying lattice is lower-locally modular (or lower-locally distributice); the counterexample is given in Example 42.
Example 42. Consider the lattice shown in Figure 6. We can easily check that this lattice is lower locally distributive. Consider a rank function r defined by r(⊥) = 0, r(a) = r(d) = r(f ) = 1, r(b) = r(e) = r(g) = r(h) = 2, and r(c) = r(⊤) = 3. Then, r satisfies the rank axiom and the rank of the supermatroid is 3. However, g is a height-2 maximal element of the supermatroids, which contradicts (H2).
We prove that the independence axiom implies the rank axiom if the lattice is lower-semimodular, and the converse holds if the lattice is upper-semimodular.
We tried to characterize the rank function of supermatroids on lower-locally modular lattices by modifying (R3). We tried the followings attempts.
• Replace the downward-DR submodularity to the upward-DR submodularity or the bidirectional DR-submodularity.
• Replace the downward-DR submodularity to a modified version of the downward-DR submodularity.
Unfortunately, both attempts failed; hence, it is an open problem to characterize the rank function of lower-locally modular lattices in terms of a submodular-like property. Below, we explain the failure of our attempts. The first modification ensures that the rank axiom implies the independence axiom because of Theorem 43; however, the converse does not hold; see the following example.
Example 44. Consider a lower locally distributive lattice L shown in Figure 7. The elements in I are shown by the black dots. Although I is a supermatroid, the rank function r is not upward DR-submodular. By taking Y ∨ b := X, Y := W , and X := Y ∨ q in (16), we can easily see that r is not downward DR-submodular on L * .
For the second modification, we introduce the following strengthening version of the DR-submodularity. We say that p ∈ L is a co-extreme point if p is join-irreducible and X ∨ p ≻ X. We denote by ex * (X) the set of co-extreme points.

Definition 45 (Downward DR-Submodular'). A function is downward DR
This definition is distinguished from the original by the prime, and is equivalent to the original definition on modular lattices.
Lemma 46. Let L be a modular lattice. The downward DR-submodularity' is then equivalent to the downward DR-submodularity. We replace the (R3) in the rank axiom by the following (R3s): (R3s) ρ is a downward DR-submodular' function.
Then, the modified properties implies the independence axiom. However, the converse does not hold as shown in the following example.
Example 48. Consider the same example in the previous example ( Figure 6). Recall that this lattice is lower locally distributive, and I shown by black dots is a supermatroid. The rank function is not downward DR-submodular'. Take X, Y, p, q as in Figure 6. Then, ex * (X) = {p} and f (X ∨ p) − f (X) = 0, i.e., the independence axiom does not implies the (replaced version of the) rank axiom.
These results indicate that it is difficult to characterize the rank function of a supermatroid over a lower locally modular lattice by submodularity.
Note that if we do not stick to the submodularity of the rank function, we can define the following "rank axiom" that characterize matroids. Note that this definition is motivated by Sano [14,Theorem 1.2], which is a characterization of matroids on lower-locally distributive lattices.

Dependendence Axiom
The dependence axiom does not characterize matroids if an underlying lattice is lower-locally modular. We prove that the dependence axiom is equivalent to the "local" independence axiom.

Proofs
In this section, we give the omitted proofs.

Properties of Lattices
Here, we summarize the properties of the lattices that are necessary for better understanding the following proofs. We state that p ∈ L is an extreme point if p is a join-irreducible and there existsX ≺ X such that X =X ∨ p. We denote by ex(X) = {(x,B) |B ≺B ∨ x = B} the set of extreme points with its remaining part. We can see that p ∈ ex * (X), and thus (p, X) ∈ ex(X ∨ p).
Lemma 52. Let L be an upper semimodular lattice. Then, for all X ∈ L and a ∈ adm(X), X ≺ X ∨ a.
Proof. a ∈ adm(X) indicates X ∧ a ≺ a. By the upper semimodularity, this implies that X ≺ X ∨ a.
Lemma 53. Let L be a lower or upper semimodular lattice. Then, X ≺ Y if and only if X ≤ Y and |X| + 1 = |Y |.
Proof. Because the height is well-defined in a lower or upper semimodular lattice, this lemma trivially holds.
Lemma 54. Let L be a lattice. For any X, Y ∈ L and a ∈ adm(Y ) with a ≤ X, there exists b ∈ adm(X) such that b ≤ a.
Proof. We construct b as follows. Initially, we set b 0 = a. For each i, if there exists Z ≺ b i with Z ≤ X, we set b i+1 = Z and continue the process; otherwise, we terminate the process and obtain b = b i . Note that b = ⊥ because ⊥ ≤ X. Then, {Z ∈ L : Z ≺ b} are maximal elements in X ∧ b, and because X ∧ b must be determined uniquely, there exists a unique Z ≺ b such that Z = X ∧ b. This means b ∈ adm(X).
Lemma 55. Let L be a lower semimodular lattice. For any X, Y ∈ L with X ≺ Y and Z ≤ Y with Z ≤ X, we have X ∧ Z ≺ Z.
Proof. Because Z ≤ X and X, Z ≤ Y , we have X < X ∨ Z ≤ Y . Because X ≺ Y , it must be X ∨ Z = Y ; thus, X ≺ X ∨ Z. By the lower submodularity, this implies X ∧ Z ≺ Z.
Proof. Based on this assumption, we have X ≤Y ; otherwise, y ≤ X ≤Y , which contradictsY ∨ y ≻Y . Thus, X ∨Y ≻Y . By the lower semimodularity, we have X ∧Y ≺ X. By y ≤ X ∧Y and y ≤ X, we have X ∧Y = X.
Lemma 57. For any (z, Z) ∈ ex(X ∨ Y ), the element z is extreme point for X and Y .
Proof. By definition, Z ≺ X ∨ Y . Based on a lower locally modularity, we have Z ∧ X ≺ X and Z ∧ Y ≺ Y . Because z ≤ X ∧ Z and z ≤ Y ∧ Z, we proved the statement.
Lemma 58. Let X < Y . Then, there exists q ≤ Y such that q ∈ ex * (X).
Proof. Let X ′ be X ≺ X ′ ≤ Y . Then, there exists a join irreducible q that is less than X ′ and not less than X because we otherwise have X ′ = {q ∈ J : q ≤ X ′ } ≤ X, which contradicts X ≺ X ′ . Because X ∨ q = X ′ ≻ X, q ∈ ex * (X).
The following lemma is useful in a lower locally modular lattice.
Lemma 59 (Ladder Lemma). Let L be a lower locally modular lattice. Let X 0 ≺ X 1 ≺ · · · ≺ X m be a maximal chain between X 0 and X m , and Z ∈ L be an element such that Z ≺ X m . There then exists l ∈ Z such that X i ∧ Z ≺ X i for i = l + 1, . . . , m and X l−1 = X l ∧ Z (see Figure 8).
Proof. We prove the claim through an induction based on the length of the chain. Suppose m = 1. Then, X 1 has X 0 , and Z = X 1 ∧ Z as the covering elements. If X 0 = X 1 ∧ Z, then the claim holds. Otherwise, by the lower local modularity at X 1 , we see that X 0 ∧ (X 1 ∧ Z) ≺ X 1 ∧ Z is covered by both X 0 and X 1 ∧ Z. Thus, the claim holds. Now, we suppose m ≥. Based on the induction hypothesis applied to the subchain X 1 ≺ · · · ≺ X m , we obtain the ladder from X 1 . If X 1 = X 1 ∧ Z, then X 0 = X 0 ∧ X 1 = X 0 ∧ (X 1 ∧ Z) = X 0 ∧ Z; therefore, the claim holds. Otherwise, by the induction hypothesis to X 0 ≺ X 1 and X 1 ∧ Z ≺ X 1 , we prove the claim.

Proofs for Independence Axiom
Proof of Theorem 5 and Theorem 37. It suffices to prove Theorem 37.
Proof of Proposition 6. Let I 1 , I 2 ∈ I such that |I 1 | ≤ |I 2 |. We prove that there exists J ∈ I such that I 1 < J ≤ I 1 ∨ I 2 by the induction on k := |I 1 ∨ I 2 | − |I 2 |. If k = 0, then we can choose J = I 2 . If k ≥ 1, then we pick I 2 < K ≺ I 1 ∨ I 2 .
To prove Theorem 39, we use the following lemma.
Lemma 60. Let L be an upper semimodular lattice. For any X, Y, Z ∈ L such that X ≺ Y , we have X ∨ Z Y ∨ Z.
Proof of Theorem 39. Let I 1 and I 2 be |I 1 | < |I 2 |. We prove that there exists J such that I 1 ≺ J ≤ I 1 ∨ I 2 by the induction on |I 2 |. If I 2 is maximal, there is nothing to prove. If I 2 is not maximal, we choose I 2 ≺ I ′ with I ′ ∈ I and apply the induction hypothesis to obtain K ∈ I such that I 1 ≺ K ≤ I 1 ∨ I ′ . Because |K| < |I ′ |, we can apply the induction hypothesis to K and J ′ and obtain K ′ ∈ I such that K ≺ K ′ ≤ K ∨ I ′ ≤ I 1 ∨ I ′ .
Proof of Theorem 15 and Theorem 41. By Proposition 6, it suffices to prove Theorem 41. (⇐). By definition, (B1) is trivial. We prove (B2). Let B 1 , B 2 , X, Y be as in (B2). Because I is an ideal and X ≤ B 1 , we have X ∈ I. We construct B as follows. Initially, we put B = X. If B is a maximal in I then B satisfies the requirement. Otherwise, by (H2), |B| < |B 1 | = |B 2 |. By (I2w), there exists I ∈ I such that B < I ≤ B 1 ∨ B 1 . We replace B by I and continue the process. Because each step increases the height of B by at least 1, it terminates in a finite step. (⇒). By definition, (I1) is trivial. We prove (I2w). Let I 1 , I 2 ∈ I with |I 1 | < |I 2 |, where I 2 is maximal. Because I 2 is maximal, I 2 ∈ B. By the definition of I, there exists B 1 ∈ B such that I 1 ≤ B 1 . By (B2), there exists B ∈ B such that I 1 ≤ B ≤ I 2 . By Lemma 14, we have |I 1 | < |I 2 | = |B|; hence, I 1 = B. Therefore, (I2w) holds.

Proofs for Rank Axiom
Proof of Theorem 8 and Theorem 43. It suffices to prove Theorem 43 because a modular lattice is both lower and upper semimodular.
(1). (R1) is trivial. We prove (R2). It is easy to see that r is an integervalued non-decreasing function. Hence, it suffices to show that the increment r(X)− r(X ′ ) is at most 1 for all X ≻ X ′ . Suppose that r(X) = |I| for I ∈ I and I ≤ X. If I ≤ X ′ , then r(X) − r(X ′ ) = 0. Otherwise, by Lemma 55, X ′ ∧ I ≺ I. Because X ′ ∧ I ∈ I, we have r(X) ≥ |X ′ ∧ I| = |I| − 1 = r(X) − 1, where the first equality follows from Lemma 53.
We finally prove (R3). Let X, Y ∈ L with X ≤ y and b ∈ adm(Y ). If r(Y ∨ b) − r(Y ) = 0, the downward DR-submodularity trivially holds. Thus, by (R2), we only have to consider the case in which r(Y ∨ a) − r(Y ) = 1. We pick a maximal chain X = X 0 ≺ X 1 ≺ · · · ≺ X k = Y ≺ X k+1 = Y ∨ a. We then construct a corresponding chain I = I 0 I 1 · · · I k ≺ I k+1 as follows. Let I 0 ∈ I be the maximal independent set of X 0 . For each i = 1, . . . , k + 1, we construct I i ∈ I such that r(X i ) = |I i | by the following rule. If r(X i ) = |I i−1 |, we apply I i = I i−1 . Otherwise, there exists J i ∈ I with J i ≤ X i and |I i−1 | < |J i |. By (R2), |J i | = |I i−1 | + 1. In addition, by (I2), there exists I i ∈ I such that I i−1 < I i ≤ I i−1 ∨ J i ≤ X i . By comparing the heights, r(X i ) = |I i |. Because X k ≺ X k+1 , we have I k+1 ≤ X k through the construction of I k+1 . By Lemma 55, X k ∨ I k+1 = X k+1 . In addition, because I k ≺ I k+1 , there exists b ∈ adm(I k ) such that This implies the downward DR-submodularity. (2). (I1) I is non-empty because ⊥∈ I. By (R2), we can easily show that I is an ideal.
Proof of Lemma 46. Note that, in a modular lattice, ex * (X) = adm(X). In addition, in a modular lattice, for any Z with Z ≡ q mod Y , there exists p ∈ ex * (X) with p ≤ Z. Thus, we can ignore the second constraint in the outer maximum in (16).
If f satisfies the DR-submodularity (6), it clearly satisfies the DR-submodularity' (16) because the range of the outer maximum in (16) is larger than that of (6).
Conversely, if f satisfies (16), we choose any z ≤ Z such that z ∈ adm(Y ). Then, z = q mod Y . Thus, it is a candidate for the outer maximum in (6). Because the range of the inner minimum in (6) is smaller than that of (16) for z ≤ Z, it satisfies (6).
Proof of Proposition 9. In this proof, we use Proposition 33, which is proved later. We note that the proof of Proposition 33 does not depend on this proposition. We first prove that (R3) implies (R3u). We define an order-reversing map (·) : L → L * byX = X. Let r * be the rank function of the dual matroid. By Proposition 33, where | · | is the height of L. The rank axiom (R3) for the dual matroid implies that r * is a downward DR-submodular function on L * . By the definition of downward DR-submodularity, we can easily check that r is also a downward DRsubmodular function on L * . Hence, by definition, r is upward DR-submodular.
We can prove that (R3u) implies (R3) by a similar argument.
To prove Theorem 47, we need the following lemma.
Lemma 61. Suppose that L is a lower locally modular lattice. Let X, Y ∈ L with X ≤ Y and q ∈ ex * (Y ). Then, there exists Z ∈ L and p ∈ ex * (X) such that Z = q mod Y and p ≤ Z.
Proof. If X = Y , then we can choose p = Z = q. Thus, we consider X < Y . First, we choose an arbitrary chain from q to Y ∨ q and select Z ∈ L as the second from the last in the chain, i.e., q ≤ Z ≺ Y ∨q. Now, we apply the Ladder lemma to the chain X = X 0 ≺ · · · ≺ X m = Y ∨ Z and Z to obtain the ladder. If X 0 ∧Z ≺ X 0 (as shown on the left side of Figure 8), by Lemma 58, there exists a join-irreducible p such that p ≤ X 1 ∧Z and p ≤ X, which gives X 0 ∨p = X 1 ≻ X 0 . Otherwise (the right of Figure 8), by Lemma 58, there exists a join-irreducible p such that p ≤ X 1 and p ≤ X, which gives X 0 ∨ p = X 1 ≻ X 0 .
Proof of Theorem 47. We prove the independence axiom. (I1) holds by (R2). We prove (I2). Let I 1 , I 2 ∈ I with |I 1 | < |I 2 |. We choose a chain Proof of Theorem 50. Note that (R1) and (R2) is equivalent to (I1) by the same proof as Theorem 43. In addition, we can easily see that (R3) is equivalent to (I2).

Proofs for Dependence Axiom
Proofs of Theorem 17 and Theorem 51. By Proposition 6, Theorem 17 implies Theorem 51. Note that the proof of Proposition 6 is valid for a supermatroids on a lower locally modular lattice. Therefore, we prove Theorem 17 in the following.
(⇐) (D1) is trivial. We prove (D2). Suppose that Z ∈ I and D 1 ∧ D 2 ∈ I. By the lower semimodularity, we have By applying augmentation (I2) to the pair (D 1 ∧ D 2 , Z), we obtain I ∈ I with Here, the last equality follows from We next prove (D3). Suppose to the contrary that X, W ∈ I. Then, |X| + 1 ≤ |W |. By applying (I2) to X and W , we have I ∈ I with X < I ≤ X ∨ W . This implies that Y ∈ I; however this is a contradiction.
(2) (I1) is trivial. It suffices to show (I2l) because of Proposition 6. In other words, it suffices to show augmentation (I2) for a restricted lattice L ′ = {X ∈ L | I 1 ∧ I 2 ≤ X ≤ I 1 ∨ I 2 }, i.e., all modular lattices with a height of at most 2. Let I 1 , I 2 ∈ I with |I 1 | + 1 = |I 2 | and |I 2 | ≺ ⊤ = I 1 ∨ I 2 . The case I 1 ≤ I 2 is trivial. Suppose that I 1 ≤ I 2 . Then, one of the following holds: (a) There uniquely exists J such that I 1 < J < ⊤ (b) there are two or more J such that I 1 ≺ J ≺ ⊤. In case (a), I 1 has an augmentation J owing to (D3). Here, we take X := I 1 , W := I 2 , and Y := J in (D3). In case (b), X has an augmentation owing to (D2). Here, we take Z := I 1 and D i = J i (i = 1, 2), where J i satisfies I 1 ≺ J i ≺ ⊤.

Proofs for Dual Matroids
Proof of Proposition 33. The rank function is characterized as r(X) = max B∈B |B∧ X|. Therefore, for the dual matroid, we have r * (X) = max B∈B |B ∧ * X | * , where we put a superscript * in order to distinguish the ∧ operation and height of L * from those of L. Because Y ∨ Z =Ȳ ∧ * Z and |Ȳ | * = |⊤| − |Y |, we have By the modularity of the height, |B ∨ X| = |B| + |X| − |B ∧ X|. Hence, min B∈B |B ∨ X| = |B| + |X| − max B∈B |B ∧ X| = r(⊤) + |X| − r(X). This completes the proof.

Birkhoff-type Representation of Modular Lattices
To prove Theorem 19, we use the Birkhoff-type representation theorem [10] for modular lattices. Hence, we summarize the Birkhoff representation.
Let P be a poset and C be a ternary relation on P . We suppose that C is symmetric, that is, C(q, r, p) and C(r, p, q) hold if C(p, q, r) holds for all p, q, r ∈ P . The symmetric ternary relation C is called a collinearity relation if the following condition holds: All triplets p, q, r ∈ P with C(p, q, r) are (1) pairwise incomparable and (2) if p, q, ≤ s, then s ≤ r for all s ∈ P . An ordered space is a poset equipped with a collinearity relation. A subspace of P is an ideal I satisfying the following property: If C(p, q, r) and p, q ∈ I, then r ∈ I. A projective ordered space is an ordered space satisfying certain axioms [10].
Herrmann, Pickering, and Roddy [10] proposed a Birkhoff-type representation theorem of a nodular lattice. We can construct a modular lattice L(P ) from a projective ordered space P as follows. Let L(P ) be the family of the subspaces of P and consider the inclusive order. Conversely, we can construct a projective ordered space P (L) from a modular lattice L as follows. Let P (L) be the family of join-irreducible elements of L. Consider the order on P (L) induced by L. In addition, p, q, r ∈ P (L) is C(p, q, r) if and only if (1) p, q, r are pairwise incomparable and p ∨ q = q ∨ r = r ∨ p. Then, the following representation theorem holds.
Theorem 62 ( [10]). Let L be a modular lattice and P be a projective ordered space. Then, L(P ) is a modular lattice and P (L) is a projective ordered space. Also, L ∼ = L(P (L)) and P ∼ = P (L(P )).
In the rest of this section, we use this identification between a modular lattice L and a projective ordered space P . The notation p ∈ X means that p ≤ X for p ∈ P (L) and X ∈ L. Recall that the join-irreducible elements of L are denoted by lower-case letters and the others are denoted by upper-case letters.
An important property of projective ordered spaces is the following.
Definition 63 (Regularity Axiom [10]). Let P be a projective ordered space and p, q, r ∈ P such that C(p, q, r). For all r ∈ P such that r ≤ r, r ≤ p, and r ≤ q, there exist p, q ∈ P such that p ≤ p, q ≤ q, and C(p, q, r).
Lemma 64 ( [10]). Let P be a projective ordered space and S, T ∈ L(P ) be the subspaces. Then, Based on these property, we can prove a useful lemma.
Lemma 65. Let L be a modular lattice and f : L → R be a downward DRsubmodular function. For all X, Y ∈ L and x ∈ adm(X) ∩ adm(X ∨ Y ), there exists x ′ ∈ adm(X) such that x = x ′ mod X, and for all x ′ ≤ x ′ with x ′ ∈ adm(Y ), we have the following: Proof. By the downward DR-submodularity, there exists w = x mod X ∨Y such that for all w ≤ w with w ∈ adm(Y ). By Lemma 64 and w ∈ (X∨Y )∨x = (X∨x)∨Y , at least one of the following holds: (1) w ∈ X ∨ x; (2) w ∈ Y ; (3) There exists x w ∈ X ∨ x and y w ∈ Y such that C(x w , y w , w).
In the case (1), x = w mod X ∨Y implies that w ∈ X. Therefore, w = x mod X and we can take x ′ as x ′ := w. Case (2) contradicts to the fact x = w mod X ∨Y . In case (3), we can take x ′ as (20) holds by the choice of w. Otherwise, x ′ ≤ y w because x ′ ∈ adm(Y ). Therefore, the regularity axiom (Definition 63) implies that there exist w ≤ w and y ≤ y w such that C(x ′ , w, y). In particular, x ′ = w mod Y . Therefore, (20) holds by the choice of w.

Proofs
Proof of Theorem 19. We first construct H ≥X as follows. Set H ←X. If there exists y ≤ Y such that y ∈ adm(H) and r(H ∨ y) = r(H), set H ← H ∨ y.
Continuing this process, the enlargement stops at some steps and we obtain a maximal H. This H has the following properties. First, H =X ∨ (Y ∧ H). Indeed, by construction, H =X ∨ y 1 ∨ y 2 ∨ · · · ∨ y l . Here, y i is the i-th y in the construction of H. Hence, we have H =X ∨ (Y ∧ H). Second, for all y ∈ adm(H) with y ∈ Y , we have r(H ∨ y) = r(H) + 1. Thirdly, x ∈ adm(H) and r(H ∨ x) = r(H) + 1 for all x ∈ adm(X) withX ∨ x = X. Indeed, if x ≤ H, then H ≥X ∨ x = X and r(X) = r(X) + 1. We next take w. Let x ≤ X be some join-irreducible element withX ∨x = X. Because r(H ∨x)−r(H) = 1 and H =X ∨(Y ∧H), Lemma 65 implies that there exist w ∈ adm(H) such that w = x modX and r(( We finally take y and v. Let y be any y ≤ y such that y ∈ adm(H).
Proof of Proposition 20. Let X ≤ Y ∈ L and B 1 , B 2 ∈ B with B 1 ≥ X and B 2 ≤ Y . We prove (B2) by the induction on k := |B 1 | − |B 1 ∧ Y |. If k = 0, then B 1 ≤ Y and the statement trivially holds. Consider the case of k > 0. Apply Theorem 19 to B 1 , B 2 , and arbitraryX with B 1 ∧ Y ≤X ≺ B 1 . Here,X ≥ X. Then, we obtain B ′ 1 ∈ B such that |B ′ 1 | − |B ′ 1 ∧ Y | = k − 1 and B ′ 1 ≥ X. By applying an induction hypothesis to X ≤ B ′ 1 and Y ≥ B 2 , we have the following statement.
Proof of Theorem 24. We prove that, for each t, the solution X t maximizes f among all elements in L whose height is t by the induction on t. The case t = 0 is trivial. For t ≥ 1, let O t be the optimal solution of height t such that |O t ∧X t | is maximum. If X t = O t , then where we obtain X t−1 ∨ b and O ′ t by applying the definition of the valuated supermatroid for (X t , X t−1 , O t ). Because the greedy property of the algorithm implies that w(X t−1 ∨ a t ) ≥ w(X t−1 ∨ b), we have O ′ t as an optimal solution. However, |X t ∧ O ′ t | > |X t ∧ O t |, it contradicts the choice of O t . Therefore, we have X t = O t .
we have proven that ω is a valuated supermatroid.
To prove Theorem 27, we need the following lemmas.
Lemma 66. Suppose that L is an atomic modular lattice. Let X, O ∈ B. In addition, let X ∧ O = Z 0 ≺ Z 1 ≺ · · · ≺ Z α = X be any chain. Then, we can take a chain X ∧ O = Y 0 ≺ Y 1 ≺ · · · ≺ Y α = O that satisfies the following condition: For all i = 1, 2, . . . , α, there exists y i such that Y i = Y i−1 ∨ y i and Z i−1 ∨ y i ∈ I.
Lemma 67. Suppose that L is an atomic modular lattice. Let X, O ∈ B. Let ⊥= X 0 ≺ X 1 ≺ · · · ≺ X k = X be any chain. Then, we can take a chain X ∧ O = Y 0 ≺ Y 1 ≺ · · · ≺ Y α = O that satisfies the following condition: For all i = 1, 2, . . . , α, there exists y i and j i ∈ [k] such that Y i = Y i−1 ∨ y i and X ji ∨ y i ∈ I. Furthermore, j i is injective with respect to i.
Proof. For any i ∈ [k], one of the following holds: If the latter case holds, then we can take o i ∈ O such that X i = X i−1 ∨ o i . Otherwise, we take x i ∈ X \ O such that X i = X i−1 ∨ x i . Then, we have X = (o m1 ∨ o m1 ∨ · · · ∨ o m β ) ∨ (x n1 ∨ x n2 ∨ · · · ∨ x nα ). Notice that X ∧ O = (o m1 ∨ o m1 ∨ · · · ∨ o m β ) and β = k − α. By using {x ni } i=1,2,...,α , we construct a chain X ∧ O = Z 0 ≺ Z 1 ≺ . . . Z α = X as Z i = (X ∧ O) ∨ x n1 ∨ x n2 ∨ · · · ∨ x ni . By using Lemma 66 for {Z i } i=1,2,,α , we can take a desired chain If we use the downward DR-submodularity instead of the strong DR-submodularity, we obtaine for some v i = w i mod W i . However, such v i might not satisfy X ji ∨ v i ∈ I, which is necessary for the next boundby the greedy property.
Proof of Theorem 29. We prove this theorem through an induction on k. The case k = 1 is trivial. Consider k > 1. Let X i be the output of the greedy algorithm after the i-th iteration, and a i be the chosen element, that is, X i = X i−1 ∨ a i . Let X * be the optimal solution. By (I2), there exists w ≤ X * such that X i−1 ∨ w is feasible. By greedy property and curvature, we have the following: where w ≤ w is a minimal element. By upward DR-submodularity, there exists X * ≺ X * such that By the induction hypothesis, (1 − c)f (X * ) ≤ f (X k−1 ). Therefore, Hence, X k is a (1-c)-approximation solution.