{'fraction_non_alphanumeric': 0.05544297789218103, 'fraction_numerical': 0.010588385636307209, 'mean_word_length': 3.704801168083827, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 19, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Secretary Problems with Convex Costs

We consider online resource allocation problems where given a set of requests our goal is to select a subset that maximizes a value minus cost type of objective function. Requests are presented online in random order, and each request possesses an adversarial value and an adversarial size. The online algorithm must make an irrevocable accept/reject decision as soon as it sees each request. The"profit"of a set of accepted requests is its total value minus a convex cost function of its total size. This problem falls within the framework of secretary problems. Unlike previous work in that area, one of the main challenges we face is that the objective function can be positive or negative and we must guard against accepting requests that look good early on but cause the solution to have an arbitrarily large cost as more requests are accepted. This requires designing new techniques. We study this problem under various feasibility constraints and present online algorithms with competitive ratios only a constant factor worse than those known in the absence of costs for the same feasibility constraints. We also consider a multi-dimensional version of the problem that generalizes multi-dimensional knapsack within a secretary framework. In the absence of any feasibility constraints, we present an O(l) competitive algorithm where l is the number of dimensions; this matches within constant factors the best known ratio for multi-dimensional knapsack secretary.


Introduction
We study online resource allocation problems under a natural profit objective: a single server accepts or rejects requests for service so as to maximize the total value of the accepted requests minus the cost imposed by them on the system. This model captures, for example, the optimization problem faced by a cloud computing service accepting jobs, a wireless access point accepting connections from mobile nodes, or an advertiser in a sponsored search auction deciding which keywords to bid on. In many of these settings, the server must make accept or reject decisions in an online fashion as soon as requests are received without knowledge of the quality future requests. We design online algorithms with the goal of achieving a small competitive ratio-ratio of the algorithm's performance to that of the best possible (offline optimal) solution.
A classical example of online decision making is the secretary problem. Here a company is interested in hiring a candidate for a single position; candidates arrive for interview in random order, and the company must accept or reject each candidate following the interview. The goal is to select the best candidate as often as possible. What makes the problem challenging is that each interview merely reveals the rank of the candidate relative to the ones seen previously, but not the ones following. Nevertheless, Dynkin [11] showed that it is possible to succeed with constant probability using the following algorithm: unconditionally reject the first 1/e fraction of the candidates; then hire the next candidate that is better than all of the ones seen previously. Dynkin showed that as the number of candidates goes to infinity, this algorithm hires the best candidate with probability approaching 1/e and in fact this is the best possible.
More general resource allocation settings may allow picking multiple candidates subject to a certain feasibility constraint. We call such a problem a generalized secretary problem (GSP) and use (Φ, F) to denote an instance of the problem. Here F denotes a feasibility constraint that the set of accepted requests must satisfy (e.g. the size of the set cannot exceed a given bound), and Φ denotes an objective function that we wish to maximize. As in the classical setting, we assume that requests arrive in random order; the feasibility constraint F is known in advance but the quality of each request, in particular its contribution to Φ, is only revealed when the request arrives. Recent work has explored variants of the GSP where Φ is the sum over the accepted requests of the "value" of each request. For such a sum-of-values objective, constant factor competitive ratios are known for various kinds of feasibility constraints including cardinality constraints [17,19], knapsack constraints [4], and certain matroid constraints [5].
In many settings, the linear sum-of-values objective does not adequately capture the tradeoffs that the server faces in accepting or rejecting a request, and feasibility constraints provide only a rough approximation. Consider, for example, a wireless access point accepting connections. Each accepted request improves resource utilization and brings value to the access point. However as the number of accepted requests grows the access point performs greater multiplexing of the spectrum, and must use more and more transmitting power in order to maintain a reasonable connection bandwidth for each request. The power consumption and its associated cost are non-linear functions of the total load on the access point. This directly translates into a value minus cost type of objective function where the cost is an increasing function of the load or total size of all the requests accepted.
Our goal then is to accept a set A out of a universe U of requests such that the "profit" π(A) = v(A) − C(s(A)) is maximized; here v(A) is the total value of all requests in A, s(A) is the total size, and C is a known increasing convex cost function 1 .
Note that when the cost function takes on only the values 0 and ∞ it captures a knapsack constraint, and therefore the problem (π, 2 U ) (i.e. where the feasibility constraint is trivial) is a generalization of the knapsack secretary problem [4]. We further consider objectives that generalize the ℓ-dimensional knapsack secretary problem. Here, we are given ℓ different (known) convex cost functions C i for 1 ≤ i ≤ ℓ, and each request is endowed with ℓ sizes, one for each dimension. The profit of a set is given by π(A) = v(A) − ℓ i=1 C i (s i (A)) where s i (A) is the total size of the set in dimension i. We consider the profit maximization problem under various feasibility constraints. For single-dimensional costs, we obtain online algorithms with competitive ratios within a constant factor of those achievable for a sum-of-values objective with the same feasibility constraints. For ℓ-dimensional costs, in the absence of any constraints, we obtain an O(ℓ) competitive ratio. We remark that this is essentially the best approximation achievable even in the offline setting: Dean et al. [9] show an Ω(ℓ 1−ǫ ) hardness for the simpler ℓ-dimensional knapsack problem under a standard complexity-theoretic assumption. For the multi-dimensional problem with general feasibility constraints, our competitive ratios are worse by a factor of O(ℓ 5 ) over the corresponding versions without costs. Improving this factor is a possible avenue for future research.
We remark that the profit function π is a submodular function. Recently several works [13,6,16] have looked at secretary problems with submodular objective functions and developed constant competitive algorithms. However, all of these works make the crucial assumption that the objective is always nonnegative; it therefore does not capture π as a special case. In particular, if Φ is a monotone increasing submodular function (that is, if adding more elements to the solution cannot decrease its objective value), then to obtain a good competitive ratio it suffices to show that the online solution captures a good fraction of the optimal solution. In the case of [6] and [16], the objective function is not necessarily monotone. Nevertheless, nonnegativity implies that the universe of elements can be divided into two parts, over each of which the objective essentially behaves like a monotone submodular function in the sense that adding extra elements to a good subset of the optimal solution does not decrease its objective function value. In our setting, in contrast, adding elements with too large a size to the solution can cause the cost of the solution to become too large and therefore imply a negative profit, even if the rest of the elements are good in terms of their value-size tradeoff. As a consequence we can only guarantee good profit when no "bad" elements are added to the solution, and must ensure that this holds with constant probability. This necessitates designing new techniques.
Our techniques. In the absence of feasibility constraints (see Section 3), we note that it is possible to classify elements as "good" or "bad" based on a threshold on their value to size ratio (a.k.a. density) such that any large enough subset of the good elements provides a good approximation to profit; the optimal threshold is defined according to the offline optimal fractional solution. Our algorithm learns an estimate of this threshold from the first few elements (that we call the sample) and accepts all the elements in the remaining stream that cross the threshold. Learning the threshold from the sample is challenging. First, following the intuition about avoiding all bad elements, our estimate must be conservative, i.e. exceed the true threshold, with constant probability. Second, the optimal threshold for the sample can differ significantly from the optimal threshold for the entire stream and is therefore not a good candidate for our estimate. Our key observation is that the optimal profit over the sample is a much better behaved random variable and is, in particular, sufficiently concentrated; we use this observation to carefully pick an estimate for the density threshold.
With general feasibility constraints, it is no longer sufficient to merely classify elements as good and bad: an arbitrary feasible subset of the good elements is not necessarily a good approximation. Instead, we decompose the profit function into two parts, each of which can be optimized by maximizing a certain sumof-values function (see Section 4). This suggests a reduction from our problem to two different instances of the GSP with sum-of-values objectives. The catch is that the new objectives are not necessarily nonnegative and so previous approaches for the GSP don't work directly. We show that if the decomposition of the profit function is done with respect to a good density threshold and an extra filtering step is applied to weed out bad elements, then the two new objectives on the remaining elements are always non-negative and admit good solutions. At this point we can employ previous work on GSP with a sum-of-values objective to obtain a good approximation to one or the other component of profit. We note that while the exposition in Section 4 focuses on a matroid feasibility constraint, the results of that section extend to any downwardsclosed feasibility constraint that admits good offline and online algorithms with a sum-of-values objective 2 .
In the multi-dimensional setting (discussed in Section 5), elements have different sizes along different dimensions. Therefore, a single density does not capture the value-size tradeoff that an element offers. Instead we can decompose the value of an element into ℓ different values, one for each dimension, and define densities in each dimension accordingly. This decomposes the profit across dimensions as well. Then, at a loss of a factor of ℓ, we can approximate the profit objective along the "best" dimension. The problem with this approach is that a solution that is good (or even best) in one dimension may in fact be terrible with respect to the overall profit, if its profit along other dimensions is negative. Surprisingly we show that it is possible to partition values across dimensions in such a way that there is a single ordering over elements in terms of their value-size tradeoff that is respected in each dimension; this allows us to prove that a solution that is good in one dimension is also good in other dimensions. We present an O(ℓ) competitive algorithm for the unconstrained setting based on this approach in Section 5, and defer a discussion of the constrained setting to Section 6.
Related work. The classical secretary problem has been studied extensively; see [14,15] and [23] for a survey. Recently a number of papers have explored variants of the GSP with a sum-of-values objective. Hajiaghayi et al. [17] considered the variant where up to k secretaries can be selected (a.k.a. the k-secretary problem) in a game-theoretic setting and gave a strategyproof constant-competitive mechanism. Kleinberg [19] later showed an improved 1 − O(1/ √ k) competitive algorithm for the classical setting. Babaioff et al. [4] generalized this to a setting where different candidates have different sizes and the total size of the selected set must be bounded by a given amount, and gave a constant factor approximation. In [5] Babaioff et al. considered another generalization of the k-secretary problem to matroid feasibility constraints. A matroid is a set system over U that is downwards closed (that is, subsets of feasible sets are feasible), and satisfies a certain exchange property (see [21] for a comprehensive treatment). They presented an O(log r) competitive algorithm, where r is the rank of the matroid, or the size of a maximal feasible set. This was subsequently improved to a O( √ log r)-competitive algorithm by Chakraborty and Lachish [7]. Several papers have improved upon the competitive ratio for special classes of matroids [1,10,20]. Bateni et al. [6] and Gupta et al. [16] were the first to (independently) consider non-linear objectives in this context. They gave online algorithms for non-monotone nonnegative submodular objective functions with competitive ratios within constant factors of the ratios known for the sum-of-values objective under the same feasibility constraint. Other versions of the problem that have been studied recently include: settings where elements are drawn from known or unknown distributions but arrive in an adversarial order [8,18,22], versions where values are permuted randomly across elements of a non-symmetric set system [24], and settings where the algorithm is allowed to reverse some of its decisions at a cost [2,3].

Notation and Preliminaries
We consider instances of the generalized secretary problem represented by the pair (π, F), and an implicit number n of requests or elements that arrive in an online fashion. U denotes the universe of elements. F ⊂ 2 U is a known downwards-closed feasibility constraint. Our goal is to accept a subset of elements A ⊂ U with A ∈ F such that the objective function π(A) is maximized. For a given set T ⊂ U , we use O * (T ) = argmax A∈F ∩2 T π(A) to denote the optimal solution over T ; O * is used as shorthand for O * (U ). We now describe the function π.
In the single-dimensional cost setting, each element e ∈ U is endowed with a value v(e) and a size s(e). Values and sizes are integral and are a priori unknown. The size and value functions extend to sets of elements as s(A) = e∈A s(e) and v(A) = e∈A v(e). Then the "profit" of a subset is given by where C is a non-decreasing convex function on size: C : Z + → Z + . The following quantities will be useful in our analysis: • The density of an element, ρ(e) := v(e)/s(e). We assume without loss of generality that densities of elements are unique and denote the unique element with density γ by e γ .
• The marginal cost function, c(s) := C(s) − C(s − 1). Note that this is an increasing function.
• The inverse marginal cost function,s(ρ) which is defined to be the maximum size for which an element of density ρ will have a non-negative profit increment, that is, the maximum s for which ρ ≥ c(s).
• The density prefix for a given density γ and a set T , P T γ := {e ∈ T : ρ(e) ≥ γ}, and the partial density prefix,P T γ := P T γ \ {e γ }. We use P γ andP γ as shorthand for P U γ andP U γ respectively.
We will sometimes find it useful to discuss fractional relaxations of the offline problem of maximizing π subject to F. To this end, we extend the definition of subsets of U to allow for fractional membership. We use αe to denote an α-fraction of element e; this has value v(αe) = αv(e) and size s(αe) = αs(e). We say that a fractional subset A is feasible if its support supp(A) is feasible. Note that when the feasibility constraint can be expressed as a set of linear constraints, this relaxation is more restrictive than the natural linear relaxation.
Note that since costs are a convex non-decreasing function of size, it may at times be more profitable to accept a fraction of an element rather than the whole. That is, argmax α π(αe) may be strictly less than 1. For such elements, ρ(e) < c(s(e)). We use F to denote the set of all such elements: F = {e ∈ U : argmax α π(αe) < 1}, and I = U \ F to denote the remaining elements. Our solutions will generally approximate the optimal profit from F by running Dynkin's algorithm for the classical secretary problem; most of our analysis will focus on I. Let F * (T ) denote the optimal (feasible) fractional subset of T ∩ I for a given set T . Then π(F * (T )) ≥ π(O * (T ∩ I)). We use F * as shorthand for F * (U ), and let s * be the size of this solution.
In the multi-dimensional setting each element has an ℓ-dimensional size s(e) = (s 1 (e), . . . , s ℓ (e)). The cost function is composed of ℓ different non-decreasing convex functions, C i : Z + → Z + . The cost of a set of elements is defined to be C(A) = i C i (s i (A)) and the profit of A, as before, is its value minus its cost:

Balanced Sampling
Our algorithms learn the distribution of element values and sizes by observing the first few elements. Because of the random order of arrival, these elements form a random subset of the universe U . The following concentration result is useful in formalizing the representativeness of the sample. Lemma 2.1. Given constant c ≥ 3 and a set of elements I with associated non-negative weights, w i for i ∈ I, say we construct a random subset J by including each element of I uniformly at random with probability 1/2. If for all k ∈ I, w k ≤ 1 c i∈I w i then the following inequality holds with probability at least 0.76: where β(c) is a non-decreasing function of c (and furthermore is independent of I).
We begin the proof of Lemma 2.1 with a restatement of Lemma 1 from [12] since it plays a crucial role in our argument. Note that we choose a different parameterization than they do, since in our setting the balance between approximation ratio and probability of success is different. We now proceed to prove Lemma 2.1. While we do not give a closed form for the approximation factor β(c) in the statement of the lemma, we define it implicitly as and give explicit values in Table 1 for particular values of c that we invoke the lemma with.
Proof of Lemma 2.1. Our general approach will be to separate our set of weights I into a "good" set G and a "bad" set B. At a high level, Lemma 2.2 guarantees us that at worst, we will accept a weight every third time we flip a coin. So the good case is when weights do not decrease too quickly; this intuition guides our definitions of G and B.
Let y ∈ (0, 1) be a lower bound on "acceptable" rates of decrease; we tune the exact value later. Throughout, we use w(S), w(S), and w(S) to denote the total, minimum, and maximum weights of a set S. We form G and B as follows.
Initialize B = ∅ and i = 1. Consider I in order of decreasing weight. While I = ∅, we repeat the following. Let P be the largest prefix such that w(P ) ≥ y · w(P ). If |P | ≤ 2, move P from I to B, i.e. set B := B ∪ P and I := I \ P . Otherwise, |P | ≥ 3 and we define G i to be the 3 largest elements of P ; remove them from I (i.e. set I := I \ G i ); and increment i by 1. Once we are done, we define G = ∪ i G i .
First, we show that the total weight in B cannot be too large. Note that we add at most 2 elements at a time to B; and when we do add elements, we know that all remaining elements in I (and hence all later additions to B) are smaller by more than a factor of y. Thus, we can see that by our assumption that no individual weight is more than w(I)/c. Next, we show that with probability at least 0.76, we can lower bound the fraction of weight we keep from G. Consider applying Lemma 2.2, flipping coins first for the weights in G in order by decreasing weight. Note that by the time we finish flipping coins for G i , we must have added at least i weights to J; hence the i th weight we add to J must have value at least w(G i ). On the other hand, we know that and so summing over i we can see that elements we accept have total weight w(J) ≥ ( y 2+y )w(G). Combining our bounds for the weights of G and B, we can see that with probability 0.76 the elements we accept have weight optimizing the above with respect to y for a fixed c gives the claimed result. Note that for each fixed y ∈ (0, 1) our approximation factor is increasing in c, and so the optimal value β(c) must be increasing in c as well.

Unconstrained Profit Maximization
We begin by developing an algorithm for the unconstrained version of the generalized secretary problem with F = 2 U , which already exhibits some of the challenges of the general setting. Note that this setting captures as a special case the knapsack secretary problem of [4] where the goal is to maximize the total value of a subset of size at most a given bound. In fact in the offline setting, the generalized secretary problem is very similar to the knapsack problem. If all elements have the same (unit) size, then the optimal offline algorithm orders elements in decreasing order of value and picks the largest prefix in which each element contributes a positive marginal profit. When element sizes are different, a similar approach works: we order elements by density this time, and note that either a prefix of this ordering or a single element is a good approximation (much like the greedy 2-approximation for knapsack).

Algorithm 1
Offline algorithm for single-dimensional (π, 2 U ) Precisely, we show that |O * ∩ F | ≤ 1, and we can therefore focus on approximating π over the set I. Furthermore, let A(U ) denote the greedy subset obtained by Algorithm 1, which considers elements in I in decreasing order of density and picks the largest prefix where every element has nonnegative marginal profit. The following lemma implies that one of A(U ) or the single best element is a 3-approximation to O * . Lemma 3.1. We have that π(O * ) ≤ π(F * ) + max e∈U π(e) ≤ π(A(U )) + 2 max e∈U π(e). Therefore the greedy offline algorithm (Algorithm 1) achieves a 3-approximation for (π, 2 U ).
Proof. We first show that O * has at most one element from F. For contradiction, assume that O * contains at least two elements f 1 , f 2 ∈ F. Since densities are unique, without loss of generality, we assume ρ(f 1 ) > ρ(f 2 ).
Recall that F is precisely the set of elements for which it is optimal to accept a strictly fractional amount. Let α 1 , α 2 < 1 be the optimal fractions for f 1 and f 2 , i.e. argmax α π(αf 1 ) = α 1 and argmax α π(αf 2 ) = α 2 . Then adding a fractional amount of any element with density at most ρ(f 1 ) to In the rest of the proof we focus on approximating π(F * ).
The offline greedy algorithm suggests an online solution as well. In the case where a single element gives a good approximation, we can use the classical secretary algorithm to get a good competitive ratio. In the other case, in order to get good competitive ratio, we merely need to estimate the smallest density, say ρ -, in the prefix of elements that the offline greedy algorithm picks, and then accept every element that exceeds this threshold.
We pick an estimate for ρby observing the first few elements of the stream U . Note that it is important for our estimate of ρto be no smaller than ρ -. In particular, if there are many elements with density just below ρ -, and our algorithm uses a density threshold less than ρ -, then the algorithm may be fooled into mostly picking elements with density below ρ -(since elements arrive in random order), while the optimal solution picks elements with densities far exceeding ρ -. We now describe how to pick an overestimate of ρwhich is not too conservative, that is, such that there is still sufficient profit in elements whose densities exceed the estimate.
In the remainder of this section, we assume that every element has profit at most 1 k 1 +1 π(O * ) for an appropriate constant k 1 , to be defined later. (If this does not hold, the classical secretary algorithm obtains an expected profit of at least . We divide the stream U into two parts X and Y , where X is a random subset of U . Our algorithm unconditionally rejects elements in X and extracts a density threshold τ from this set. Over the remaining stream Y , it accepts an element if and only if its density is at least τ and if it brings in strictly positive marginal profit. Under the assumption of small element profits we can apply Lemma 2.1 to show that π(X ∩A(U )) is concentrated and is a large enough fraction of π(O * ). This implies that with high probability π(X ∩ A(U )) (which is a prefix of A(X)) is a significant fraction of π(A(X)). Therefore we attempt to identify X ∩ A(U ) by looking at profits of prefixes of X.
We will need the following lemma about A().

Lemma 3.2. For any set S, consider subsets
. In other words, π is monotone-increasing when restricted to A(S) for all S ⊂ U .
Proof. We observe that the fractional greedy algorithm sorts its input S by decreasing order of density, and A(S) consists of the top |A(S)| elements under that ordering. Since F * (S) contains each element in A(S) Algorithm 2 Online algorithm for single-dimensional (π, 2 U ) 1: With probability 1/2 run the classic secretary algorithm to pick the single most profitable element else execute the following steps. 2: Draw k from Binomial(n, 1/2). 3: Select the first k elements to be in the sample X. Unconditionally reject these elements. 4: Let τ be largest density such that π(P X τ ) ≥ β 1 − 1 k 1 π(F * (X)) for constants β and k 1 to be specified later. 5 We define two good events. E 1 asserts that X ∩ A(U ) has high enough profit. Our final output is the set P Y τ . E 2 asserts that the profit of P Y τ is a large enough fraction of the profit of P τ . Recall that A(U ) is a density prefix, say P ρ -, and so X ∩ A(U ) = P X ρ -. We define the event E 1 as follows.
where β is a constant to be specified later. Conditioned on Note that threshold τ , as selected by Algorithm 2, is the largest density such that π(P X τ ) ≥ β (1 − 1/k 1 ) π(F * (X)). Therefore, E 1 implies τ ≥ ρ -, and we have the following lemma.
On the other hand, where the second inequality is by the definition of τ , the third by optimality and the last is obtained by applying We define ρ + to be the largest density such that π(P ρ + ) ≥ β 2 1 − 1 k 1 2 π(F * ). Then ρ + ≥ τ , which implies P ρ + ⊆ P τ and the following lemma.
Based on the above lemma, we define event E 2 for an appropriate constant β ′ as follows . Conditioned on events E 1 and E 2 , and using Lemma 3.2 again, we get To wrap up the analysis, we show that E 1 and E 2 are high probability events. In the following, we assume the elements are sorted in decreasing order of density. Denote the profit increment of the i th element byπ(i) = π(P (i) ) − π(P (i−1) ); this extends naturally to sets A ⊆ A(U ) by settingπ(A) = i∈Aπ (i). By the subadditivity of π, we have π(A) ≥π(A) for all A ⊆ A(U ), with equality at A(U ).
We apply Lemma 2.1 with P ρ -as the fixed set I and P X ρ -= U ∩P ρ -as the the random set J. The weights in Lemma 2.1 correspond to profit increments of the elements. Note that P ρ -= A(U ); so we know both that elements in P ρ -have non-negative profit increments, and π(P ρ -) ≥ π(O * ) − 2 max e∈U π(e). Hence if no element has profit exceeding a 1/113-fraction of π(O * ), we get that any element e i ∈ P ρ -has profit incrementπ(i) ≤ π(e i ) ≤ 1/(113 − 2)π(P ρ -) = 1/111π(P ρ -). Hence we can apply Lemma 2.1 to get π(P X ρ -) ≥ 0.262π(P ρ -) with probability at least 0.76, and so the event E 1 holds with probability at least 0.76.
By our definition of ρ + , the profit of P ρ + is at least ; substituting in the specified values of β and k 1 give us that no element in P ρ + has profit increment more than 2/15π(P ρ + ).
Putting everything together we get the following theorem. Theorem 3.6. Algorithm 2 achieves a competitive ratio of 616 for (π, 2 U ) using k 1 = 112 and β = 0.262.
Proof. If there exists an element with profit at least 1 113 π(O * (U )), the classical secretary algorithm (Step 1) gives a competitive ratio of 1 113e ≥ 1 308 . Otherwise, using Lemma 3.5, with Since we flip a fair coin to decide whether to output the result of running the classical secretary algorithm, or output the set O, we achieve a 2 max{308, 307} = 616-approximation to π(O * ) in expectation (over the coin flip).

Matroid-Constrained Profit Maximization
We now extend the algorithm of Section 3 to the setting (π, F) where F is a matroid constraint. In particular, F is the set of all independent sets of a matroid over U . We skip a precise definition of matroids and will only use the following facts: F is a downward closed feasibility constraint and there exist an exact offline and an O( √ log r) online algorithm for (Φ, F), where Φ is a sum-of-values objective and r is the rank of the matroid.
In the unconstrained setting, we showed that there always exists either a density prefix or a single element with near-optimal profit. So in the online setting it sufficed to determine the density threshold for a good prefix. In constrained settings this is no longer true, and we need to develop new techniques. Our approach is to develop a general reduction from the π objective to two different sum-of-values type objectives over the same feasibility constraint. This allows us to employ previous work on the (Φ, F) setting; we lose only a constant factor in the competitive ratio. We will first describe the reduction in the offline setting and then extend it to the online algorithm using techniques from Section 3.

Decomposition of π.
For a given density γ, we define the shifted density function h γ () over sets as h γ (A) := e∈A (ρ(e) − γ) s(e) and the fixed density function g γ () over sizes as g γ (s) := γs − C(s). For a set A we use g γ (A) to denote g γ (s(A)). It is immediate that for any density γ we can split the profit function as π(A) = h γ (A) + g γ (A). In particular π(O * ) = h γ (O * ) + g γ (O * ). Our goal will be to optimize the two parts separately and then return the better of them.
Note that the function h γ is a sum of values function where the value of an element is defined to be (ρ(e) − γ)s(e). Its maximizer is a subset of P γ , the set of elements with nonnegative shifted density ρ(e) − γ. In order to ensure that the maximizer, say A, of h γ also obtains good profit, we must ensure that g γ (A) is nonnegative, and therefore π(A) ≥ h γ (A). This is guaranteed for a set A as long as s(A) ≤s(γ).
Likewise, the function g γ increases as a function of size s as long as s is at mosts(γ), and decreases thereafter. Therefore, in order to maximize g γ , we merely need to find the largest (in terms of size) feasible subset of size no more thans(γ). As before, if we can ensure that for such a subset h γ is nonnegative (e.g. if the set is a subset of P γ ), then the profit of the set is no smaller than its g γ value. This motivates the following definition of "bounded" subsets: We begin by formally proving that the function g γ increases as a function of size s as long as s is at most s(γ).
Proof. Since C(·) is convex, we have that its marginal, c(), is monotonically non-decreasing. Thus we get the following chain of inequalities, The last inequality follows from the assumption that t is no more thans(γ) and hence c(t) ≤ γ. By definition of g γ () we get the desired claim. Proof. Since π(A) = h γ (A) + g γ (A), it is sufficient to prove that h γ (A) and g γ (A) are both non-negative. The former is clearly non-negative since all elements of A have density at least γ. Lemma 4.1 implies that the latter is non-negative by taking t = s(A) and s = 0.
For a density γ and set T we define H T γ and G T γ as follows. (We write H γ for H U γ and G γ for G U γ .) Following our observations above, both H γ and G γ can be determined efficiently (in the offline setting) using standard matroid maximization. However, we must ensure that the two sets are γ-bounded. Further, in order to compare the performance of G γ against O * , we must ensure that its size is at least a constant fraction of the size of O * . We now show that there exists a density γ for which H γ and G γ satisfy these properties.
Once again, we focus on the case where no single element has high enough profit by itself. Recall that F * denotes F * (I), s * denotes the size of this set andP γ denotes P γ \ {e γ }. Before we proceed we need the following fact about the fractional optimal subset F * .

Lemma 4.3.
If F * has an element of density γ then s * is at mosts(γ).
Proof. The proof is by contradiction. Say s * is more thans(γ). Recall that e γ denotes the element with density γ. We show that in such conditions reducing the fractional contribution of e γ , say by ǫ, increases profit giving us a better fractional solution. This is turn contradicts the optimality of F * .

Definition 4.2.
Let ρbe the largest density such that P ρ -has a feasible set of size at least s * .
We now state a useful property of ρ -.

Lemma 4.4.
Any feasible set inP ρ -is ρ --bounded and has size less than s * . Moreover for any density γ > ρall feasible subsets of P γ are γ-bounded.
Proof. By definition, the size of any feasible set contained in P ρ -\ {e ρ -} is no more than s * . We will show that s * ≤s(ρ -). Then the first part of the lemma follows immediately. For the second part we have γ > ρand hences(ρ -) ≤s(γ). Overall a size bound of s * also implies that feasible sets in P γ satisfy the size requirement for being γ-bounded. Hence we get that all feasible sets in P ρ -\ {e ρ -} are ρ --bounded and all feasible sets in P γ are γ-bounded.
The size of F * is at most the size of its support. Thus the support of F * is a feasible set of size at least s * . By definition, ρis the largest density such that P ρ -contains a feasible set of size s * . Hence we get that F * contains an element of density less than or equal to ρ -. Applying Lemma 4.3 we get s * ≤s(ρ -) and the lemma follows.
The following is our main claim of this section.
Proof. Let P , H, and G denote P ρ -, H ρ -, and G ρ -respectively. As in the unconstrained setting, there can be at most one element in the intersection of O * and F (see proof of Lemma 3.1). Note that π() is subadditive, hence π(O * ∩ I) + max e∈U π(e) ≥ π(O * ). In the analysis below we do not consider elements present in F and show that π(H) + π(G) + max e∈U π(e) ≥ π(O * ∩ I). This in turn establishes the second part of the Lemma.
For ease of notation we denote e ρ -as e ′ . Without loss of generality, we can assume that H does not contain e ′ since ρ(e ′ ) − ρ -= 0. Therefore set H is contained in P \ {e ′ }. By Lemma 4.4 we get that H is ρ --bounded.
Note that by definition G does not contain e ′ , hence its size is at most s * . Also, G∪{e ′ } is no smaller than the maximum-size feasible subset contained in P . So, by definition of ρ -, we also have s(G) + s(e ′ ) ≥ s * . Thus there exists α < 1 such that the fractional set F = G ∪ {αe ′ } has size exactly equal to s * .
Next we split the profit of F * into two parts, and bound the first by h ρ -(H) and the second by g ρ -(F ):

Note that we can drop elements which have a negative contribution to the sum to get
The second inequality follows since we can only increase the value of a subset by "rounding up" fractional elements. The third inequality follows from the optimality of H, and the fourth from the fact that it is ρ --bounded.
The first half of the lemma follows along similar lines. We have the standard decomposition, π(O * (P γ )) = h γ (O * (P γ ))+g γ (O * (P γ )). By definition, H γ is the constrained maximizer of h γ , hence we get h γ (O * (P γ )) ≤ h γ (H γ ). We note that all feasible sets in P γ are γ-bounded, for density γ > ρ -(Lemma 4.4). Hence, by Lemma 4.1, g γ strictly increases with size when restricted to feasible sets inP γ . G γ is the largest such set, hence we get g γ (G γ ) ≥ g γ (O * (P γ )). H γ and G γ are γ-bounded and hence by Proposition 4.2 we have π(H γ ) ≥ h γ (H γ ) and π(G γ ) ≥ g γ (G γ ). This establishes the lemma. This lemma immediately gives us an offline approximation algorithm for (π, F): for every element density γ, we find the sets H γ and G γ ; we then output the best (in terms of profit) of these sets or the best individual element. We obtain the following theorem: Theorem 4.6. Algorithm 3 4-approximates (π, F) in the offline setting.

Algorithm 3
Offline algorithm for single-dimensional (π, F) 1: Set A max ← argmax H∈{Hγ }γ π(H) 2: Set B max ← argmax G∈{Gγ }γ π(G) 3: Set e max ← argmax e∈U π(e) 4: Assign A(U ) ← argmax S∈{Amax ,Bmax ,emax } π(S) The online setting. Our online algorithm, as in the unconstrained case, uses a sample X from U to obtain an estimate τ for the density ρ -. Then with equal probability it applies the online algorithm for (h τ , F) on the remaining set Y ∩ P τ or the online algorithm for (s, F) (in order to maximize g τ ) on Y ∩ P τ . Lemma 4.5 indicates that it should suffice for τ to be larger than ρwhile ensuring that π(O * (P τ )) is large enough. As in Section 3 we define the density ρ + as the upper limit on τ , and claim that τ satisfies the required properties with high probability.

Algorithm 4
Online algorithm for single-dimensional (π, F) 1: Draw k from Binomial(n, 1/2). 2: Select the first k elements to be in the sample X. Unconditionally reject these elements. 3: Toss a fair coin. 4: if Heads then 5: Set output O as the first element, over the remaining stream, with profit higher than max e∈X π(e). 6: else 7: Determine A(X) using the offline Algorithm 3.

9:
Toss a fair coin. 10: if Heads then       Note that we use an algorithm for (Φ, F) where Φ is a sum-of-values objective in Algorithm 4 as a black box. For example if the underlying feasibility constraint is a partition matroid we execute the partitionmatroid secretary algorithm in steps 11 and 20 as subroutines. Since these subroutines are online algorithms, we can execute steps 11 and 20 in parallel with the respective 'for' loops in steps 13 and 22. This ensures that all accepted elements have positive profit increment.
Proof. We first define two events analogous to the events E 1 and E 2 in Section 3.
We claim that the event ). This inequality, when combined with event E 2 and the definition of ρ + , proves the second condition. We furthermore claim that E 1 and E 2 simultaneously hold with probability at least k 2 , which would give the desired result.
Thus, we are done if we demonstrate that event E 1 implies ρ + ≥ τ ≥ ρ -, and that the probability of E 1 and E 2 occurring simultaneously is at least k 2 ; we now proceed to prove each of these claims in turn.
We fix an ordering over elements of O * (P ρ -), such that the profit increments are non-increasing. That is, if L i is the set containing elements 1 through i and hence the profit increment of the ith element is π(i) := π(L i ) − π(L i−1 ), then we haveπ(1) ≥π(2) ≥ . . .. Note that such an ordering can be determined by greedily picking elements from O * (P ρ -) such that the profit increment at each step is maximized.
We set k 1 ≥ 24, now the fact that no element in S has profit more than 1 24 π(O * ) implies no element by itself has profit more than 1/8 π(O * (P ρ -)), since π(O * (P ρ -)) ≥ 1/3π(O * ). Profit increments of elements are upper bounded by their profits, therefore we can apply Lemma 2.1 with O * (P ρ -) as the fixed set and profit increments as the weights. By optimality of O * (P ρ -) we have that these profit increments are nonnegative hence the required conditions of Lemma 2.1 hold and we have π With the demonstration that the above three claims hold, our proof is complete.
To conclude the analysis, we show that if the online algorithms for (h τ , F) and (s, F) have a competitive ratio of α, then we obtain an O(α) approximation to π(O * (P Y τ )). We therefore get the following theorem. Before we proceed to prove Theorem 4.8, we show that in steps 9 to 27 the algorithm obtains a good approximation to O * (P Y τ ).

Lemma 4.9. Suppose that there is an α-competitive algorithm for (Φ, F) where Φ is any sum-of-values objective. For a fixed set Y and threshold
Proof. The threshold τ is either equal to or strictly greater than ρ -. In the former case e ρ -must have been in the sample set X By applying the α-competitive matroid secretary algorithm with objective h τ (Step 11 of Algorithm 4 ) we get where the second inequality follows from the optimality of H Y τ . Next we bound E σ [g τ (O 2 )]. Let K be the largest feasible subset contained in P Y τ . The fact that the underlying algorithm is α- Note that, as observed above, P Y τ ⊂P ρ -. Since K ⊂ P Y τ , by definition of ρwe get that s(K) ≤ s * . So, for O 2 we have Since s(O * (P Y τ )) ≤ s(K) ≤ s * ≤s(τ ) we get the last inequality by applying Lemma 4.1. The conclusion of the lemma now follows from the decomposition Proof of Theorem 4.8. With probability 1 2 we apply the standard secretary algorithm which is e-competitive. If an element has profit more than 1 k 1 π(O * ), in expectation we get a profit of 1 2k 1 e times the optimal. We have Pr[E 1 ∧ E 2 ] ≥ k 2 , for a fixed constant k 2 . Also, the events E 1 and E 2 depend only on what elements are in X and Y , and not on their ordering in the stream. So conditioned on E 1 and E 2 , the remaining stream is still a uniformly random permutation of Y . Therefore, if no element has profit more than 1 k 1 π(O * ) we can apply the second inequality of Lemma 4.7 and Lemma 4.9 along with the fact that we output O 1 and O 2 with probability 1 4 each, to show that Overall, we have that Since all the involved parameters are fixed constants we get the desired result.

Multi-dimensional Profit Maximization
In this section, we consider the GSP with a multi-dimensional profit objective. Recall that in this setting each element e has ℓ different sizes s 1 (e), . . . , s ℓ (e), and the cost of a subset is defined by ℓ different convex functions C 1 , . . . , C ℓ . The profit function is defined as π(A) = v(A) − i C i (s i (A)).
As in the single-dimensional setting, we partition U into two sets I and F with F = {e ∈ U : argmax α π(αe) < 1}. We first claim that, as before, an optimal solution cannot contain too many elements of F.
Proof. Suppose, towards a contradiction, that |O * ∩ F | ≥ ℓ + 1.  We therefore focus on approximating π over I and devote this section to the unconstrained problem (π, 2 U ).
The main challenge of this setting is that we cannot summarize the value-size tradeoff that an element provides by a single density because the element can be quite large in one dimension and very small in another. Our high level approach is to distribute the value of each element across the ℓ dimensions, thereby defining densities and decomposing profit across dimensions appropriately. We do this in such a way that a maximizer of the ith dimensional profit for some dimension i gives us a good overall solution (albeit at a cost of a factor of ℓ).
Formally, let ρ : U → R ℓ denote an ℓ-dimensional vector function ρ(e) = (ρ 1 (e), . . . , ρ ℓ (e)) that satisfies i ρ i (e)s i (e) = v(e) for all e. We set v i (e) = ρ i (e)s i (e) and π i (A) = v i (A) − C i (s i (A)) and note that π(A) = i π i (A). Let F * i denote the maximizer of π i over I. Then, π(F * ) ≤ i π i (F * i ). Given this observation, it is natural to try to obtain an approximation to π by solving for F * i for all i and rounding the best one. This does not immediately work: even if π i (F * i ) is very large, π(F * i ) could be negative because of the profit of the set being negative in other dimensions. We will now describe an approach for defining and finding density vectors such that the best set F * i indeed gives an O(ℓ) approximation to O * (I). We first define a quantity Π i (γ i ) which bounds the ith dimensional profit that can be obtained by any set with elements of ith density at most γ i : In order to obtain a uniform bound on the profits π j (F * j ), we restrict density vectors as follows. We call a vector ρ(e) proper if it satisfies the following properties: (P2) Π i (ρ i (e)) = Π j (ρ j (e)) for all i, j ∈ [1, ℓ]; we denote this quantity by Π(e).
The following lemma is proved in Section 5.1.

Lemma 5.3. For every element e, a unique proper density vector exists and can be found in polynomial time.
Finally, we note that proper density vectors induce a single ordering over elements. In particular, since the Π i s are monotone, ρ i (e) ≥ ρ i (e ′ ) if and only if Π(e) ≥ Π(e ′ ). We order the elements e 1 , . . . , e n in decreasing order of Π. Note that each F * i is a (fractional) prefix of this sequence. Let F * 1 be the shortest prefix. Let A = {e 1 , . . . , e k 1 } denote the integral part of F * 1 and e ′ = e k 1 +1 (i.e., F * 1 's unique fractional element if it exists).
First, we need the following fact about F * 1 . It implies that the multidimensional profit function π is monotone when restricted to subsets of F * 1 .
The conclusion now follows from the fact we are considering only elements from I and π(F * ) = i π i (F * ) ≤ i π i (F * i ).
The online setting. Note that proper densities essentially define a 1-dimensional manifold in ℓ-dimensional space. We can therefore hope to apply our online algorithm from Section 3 to this setting. However, there is a caveat: the algorithm from Section 3 uses the offline algorithm as a subroutine on the sample X to estimate the threshold τ ; naïvely replacing the subroutine by the O(ℓ) approximation described above leads to an O(ℓ 2 ) competitive online algorithm 3 . In order to improve the competitive ratio to O(ℓ) we need to pick the threshold τ more carefully.

Algorithm 5
Online algorithm for multi-dimensional (π, 2 U ) 1: With probability 1/2 run the classic secretary algorithm to pick the single most profitable element else execute the following steps. 2: Draw k from Binomial(n, 1/2). 3: Select the first k elements to be in the sample X. Unconditionally reject these elements. 4: Let τ be largest density such that e τ ∈ X satisfies π(P X τ ) + π(e τ ) ≥ β 2 π i (F * i (X)) for all i, for a constant β. We define τ to be the largest density with e τ ∈ X such that for an appropriate constant β, π(P X τ ) + π(e τ ) ≥ β 2 π i (F * i (X)) for all i. For a set T , let F * i (T ) denote the maximizer of π i over T ∩ I and let P * (T ) = ∩ i F * i (T ) denote the shortest of these prefixes. Recall that P * (U ) = F * 1 . Let ρdenote the smallest density in F * 1 . That is, F * 1 = P * (P ρ -). Our analysis relies on the following two events: E 1 implies the following sequence of inequalities; here the second inequality follows from Lemma 5.5.
This implies τ ≥ ρ -. Formally, we have the following claim.
Summing over all dimensions and applying event E ′ 1 gives us So if we define ρ + to be the highest density such that π(P ρ + ) + π(e ρ + ) ≥ ββ ′′ 2ℓ π(O * ), then we get ρ + ≥ τ . Then, as before we can define the event E 2 in terms of ρ + to conclude that π(P Y τ ) is large enough. Formally, we define E 2 for some fixed constant β ′ as follows.
Since P Y ρ + ⊂ P Y τ ⊂P τ ⊂ A, applying Claim 5.4, we have π(O) = π(P Y τ ) ≥ π(P Y ρ + ). Therefore, conditioning on events E 1 , E ′ 1 and E 2 , we get To wrap up the analysis, we argue that the probability of these events is bounded from below by a constant. Using Lemma 2.1 as in the proof of Lemma 3.5 , if no element has profit at least 1 ℓk 3 π(O * ), then events E 1 , E ′ 1 and E 2 each occur with probability at least 0.76. Using a union bound, we have that 28. This proves the following lemma.
Via a similar argument as for Theorem 3.6, we get Theorem 5.9. Algorithm 5 is O(ℓ) competitive for (π, 2 U ) where π is a multi-dimensional profit function.

Computing Proper Densities
In this subsection, we show that proper ρ's exist and can be efficiently computed. To do this, we make the following assumptions about the marginal cost functions: (A1) The marginal cost functions c j (·) are unbounded.
(A2) They satisfy c j (s j (U )) > max e∈U v(e) for all i.
Note that these assumptions do not affect C i (t) for sizes t ≤ s i (U ), and so have no effect on either the profit function or the optimal solution as well. We first prove that there exists a proper ρ(e) for each element e. Observe that properties (P1) and (P2) together uniquely define ρ(e). Therefore, we only need to find x * satisfying the equation then our proper density ρ(e) is given by ρ j (e) = Π −1 j (x * ). By Assumption (A1), Π j is a strictly-increasing continuous function with Π j (0) = 0 and lim γ→∞ Π j (γ) = ∞, so its inverse Π −1 j is well-defined and is also a strictly-increasing continuous function with Π −1 j (0) = 0 and lim x→∞ Π −1 j (x) = ∞. Thus, the solution x * exists.
Next, we show that for any element e, we can efficiently compute ρ(e). In the following, we fix an element e, and use s j and v to denote s j (e) and v(e), respectively. We define I j (t) = Π j (c j (t)). Let x * be the solution to Equation 4 for the fixed element e and note that x * = Π(e).
In the following two lemma statements and proofs, we focus on a single dimension j and remove subscripts for ease of notation. First, we prove that we can easily compute I(t).

Lemma 5.10. We have
Proof. Let t ′ =s(c(t)). Since t ′ is the maximum size r ≥ t such that c(t) ≥ c(r), by monotonicity, we have that c(·) is constant in [t, t ′ ]. This implies C(t ′ ) − C(t) = c(t)(t ′ − t) and so, The lemma now follows from the fact that I(t) = Π(c(t)) is the LHS of the above equation.
Lemma 5.11 leads to the FIND-DENSITY algorithm which, given a profit x, uses a binary search to compute Π −1 j (x). Together with Lemma 5.12, this enables us to determine x * by first using binary search, and then solving linear equations. Algorithm 6 Given x and sizes s j , find Π −1 (x) and t 1 , . . . , t ℓ satisfying I j (t j ) ≤ x < I j (t j + 1). FIND-DENSITY(x, s) 1: for j = 1 to ℓ do 2: Binary search to find integral t j ∈ [0, s j (U )) satisfying I j (t j ) ≤ x < I j (t j + 1).

Lemma 5.12. Suppose we have a positive integer x such that
and positive integers t 1 , . . . , t ℓ such that I j (t j ) ≤ x < I j (t j + 1) for all j. Then the solution x * to Equation (4) is precisely: .
Proof. Equation (5) and the monotonicity of the Π −1 j 's imply that x ≤ x * < x + 1 and so, we have I j (t j ) ≤ x * < x + 1 ≤ I j (t j + 1) for all j. Applying Lemma 5.11 to dimension j gives us Π −1 j (x * ) = (x * − C j (t j ))/t j . Then, applying Equation (4) Solving this for x * gives the claimed equality.
We need the following lemma to show that the binary search upper bounds in both algorithms are correct.
Lemma 5.13. For proper density ρ, we have x * < I j (s j (U )) for all dimensions j.
Proof. If an element has zero size in dimension j, then we can ignore C j (·). So without loss of generality, we assume that s j > 0 for all j. Property (P1) gives us v = i ρ i s i ≥ ρ j s j and so ρ j ≤ v/s j ≤ v. From assumption (A2), we have that c j (s j (U )) > v ≥ ρ j . This implies that Since ρ is proper, we have Π j (ρ j ) = x * and this proves the lemma. we decompose the profit functions π i into sum-of-values objectives defined as follows.
Let h γ (A) = i h i γ (A) and g γ (A) = i g i γ (A). We have π i (A) = h i γ (A) + g i γ (A) for all i and π(A) = h γ (A) + g γ (A). As before, G γ,i = argmax A⊂Pγ s i (A).
We extend the definition of "boundedness" to the multi-dimensional setting as follows (see also Definition 4.1). Definition 6.1. Given a density vector γ, a subset A ⊂ P γ is said to be γ-bounded if, for all i, A is γ ibounded with respect to C i , that is, ρ i (A) ≥ γ i and s i (A) ≤s i (γ i ). If A is γ-bounded and γ is the minimum density of A, then we say A is bounded.
The following lemma is analogous to Proposition 4.2.
Next, we assume that A is bounded. Let µ be its minimum density. Then h i µ (A) ≥ 0 and g i µ (A) ≥ 0. This gives us π i (A) = h i µ (A) + g i µ (A) ≥ 0 and so π(A) ≥ π i (A) for all i.
We are now ready to give an offline algorithm. Let D γ,i be the result of running Algorithm 3 on P γ with objective π i and feasibility constraint F.
Finally, we use the above lemmas to lower bound the performance of Algorithm 8.
The following lemma is essentially an analogue of Lemma 4.7. Lemma 6.5. Suppose there exists an unbounded feasible set. For fixed parameters k 1 ≥ 1, k 4 ≤ 1, β ≤ 1 and β ′ ≤ 1 assume that there does not exists an element with profit more than 1 k 1 π(O * ). Then with probability at least k 4 , we have that τ , as defined in Algorithm 9, satisfies 1. ρ + ≥ τ ≥ ρand 2. π(O * (P Y τ )) ≥ β ′ β Proof Sketch: We define events E 1 and E 2 as in the single-dimensional setting: We observe that the proof of Lemma 4.7 primarily depends on the properties of density prefixes, in particular that π(O * (P X ρ -)) is a sufficiently large fraction of π(O * (P ρ -)), and that Algorithm 3's profit does not decrease when considering larger prefixes. Then Theorem 6.4 gives us π(O * (P ρ -)) ≥ 1 7ℓ π(O * ). Thus, a proof similar to that of Lemma 4.7 validates Lemma 6.5. The following lemma establishes the competitive ratio of Algorithm 9 in the presence of an unbounded feasible set. Lemma 6.6. Suppose that there exists an unbounded feasible set, and let α be the competitive ratio that Algorithm 4 achieves for a single-dimensional problem (π i , F). Then, for a fixed set Y and threshold τ , satisfying τ ≥ ρ -, we have E σ [π(O 2 )] ≥ 1 αℓ π(O * (P Y τ )), where the expectation is over all permutations σ of Y .
Proof. First, we prove that O 2 is bounded. By the definition of ρ -, since O 2 ⊆ P Y τ it suffices to show that P Y τ ⊆P ρ -, as all feasible sets inP ρ -are bounded. The threshold τ is either equal to or strictly greater than ρand it suffices to consider the former case. If τ = ρ -, then e ρ -must have been in the sample set X so it is not in P Y τ and so P Y τ ⊆P ρ -. Hence, by Lemma 6.1, for all i we have π(O 2 ) ≥ π i (O 2 ). Applying Theorem 4.8 where the ground set is P Y τ gives us E σ [π i (O 2 ) | i * = i] ≥ 1 α π i (O * (P Y τ )). Therefore, we have We now prove the main result of this section.