Convex and V-Shaped Sequences of Sums of Functions that Depend on Ceiling Functions

Kabir Rustogi and Vitaly A. Strusevich School of Computing and Mathematical Sciences University of Greenwich Old Royal Naval College Park Row, Greenwich London SE10 9LS United Kingdom

               K.Rustogi@greenwich.ac.uk
             V.Strusevich@greenwich.ac.uk

Abstract

The paper primarily revolves around the convex and V-shaped finite sequences and the inequalities that govern them. We give an elementary proof that a convex sequence is also V-shaped. We prove an inequality that involves an arbitrary nondecreasing function that depends on ceiling functions, thereby establishing the convexity of the corresponding sequence. We present various interpretations and applications of our results, mainly in terms of operations research problems.

1 Introduction

A sequence A(k), 1 ≤ k ≤ n, is called convex if

A(k) ≤ \frac{1}{2} (A(k − 1) + A(k + 1)) , 2 ≤ k ≤ n − 1,  (1)

i.e., any element is no larger than the arithmetic mean of its neighbors. For a convex sequence, the rate ∇(k) = A(k + 1) − A(k) does not decrease as k grows. A concept of a convex sequence is closely related to the notion of a log-convex sequence, for which

A(k) ≤ \sqrt{A(k − 1)A(k + 1)}, 2 ≤ k ≤ n − 1,

i.e., any element is no larger than the geometric mean of its neighbors. Convex sequences play an important role in the derivation of various inequalities. Wu and Debnath [15] give a necessary and sufficient condition for a sequence to be convex in terms of majorization, and this gives access to a powerful toolkit that is systematically exposed in [9]. Various applications of convex sequences to the problems of combinatorics, algebra and calculus are presented in [10, 14, 15]. Any log-convex sequence is also convex due to the inequality between the arithmetic and geometric means. An additional important link between convex and log-convex sequences is pointed out by T. Došlić [5]. In operations research, an application of convex sequences to a special form of the assignment problem and their relations to the famous Monge property is discussed in Chapter 5.2 of the recent monograph [4].

A sequence C(k) is called V-shaped if there exists a k_{0}, 1 ≤ k_{0} ≤ n, such that

C(1) ≥ ⋯ ≥ C(k_{0} − 1) ≥ C(k_{0}) ≤ C(k_{0} + 1) ≤ ⋯ ≤ C(n).

If a finite sequence that contains n terms is V-shaped then its minimum value and the position k_{0} of that minimum in the sequence can be found by binary search in at most log_{2} n comparisons.

The V-shaped sequences often arise in optimization over a set of permutations, in particular in machine scheduling. For a number of scheduling problems it is possible to establish that an optimal sequence of jobs possesses the V-shaped property, e.g., the elements of the input sequence of the processing times can be interchanged so that the resulting sequence is V-shaped. This property has been explored in numerous papers. Here, we refer to only five, mostly with the words “V-shaped” in the title; see [1, 2, 6, 11, 12].

There is also a somewhat dual concept of the Λ−shaped sequence, also known as unimodal sequence or pyramidal sequence, in which the elements are placed in nondecreasing order and then in nonincreasing order. These sequences are the main object of study in identifying efficiently solvable combinatorial optimization problems, in particular the traveling salesman problem. Here we only refer to two most recent surveys [3] and [8].

Despite the fact that the two types of sequences, convex and V-shaped, are well-known in the corresponding area of study, to the best of our knowledge, so far there has been no attempt to link these two concepts. In the following section we give an elementary proof that a convex sequence is in fact V-shaped.

2 A Convex Sequence is V-Shaped

The statement below links the convex and V-shaped sequences.

Lemma 1. A convex sequence C(k), 1 ≤ k ≤ n, is V-shaped.

Proof. Suppose that a convex sequence C(k), 1 ≤ k ≤ n, is not V-shaped, i.e., there exists a k_{1}, 1 < k_{1} < n, such that

C(k_{1} − 1) ≤ C(k_{1}) > C(k_{1} + 1).

Combining the inequalities

C(k_{1} − 1) ≤ C(k_{1}),
C(k_{1}) > C(k_{1} + 1),

we obtain

C(k_{1}) > \frac{1}{2} (C(k_{1} − 1) + C(k_{1} + 1)) .

The latter inequality contradicts (1).

The statement opposite to Lemma 1 is not true: indeed, any monotone sequence is V-shaped, but need not be convex.

It can be immediately verified that the sum of two convex sequences is convex, and therefore is V-shaped. On the other hand, the sum of two V-shaped sequences is not necessarily V-shaped, which, e.g., is demonstrated by the following counterexample suggested by an anonymous referee. For an integer n, 0 ≤ n ≤ 9, both sequences \sqrt{|n − 1|} and \sqrt{|n − 9|} are V-shaped, but their sum is not, since the sum has two equal maxima at n = 0 and n = 5 as well as two equal minima at n = 1 and n = 9.

The use of these sequences can be illustrated by problems that raise in operations research. Consider the following inventory control problem. Suppose that the sequence A(k), 1 ≤ k ≤ n, represents the annual holding cost of some product, provided that k orders are placed during a year. Let T be the cost of placing one order, so that B(k) = T k is the total ordering cost for k orders. The purpose is to determine the optimal number of orders that minimizes the total cost C(k) = A(k) + B(k). Notice that the sequence B(k), 1 ≤ k ≤ n, is nondecreasing and convex, while the sequence A(k), 1 ≤ k ≤ n, is nonincreasing (the more frequently we order, the smaller the holding cost will be); thus, the sequence C(k) captures the trade-off between its two components. Now, if the sequence A(k), 1 ≤ k ≤ n, is convex, then C(k), 1 ≤ k ≤ n, is also convex and therefore V-shaped by Lemma 1. Thus, the optimal number of orders can be found by binary search by computing at most ⌈log_{2} n⌉ elements of sequence C(k), 1 ≤ k ≤ n. On the other hand, if the sequence A(k), 1 ≤ k ≤ n, is not convex, then we cannot guarantee that sequence C(k), 1 ≤ k ≤ n, is V-shaped. To see this, consider the case that T = 20 and n = 5, while the sequence A(k), 1 ≤ k ≤ n, is as below.

A(1) = 100, A(2) = 70, A(3) = 60, A(4) = 25, A(5) = 20.

The sequence A(k), 1 ≤ k ≤ n, is not convex, and it is easy to verify that the resulting sequence C(k), 1 ≤ k ≤ n, is not V-shaped.

For another illustration, suppose that n customers are to be assigned, in order, to one of k service centers. Let G(k) represent the service cost measured as the total dissatisfaction of all customers, provided that k centers are open. Let T be the cost of running a center, so that T (k) = kT is the total cost of running k centers. The purpose is to determine the number of centers to be opened so that the total cost C(k) = G(k) + T (k), 1 ≤ k ≤ n, is minimized. As in the example above, the sequence C(k) captures the trade-off between its two components, i.e., between the sequence T (k), 1 ≤ k ≤ n, that is nondecreasing and convex, and G(k), 1 ≤ k ≤ n, that is nonincreasing. For the sequence C(k), 1 ≤ k ≤ n, to be V-shaped, it is sufficient to show that the sequence G(k), 1 ≤ k ≤ n, is convex.

3 Convexity of a Sequence That Involves Sums of Functions of Ceilings

In this section we prove that the sequence

G(k) = ∑_{j=1}^{n} g (⌈\frac{j}{k} ⌉) , 1 ≤ k ≤ n,  (2)

where g is an arbitrary nonnegative nondecreasing function, is convex. Recall that ⌈x⌉ is the ceiling function and is equal to the smallest integer that is not less than x.

Our interest in this and more general sequences has been initiated by our study of single machine scheduling problems with deteriorating jobs and machine maintenance. However, in this paper we give a different interpretation of the sequence G(k), 1 ≤ k ≤ n, in terms of the service center example outlined in Section 2. In that model, the centers are numbered by the integers 1, 2, …, k, and the customers are numbered by the integers 1, 2, …, n. The customers are considered in the order of their numbering and the next customer is assigned to the current last position at the least loaded center with the smallest number. Thus, customer j will get the position ⌈\frac{j}{k}⌉ at one of the centers. Indeed, if j = ak then the predecessors of j are placed into the first a positions of centers 1, 2, …, k −1 and take a−1 positions of center k, so that customer j gets position a = ⌈\frac{j}{k}⌉ at center k. If j = ak + b for 1 ≤ b ≤ k − 1, then the predecessors of j will take the first a positions at each center and additionally the (a + 1) −th position at each of the centers 1, 2, …, b − 1, so that customer j gets position a + 1 = ⌈\frac{j}{k}⌉ at center b.

Thus, the value of function g (⌈\frac{j}{k}⌉) can be understood as dissatisfaction of customer j with its position at a center, and G(k) measures the total dissatisfaction of all customers, provided that k centers are open.

Below we give an elementary proof of the convexity of the sequence (2). It should be noticed that although the ceiling function and its counterpart, the floor function ⌊x⌋ = max {n ∈ ℤ|n ≤ x}, arise and find applications in many areas, publications that study the relations that involve these functions are quite scarce; we mention only Chapter 3 of [7] and [13].

Theorem 2. The sequence G(k), 1 ≤ k ≤ n, of the form (2) is convex.

Proof. In accordance with (1), we need to prove that

2G(k) − G(k − 1) − G(k + 1) ≤ 0, 2 ≤ k ≤ n − 1,  (3)

Given a value of k, 2 ≤ k ≤ n − 1, for a j, 1 ≤ j ≤ n, we can express j as ak + b, where a is in integer in \{0, 1, …, ⌊\frac{j}{k}⌋\} and b ≤ k. We can write

G(k) = ∑_{a=0}^{⌊\frac{n}{k}⌋−1} ∑_{b=1}^{k} g (⌈\frac{ak + b}{k}⌉) + ∑_{b=1}^{n−k⌊\frac{n}{k}⌋} g (⌈\frac{⌊\frac{n}{k}⌋ k + b}{k}⌉)

= ∑_{a=0}^{⌊\frac{n}{k}⌋−1} ∑_{b=1}^{k} g (a + ⌈\frac{b}{k} ⌉) + ∑_{b=1}^{n−k⌊\frac{n}{k}⌋} g (⌊\frac{n}{k}⌋ + ⌈\frac{b}{k} ⌉) .

Since b ≤ k, it follows that ⌈\frac{b}{k}⌉ = 1, so that

G(k) = ∑_{a=0}^{⌊\frac{n}{k}⌋−1} ∑_{b=1}^{k} g (a + 1) + ∑_{b=1}^{n−k⌊\frac{n}{k}⌋} g (⌊\frac{n}{k}⌋ + 1)

= k \begin{matrix}⌊ & \frac{n}{k} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r) + (n − k ⌊\frac{n}{k}⌋) g (⌊\frac{q}{k} ⌋ + 1) ,

where r = a + 1 is a new summation index. Similarly, we deduce

G(k + 1) = (k + 1) \begin{matrix}⌊ & \frac{n}{k+1} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r) + (n − (k + 1) ⌊\frac{n}{k + 1}⌋) g (⌊\frac{n}{k + 1}⌋ + 1);

G(k − 1) = (k − 1) \begin{matrix}⌊ & \frac{n}{k−1} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r) + (n − (k − 1) ⌊\frac{n}{k − 1}⌋) g (⌊\frac{n}{k − 1}⌋ + 1) .

To prove (3), we rewrite the difference 2G(k) − G(k + 1) − G(k − 1) as

(k \begin{matrix}⌊ & \frac{n}{k} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r) − (k + 1) \begin{matrix}⌊ & \frac{n}{k+1} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r)) + (k \begin{matrix}⌊ & \frac{n}{k} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r) − (k − 1) \begin{matrix}⌊ & \frac{n}{k−1} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r))

+2 (n − k ⌊\frac{n}{k}⌋) g (⌊\frac{n}{k}⌋ + 1) − (n − (k + 1) ⌊\frac{n}{k + 1}⌋) g (⌊\frac{n}{k + 1}⌋ + 1)

− (n − (k − 1) ⌊\frac{n}{k − 1}⌋) g (⌊\frac{n}{k − 1}⌋ + 1)

and show that it is nonpositive.

Notice that the expression

k \begin{matrix}⌊ & \frac{n}{k} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r) − (k + 1) \begin{matrix}⌊ & \frac{n}{k+1} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r)

can be simplified by cancelling the values of the function g computed for the same values of r. Since ⌊\frac{n}{k}⌋ ≥ ⌊\frac{n}{k+1}⌋, we obtain

k \begin{matrix}⌊ & \frac{n}{k} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r) − (k + 1) \begin{matrix}⌊ & \frac{n}{k+1} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r) = k \begin{matrix}⌊ & \frac{n}{k} & ⌋ \\ ∑ \\ r=⌊\frac{n}{k+1}⌋+1 \end{matrix} g (r) − \begin{matrix}⌊ & \frac{n}{k+1} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r) .

Similarly, since ⌊\frac{n}{k−1}⌋ ≥ ⌊\frac{n}{k}⌋, we obtain

k \begin{matrix}⌊ & \frac{n}{k} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r) − (k − 1) \begin{matrix}⌊ & \frac{n}{k−1} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r) = \begin{matrix}⌊ & \frac{n}{k−1} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r) − k \begin{matrix}⌊ & \frac{n}{k−1} & ⌋ \\ ∑ \\ r=⌊\frac{n}{k}⌋+1 \end{matrix} g (r) .

Combining the two above equalities, we obtain

(k \begin{matrix}⌊ & \frac{n}{k} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r) − (k + 1) \begin{matrix}⌊ & \frac{n}{k+1} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r)) + (k \begin{matrix}⌊ & \frac{n}{k} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r) − (k − 1) \begin{matrix}⌊ & \frac{n}{k−1} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r))

= k (\begin{matrix}⌊ & \frac{n}{k} & ⌋ \\ ∑ \\ r=⌊\frac{n}{k+1}⌋+1 \end{matrix} g (r) − \begin{matrix}⌊ & \frac{n}{k−1} & ⌋ \\ ∑ \\ r=⌊\frac{n}{k}⌋+1 \end{matrix} g (r)) + \begin{matrix}⌊ & \frac{n}{k−1} & ⌋ \\ ∑ \\ r=⌊\frac{n}{k+1}⌋+1 \end{matrix} g (r) ,

which reduces to

(k \begin{matrix}⌊ & \frac{n}{k} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r) − (k + 1) \begin{matrix}⌊ & \frac{n}{k+1} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r)) + (k \begin{matrix}⌊ & \frac{n}{k} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r) − (k − 1) \begin{matrix}⌊ & \frac{n}{k−1} & ⌋ \\ ∑ \\ r=1 \end{matrix} g (r))

= (k + 1) \begin{matrix}⌊ & \frac{n}{k} & ⌋ \\ ∑ \\ r=⌊\frac{n}{k+1}⌋+1 \end{matrix} g (r) − (k − 1) \begin{matrix}⌊ & \frac{n}{k−1} & ⌋ \\ ∑ \\ r=⌊\frac{n}{k}⌋+1 \end{matrix} g (r) .

Coming back to the initial difference in (3), we have that

2G(k) − G(k + 1) − G(k − 1) = (k + 1) \begin{matrix}⌊ & \frac{n}{k} & ⌋ \\ ∑ \\ r=⌊\frac{n}{k+1}⌋+1 \end{matrix} g (r) − (k − 1) \begin{matrix}⌊ & \frac{n}{k−1} & ⌋ \\ ∑ \\ r=⌊\frac{n}{k}⌋+1 \end{matrix} g (r)

+2 (n − k ⌊\frac{n}{k}⌋) g (⌊\frac{n}{k}⌋ + 1)

− (n − (k + 1) ⌊\frac{n}{k + 1}⌋) g (⌊\frac{n}{k + 1}⌋ + 1)

Recombine

(k + 1) \begin{matrix}⌊ & \frac{n}{k} & ⌋ \\ ∑ \\ r=⌊\frac{n}{k+1}⌋+2 \end{matrix} g (r) + ((k + 1) − (n − (k + 1) ⌊\frac{n}{k + 1}⌋)) g (⌊\frac{n}{k + 1}⌋ + 1)

−(k − 1) \begin{matrix}⌊ & \frac{n}{k−1} & ⌋ \\ ∑ \\ r=⌊\frac{n}{k}⌋+2 \end{matrix} g (r) + (2n − 2k ⌊\frac{n}{k}⌋ − (k − 1)) g (⌊\frac{n}{k}⌋ + 1)

− (n − (k − 1) ⌊\frac{n}{k − 1}⌋) g (⌊\frac{n}{k − 1}⌋ + 1) .

To prove (3), we collect together the terms that make a positive contribution X and a negative contribution Y so that 2G(k)−G(k+1)−G(k−1) = X −Y, and show that X ≤ Y.

It follows that

X = ((k + 1) (⌊\frac{n}{k + 1}⌋ + 1) − n) g (⌊\frac{n}{k + 1}⌋ + 1) + (k + 1) \begin{matrix}⌊ & \frac{n}{k} & ⌋ \\ ∑ \\ r=⌊\frac{n}{k+1}⌋+2 \end{matrix} g (r) +

+ (2n + 1) g (⌊\frac{n}{k}⌋ + 1);

Y = (2k ⌊\frac{n}{k}⌋ + k) g (⌊\frac{n}{k}⌋ + 1) + (k − 1) \begin{matrix}⌊ & \frac{n}{k−1} & ⌋ \\ ∑ \\ r=⌊\frac{n}{k}⌋+2 \end{matrix} g (r) +

+ (n − (k − 1) ⌊\frac{n}{k − 1}⌋) g (⌊\frac{n}{k − 1}⌋ + 1) .

In the expression for X, the arguments of the function g are from ⌊\frac{n}{k+1}⌋ + 1 to ⌊\frac{n}{k}⌋ + 1, while in the expression for Y, the arguments of the function g are from ⌊\frac{n}{k}⌋ + 1 to ⌊\frac{n}{k−1}⌋ + 1, so that we can write

X = ∑_{r=⌊\frac{n}{k+1}⌋+1}^{⌊\frac{n}{k}⌋+1} x_{r}g(r), Y = ∑_{r=⌊\frac{n}{k}⌋+1}^{⌊\frac{n}{k−1}⌋+1} y_{r}g(r),

where all coefficients x_{r} and y_{r} are non-negative.

Computing

∑_{r=⌊\frac{n}{k+1}⌋+1}^{⌊\frac{n}{k}⌋+1} x_{r} = (k + 1) (⌊\frac{n}{k + 1}⌋ + 1) − n + (k + 1) (⌊\frac{n}{k}⌋ − ⌊\frac{n}{k + 1}⌋ − 1) + (2n + 1) ,

∑_{r=⌊\frac{n}{k}⌋+1}^{⌊\frac{n}{k−1}⌋+1} y_{r} = (2k ⌊\frac{n}{k}⌋ + k) + (k − 1) (⌊\frac{n}{k − 1}⌋ − ⌊\frac{n}{k}⌋ − 1) + (n − (k − 1) ⌊\frac{n}{k − 1}⌋)

we deduce that both sums above are equal to (k + 1) ⌊\frac{n}{k}⌋ + n + 1. Thus, each X and Y can be seen as the sum of (k + 1) ⌊\frac{n}{k}⌋ + n + 1 values of the function g; however, for any i, 1 ≤ i ≤ (k +1) ⌊\frac{n}{k}⌋+n+1, the i−th smallest value of g(r) involved in the expression for X is no larger than the i−th smallest value of g(r) involved in the expression for Y. This proves that X ≤ Y, i.e., 2G(k) − G(k + 1) − G(k − 1) ≤ 0, so that the sequence G(k), 1 ≤ k ≤ n, is convex.

An immediate implication of Theorem 2 is that the sequence C(k) = G(k) + T (k), 1 ≤ k ≤ n, that represents the total cost is convex as the sum of two convex sequences. Lemma 1 guarantees that C(k), 1 ≤ k ≤ n, is V-shaped, so that the minimum total cost and the optimal number of service centers to be opened can be found as a result of ⌈log_{2} n⌉ comparisons (as opposed to n comparisons if the V-shapeness were not established). Other applications of Theorem 2 can be found in the area of machine scheduling with positionally dependent processing times.

References

[1] B. Alidaee and D. Rosa, A note on the V-shaped property in one-machine scheduling. J. Oper. Res. Soc., 46 (1995), 128–132.

[2] U. M. Alturki, J. Mittenthal, and M. Raghavachari, A dominant subset of V-shaped sequences for a class of single machine sequencing problems. Eur. J. Oper. Res., 88 (1996), 345–347.

[3] R. E. Burkard, V. G. Deineko, R. van Dal, J. A. A. van der Veen, and G. J. Woeginger, Well-solvable special cases of the traveling salesman problem: a survey. SIAM Rev., 40 (1998), 496–546.

[4] R. Burkard, M. Dell’amico, and S. Martello, Assignment Problems. SIAM, Philadelphia, 2009.

[5] T. Došlić, Log-convexity of combinatorial sequences from their convexity, J. Math. Inequal., 3 (2009), 437–442.

[6] A. Federgruen and G. Mosheiov, Single machine scheduling problems with general breakdowns, earliness and tardiness costs, Oper. Res., 45 (1997), 66–71.

[7] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics. Addison-Wesley, New York, 1989.

[8] S. N. Kabadi, Polynomially solvable cases of the TSP. In The Traveling Salesman Problem and Its Variations, G. Gutin and A.P. Punnen (Eds.), Springer, 2007, pp. 489–583.

[9] A. W. Marshall and I. Olkin, Inequalities: The Theory of Majorization and Its Applications, Academic Press, 1979.

[10] A. M. Mercer, Polynomials and convex sequence inequalities. J. Inequal. Pure Appl. Math., 6 (2005), 1–4.

[11] J. Mittenthal, M. Raghavachari and A. I. Rana, V-shapes and Lambda-spared properties for optimal single-machine schedules for a class of nonseparable penalty-functions. Eur. J. Oper. Res., 86 (1995), 262–269.

[12] G. Mosheiov, V-shaped policies for scheduling deteriorating jobs, Oper. Res., 39 (1991), 979–991.

[13] M. A. Nyblom, Some curious sequences involving floor and ceiling functions. Am. Math. Mon., 109 (2002), 559–564.

[14] G. Toader, On Chebychev’s inequality for sequences. Discrete Math., 161 (1996), 317– 322.

[15] S. Wu and L. Debnath, Inequalities for convex sequences and their application. Int. J. Comput. Math. Appl., 54 (2007), 525–534.

2010 Mathematics Subject Classification: Primary 11B99; Secondary 90C27. Keywords: convex sequence, V-shaped sequence, ceiling function.

Received October 5 2010; revised version received January 31 2011. Published in Journal of Integer Sequences, February 7 2011.

Return to Journal of Integer Sequences home page.