\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm{\LARGE \textbf{Convex and V-Shaped Sequences of Sums of
\\
\vskip .1in
Functions that Depend on Ceiling Functions }} \vskip 1cm {\large 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\\
\href{mailto:K.Rustogi@greenwich.ac.uk}{\tt K.Rustogi@greenwich.ac.uk} \\
\href{mailto:V.Strusevich@greenwich.ac.uk}{\tt V.Strusevich@greenwich.ac.uk} \\
}
\end{center}
\begin{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.
\end{abstract}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\section{Introduction}
A sequence $A(k),1\leq k\leq n,$ is called \emph{convex} if
\begin{equation}
A(k)\leq \frac{1}{2}\left( A(k-1)+A(k+1)\right) ,~2\leq k\leq n-1,
\label{ConvADef}
\end{equation}%
i.e., any element is no larger than the arithmetic mean of its neighbors.
For a convex sequence, the rate $\nabla (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
\begin{equation*}
A(k)\leq \sqrt{A(k-1)A(k+1)},~2\leq k\leq n-1,
\end{equation*}%
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 \cite{WuDebnath07} 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 \cite{MarshallOlkin}. Various applications of convex sequences to the
problems of combinatorics, algebra and calculus are presented in \cite%
{Mercer05, Toader96,WuDebnath07}. 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\v{s}li\'{c} \cite{Doslic09}. 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 \cite{AssignBook}.
A sequence $C(k)$ is called \emph{V-shaped} if there exists a $k_{0}$, $%
1\leq k_{0}\leq n$, such that
\begin{equation*}
C(1)\geq \cdots \geq C(k_{0}-1)\geq C(k_{0})\leq C(k_{0}+1)\leq \cdots \leq
C(n).
\end{equation*}
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 \textquotedblleft V-%
shaped\textquotedblright\ in the title; see \cite%
{AliDaee95,AlVShape96,FederMosh97,Mitten,Mosheiov91}.
There is also a somewhat dual concept of the $\Lambda -$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 \cite{TSPSurvSIAM}
and \cite{KabadiTSP}.
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.
\section{A Convex Sequence is V-Shaped\label{SectConv}}
The statement below links the convex and V-shaped sequences.
\begin{lemma}
\label{LCV}A convex sequence $C(k),1\leq k\leq n,$ is V-shaped.
\end{lemma}
\begin{proof} Suppose that a convex sequence $C(k)$, $1\leq
k\leq n$, is not V-shaped, i.e.,
there exists a $k_{1}$, $1C(k_{1}+1).
\end{equation*}
Combining the inequalities
\begin{eqnarray*}
C(k_{1}-1) &\leq &C(k_{1}), \\
C(k_{1}) &>&C(k_{1}+1),
\end{eqnarray*}%
we obtain
\begin{equation*}
C(k_{1})>\frac{1}{2}\left( C(k_{1}-1)+C(k_{1}+1)\right) .
\end{equation*}
The latter inequality contradicts (\ref{ConvADef}).
\end{proof}
The statement opposite to Lemma~\ref{LCV} 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\leq n\leq 9,$ both sequences $\sqrt{\left\vert
n-1\right\vert }$ and $\sqrt{\left\vert n-9\right\vert }$ 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\leq k\leq 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)=Tk$ 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\leq k\leq n$, is nondecreasing and convex, while the
sequence $A(k)$, $1\leq k\leq 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\leq k\leq n$, is convex, then $C(k)$, $1\leq k\leq n$, is also
convex and therefore V-shaped by Lemma~\ref{LCV}. Thus, the optimal number
of orders can be found by binary search by computing at most $\left\lceil
\log _{2}n\right\rceil $ elements of sequence $C(k)$, $1\leq k\leq n.$ On
the other hand, if the sequence $A(k)$, $1\leq k\leq n$, is not convex, then
we cannot guarantee that sequence $C(k)$, $1\leq k\leq n,$ is V-shaped. To
see this, consider the case that $T=20$ and $n=5$, while the sequence $A(k)$%
, $1\leq k\leq n$, is as below.
\begin{equation*}
A(1)=100,~A(2)=70,~A(3)=60,~A(4)=25,~A(5)=20.
\end{equation*}
The sequence $A(k)$, $1\leq k\leq n$, is not convex, and it is easy to
verify that the resulting sequence $C(k)$, $1\leq k\leq 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\leq k\leq 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\leq k\leq n,$ that is nondecreasing and convex, and $%
G(k) $, $1\leq k\leq n$, that is nonincreasing. For the sequence $C(k)$, $%
1\leq k\leq n,$ to be V-shaped, it is sufficient to show that the sequence
$G(k)$, $1\leq k\leq n,$ is convex.
\section{Convexity of a Sequence That Involves Sums of Functions of Ceilings}
In this section we prove that the sequence%
\begin{equation}
G(k)=\sum_{j=1}^{n}g\left( \left\lceil \frac{j}{k}\right\rceil \right) ,%
\text{~}1\leq k\leq n, \label{SeqG(k)}
\end{equation}%
where $g$ is an arbitrary nonnegative nondecreasing function, is convex.
Recall that $\left\lceil x\right\rceil $ 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\leq k\leq n$, in terms of the
service center example outlined in Section~\ref{SectConv}. In that model,
the centers are numbered by the integers $1,2,\ldots ,k$, and the customers
are numbered by the integers $1,2,\ldots ,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 $\left\lceil \frac{j}{k}%
\right\rceil $ 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,\ldots ,k-1$ and take $a-1$ positions of center $k$, so that customer $j$
gets position $a=\left\lceil \frac{j}{k}\right\rceil $ at center $k$. If $%
j=ak+b$ for $1\leq b\leq k-1$, then the predecessors of $j$ will take the
first $a$ positions at each center and additionally the $\left( a+1\right) -$%
th position at each of the centers $1,2,\ldots ,b-1$, so that customer $j$
gets position $a+1=\left\lceil \frac{j}{k}\right\rceil $ at center $b$.
Thus, the value of function $g\left( \left\lceil \frac{j}{k}\right\rceil
\right) $ 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 (\ref%
{SeqG(k)}). It should be noticed that although the ceiling function and its
counterpart, the floor function $\left\lfloor x\right\rfloor =\max \left\{
n\in \mathbb{Z}|n\leq x\right\} $, 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 \cite{GrahamBook} and \cite%
{Nyblom}.
\begin{theorem}
\label{TGConv}The sequence $G(k)$, $1\leq k\leq n,$ of the form (\ref%
{SeqG(k)}) is convex.
\end{theorem}
\begin{proof} In accordance with (\ref{ConvADef}), we need to
prove that
\begin{equation}
2G(k)-G(k-1)-G(k+1)\leq 0,~2\leq k\leq n-1, \label{GConv}
\end{equation}
Given a value of $k$, $2\leq k\leq n-1$, for a $j$, $1\leq j\leq n$, we can
express $j$ as $ak+b$, where $a$ is in integer in $\left\{ 0,1,\ldots
,\left\lfloor \frac{j}{k}\right\rfloor \right\} $ and $b\leq k$. We can write%
\begin{eqnarray*}
G(k) &=&\sum_{a=0}^{\left\lfloor \frac{n}{k}\right\rfloor
-1}\sum_{b=1}^{k}g\left( \left\lceil \frac{ak+b}{k}\right\rceil
\right) +\sum_{b=1}^{n-k\left\lfloor \frac{n}{k}\right\rfloor
}g\left( \left\lceil \frac{\left\lfloor \frac{n}{k}\right\rfloor k+b}{k}%
\right\rceil \right) \\
&=&\sum_{a=0}^{\left\lfloor \frac{n}{k}\right\rfloor
-1}\sum_{b=1}^{k}g\left( a+\left\lceil \frac{b}{k}\right\rceil
\right) +\sum_{b=1}^{n-k\left\lfloor \frac{n}{k}\right\rfloor
}g\left( \left\lfloor \frac{n}{k}\right\rfloor +\left\lceil \frac{b}{k}%
\right\rceil \right) .
\end{eqnarray*}
Since $b\leq k,$ it follows that $\left\lceil \frac{b}{k}\right\rceil =1$,
so that
\begin{eqnarray*}
G(k) &=&\sum_{a=0}^{\left\lfloor \frac{n}{k}\right\rfloor
-1}\sum_{b=1}^{k}g\left( a+1\right)
+\sum_{b=1}^{n-k\left\lfloor \frac{n}{k}\right\rfloor }g\left(
\left\lfloor \frac{n}{k}\right\rfloor +1\right) \\
&=&k\sum_{r=1}^{\left\lfloor \frac{n}{k}\right\rfloor }g\left(
r\right) +\left( n-k\left\lfloor \frac{n}{k}\right\rfloor \right) g\left(
\left\lfloor \frac{q}{k}\right\rfloor +1\right) ,
\end{eqnarray*}%
where $r=a+1$ is a new summation index. Similarly, we deduce%
\begin{eqnarray*}
G(k+1) &=&(k+1)\sum_{r=1}^{\left\lfloor \frac{n}{k+1}\right\rfloor
}g\left( r\right) +\left( n-(k+1)\left\lfloor \frac{n}{k+1}\right\rfloor
\right) g\left( \left\lfloor \frac{n}{k+1}\right\rfloor +1\right) ; \\
G(k-1) &=&(k-1)\sum_{r=1}^{\left\lfloor \frac{n}{k-1}\right\rfloor
}g\left( r\right) +\left( n-(k-1)\left\lfloor \frac{n}{k-1}\right\rfloor
\right) g\left( \left\lfloor \frac{n}{k-1}\right\rfloor +1\right) .
\end{eqnarray*}
To prove (\ref{GConv}), we rewrite the difference $2G(k)-G(k+1)-G(k-1)$ as
\begin{eqnarray*}
&&\left( k\sum_{r=1}^{\left\lfloor \frac{n}{k}\right\rfloor }g\left(
r\right) -(k+1)\sum_{r=1}^{\left\lfloor \frac{n}{k+1}\right\rfloor
}g\left( r\right) \right) +\left( k\sum_{r=1}^{\left\lfloor \frac{n}{%
k}\right\rfloor }g\left( r\right) -(k-1)\sum_{r=1}^{\left\lfloor
\frac{n}{k-1}\right\rfloor }g\left( r\right) \right) \\
&&+2\left( n-k\left\lfloor \frac{n}{k}\right\rfloor \right) g\left(
\left\lfloor \frac{n}{k}\right\rfloor +1\right) -\left( n-(k+1)\left\lfloor
\frac{n}{k+1}\right\rfloor \right) g\left( \left\lfloor \frac{n}{k+1}%
\right\rfloor +1\right) \\
&&-\left( n-(k-1)\left\lfloor \frac{n}{k-1}\right\rfloor \right) g\left(
\left\lfloor \frac{n}{k-1}\right\rfloor +1\right)
\end{eqnarray*}%
and show that it is nonpositive.
Notice that the expression
\begin{equation*}
k\sum_{r=1}^{\left\lfloor \frac{n}{k}\right\rfloor }g\left( r\right)
-(k+1)\sum_{r=1}^{\left\lfloor \frac{n}{k+1}\right\rfloor }g\left(
r\right)
\end{equation*}%
can be simplified by cancelling the values of the function $g$ computed for
the same values of $r$. Since $\left\lfloor \frac{n}{k}\right\rfloor \geq
\left\lfloor \frac{n}{k+1}\right\rfloor $, we obtain%
\begin{equation*}
k\sum_{r=1}^{\left\lfloor \frac{n}{k}\right\rfloor }g\left( r\right)
-(k+1)\sum_{r=1}^{\left\lfloor \frac{n}{k+1}\right\rfloor }g\left(
r\right) =k\sum_{r=\left\lfloor \frac{n}{k+1}\right\rfloor
+1}^{\left\lfloor \frac{n}{k}\right\rfloor }g\left( r\right)
-\sum_{r=1}^{\left\lfloor \frac{n}{k+1}\right\rfloor }g\left(
r\right) .
\end{equation*}
Similarly, since $\left\lfloor \frac{n}{k-1}\right\rfloor \geq \left\lfloor
\frac{n}{k}\right\rfloor $, we obtain
\begin{equation*}
k\sum_{r=1}^{\left\lfloor \frac{n}{k}\right\rfloor }g\left( r\right)
-(k-1)\sum_{r=1}^{\left\lfloor \frac{n}{k-1}\right\rfloor }g\left(
r\right) =\sum_{r=1}^{\left\lfloor \frac{n}{k-1}\right\rfloor
}g\left( r\right) -k\sum_{r=\left\lfloor \frac{n}{k}\right\rfloor
+1}^{\left\lfloor \frac{n}{k-1}\right\rfloor }g\left( r\right) .
\end{equation*}
Combining the two above equalities, we obtain%
\begin{eqnarray*}
&&\left( k\sum_{r=1}^{\left\lfloor \frac{n}{k}\right\rfloor }g\left(
r\right) -(k+1)\sum_{r=1}^{\left\lfloor \frac{n}{k+1}\right\rfloor
}g\left( r\right) \right) +\left( k\sum_{r=1}^{\left\lfloor \frac{n}{%
k}\right\rfloor }g\left( r\right) -(k-1)\sum_{r=1}^{\left\lfloor
\frac{n}{k-1}\right\rfloor }g\left( r\right) \right) \\
&=&k\left( \sum_{r=\left\lfloor \frac{n}{k+1}\right\rfloor
+1}^{\left\lfloor \frac{n}{k}\right\rfloor }g\left( r\right)
-\sum_{r=\left\lfloor \frac{n}{k}\right\rfloor +1}^{\left\lfloor
\frac{n}{k-1}\right\rfloor }g\left( r\right) \right)
+\sum_{r=\left\lfloor \frac{n}{k+1}\right\rfloor +1}^{\left\lfloor
\frac{n}{k-1}\right\rfloor }g\left( r\right) ,
\end{eqnarray*}
which reduces to
\begin{eqnarray*}
&&\left( k\sum_{r=1}^{\left\lfloor \frac{n}{k}\right\rfloor }g\left(
r\right) -(k+1)\sum_{r=1}^{\left\lfloor \frac{n}{k+1}\right\rfloor
}g\left( r\right) \right) +\left( k\sum_{r=1}^{\left\lfloor \frac{n}{%
k}\right\rfloor }g\left( r\right) -(k-1)\sum_{r=1}^{\left\lfloor
\frac{n}{k-1}\right\rfloor }g\left( r\right) \right) \\
&=&(k+1)\sum_{r=\left\lfloor \frac{n}{k+1}\right\rfloor
+1}^{\left\lfloor \frac{n}{k}\right\rfloor }g\left( r\right)
-(k-1)\sum_{r=\left\lfloor \frac{n}{k}\right\rfloor
+1}^{\left\lfloor \frac{n}{k-1}\right\rfloor }g\left( r\right) .
\end{eqnarray*}
Coming back to the initial difference in (\ref{GConv}), we have that
\begin{eqnarray*}
2G(k)-G(k+1)-G(k-1) &=&(k+1)\sum_{r=\left\lfloor \frac{n}{k+1}%
\right\rfloor +1}^{\left\lfloor \frac{n}{k}\right\rfloor }g\left( r\right)
-(k-1)\sum_{r=\left\lfloor \frac{n}{k}\right\rfloor
+1}^{\left\lfloor \frac{n}{k-1}\right\rfloor }g\left( r\right) \\
&&+2\left( n-k\left\lfloor \frac{n}{k}\right\rfloor \right) g\left(
\left\lfloor \frac{n}{k}\right\rfloor +1\right) \\
&&-\left( n-(k+1)\left\lfloor \frac{n}{k+1}\right\rfloor \right) g\left(
\left\lfloor \frac{n}{k+1}\right\rfloor +1\right)
\end{eqnarray*}
Recombine
\begin{eqnarray*}
&&(k+1)\sum_{r=\left\lfloor \frac{n}{k+1}\right\rfloor
+2}^{\left\lfloor \frac{n}{k}\right\rfloor }g\left( r\right) +\left(
(k+1)-\left( n-(k+1)\left\lfloor \frac{n}{k+1}\right\rfloor \right) \right)
g\left( \left\lfloor \frac{n}{k+1}\right\rfloor +1\right) \\
&&-(k-1)\sum_{r=\left\lfloor \frac{n}{k}\right\rfloor
+2}^{\left\lfloor \frac{n}{k-1}\right\rfloor }g\left( r\right) +\left(
2n-2k\left\lfloor \frac{n}{k}\right\rfloor -(k-1)\right) g\left(
\left\lfloor \frac{n}{k}\right\rfloor +1\right) \\
&&-\left( n-(k-1)\left\lfloor \frac{n}{k-1}\right\rfloor \right) g\left(
\left\lfloor \frac{n}{k-1}\right\rfloor +1\right) .
\end{eqnarray*}
To prove (\ref{GConv}), 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\leq Y$. It follows that%
\begin{eqnarray*}
X &=&\left( (k+1)\left( \left\lfloor \frac{n}{k+1}\right\rfloor +1\right)
-n\right) g\left( \left\lfloor \frac{n}{k+1}\right\rfloor +1\right)
+(k+1)\sum_{r=\left\lfloor \frac{n}{k+1}\right\rfloor
+2}^{\left\lfloor \frac{n}{k}\right\rfloor }g\left( r\right) + \\
&&+\left( 2n+1\right) g\left( \left\lfloor \frac{n}{k}\right\rfloor
+1\right) ; \\
Y &=&\left( 2k\left\lfloor \frac{n}{k}\right\rfloor +k\right) g\left(
\left\lfloor \frac{n}{k}\right\rfloor +1\right)
+(k-1)\sum_{r=\left\lfloor \frac{n}{k}\right\rfloor
+2}^{\left\lfloor \frac{n}{k-1}\right\rfloor }g\left( r\right) + \\
&&+\left( n-(k-1)\left\lfloor \frac{n}{k-1}\right\rfloor \right) g\left(
\left\lfloor \frac{n}{k-1}\right\rfloor +1\right) .
\end{eqnarray*}
In the expression for $X$, the arguments of the function $g$ are from $%
\left\lfloor \frac{n}{k+1}\right\rfloor +1$ to $\left\lfloor \frac{n}{k}%
\right\rfloor +1$, while in the expression for $Y$, the arguments of the
function $g$ are from $\left\lfloor \frac{n}{k}\right\rfloor +1$ to $%
\left\lfloor \frac{n}{k-1}\right\rfloor +1$, so that we can write%
\begin{equation*}
X=\sum_{r=\left\lfloor \frac{n}{k+1}\right\rfloor +1}^{\left\lfloor \frac{n%
}{k}\right\rfloor +1}x_{r}g(r),\text{ }Y=\sum_{r=\left\lfloor \frac{n}{k}%
\right\rfloor +1}^{\left\lfloor \frac{n}{k-1}\right\rfloor +1}y_{r}g(r),
\end{equation*}%
where all coefficients $x_{r}$ and $y_{r}$ are non-negative.
Computing%
\begin{eqnarray*}
\sum_{r=\left\lfloor \frac{n}{k+1}\right\rfloor +1}^{\left\lfloor \frac{n}{k%
}\right\rfloor +1}x_{r} &=&(k+1)\left( \left\lfloor \frac{n}{k+1}%
\right\rfloor +1\right) -n+(k+1)\left( \left\lfloor \frac{n}{k}\right\rfloor
-\left\lfloor \frac{n}{k+1}\right\rfloor -1\right) +\left( 2n+1\right) , \\
\sum_{r=\left\lfloor \frac{n}{k}\right\rfloor +1}^{\left\lfloor \frac{n}{k-1%
}\right\rfloor +1}y_{r} &=&\left( 2k\left\lfloor \frac{n}{k}\right\rfloor
+k\right) +(k-1)\left( \left\lfloor \frac{n}{k-1}\right\rfloor -\left\lfloor
\frac{n}{k}\right\rfloor -1\right) +\left( n-(k-1)\left\lfloor \frac{n}{k-1}%
\right\rfloor \right)
\end{eqnarray*}%
we deduce that both sums above are equal to $(k+1)\left\lfloor \frac{n}{k}%
\right\rfloor +n+1.$ Thus, each $X$ and $Y$ can be seen as the sum of $%
(k+1)\left\lfloor \frac{n}{k}\right\rfloor +n+1$ values of the function $g$;
however, for any $i$, $1\leq i\leq (k+1)\left\lfloor \frac{n}{k}%
\right\rfloor +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\leq Y$, i.e., $%
2G(k)-G(k+1)-G(k-1)\leq 0,$ so that the sequence $G(k)$, $1\leq k\leq n$, is
convex.
\end{proof}
An immediate implication of Theorem~\ref{TGConv} is that the sequence $%
C(k)=G(k)+T(k)$, $1\leq k\leq n,$ that represents the total cost is convex
as the sum of two convex sequences. Lemma~\ref{LCV} guarantees that $C(k)$, $%
1\leq k\leq 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 $%
\left\lceil \log _{2}n\right\rceil $ comparisons (as opposed to $n$
comparisons if the V-shapeness were not established). Other applications
of Theorem~\ref{TGConv} can be found in the area of machine scheduling with
positionally dependent processing times.
\begin{thebibliography}{99}
\bibitem{AliDaee95} B. Alidaee and D. Rosa, A note on the V-shaped
property in one-machine scheduling. \emph{J. Oper. Res. Soc.},~\textbf{46}
(1995), 128--132.
\bibitem{AlVShape96} U. M. Alturki, J. Mittenthal, and M. Raghavachari, A
dominant subset of V-shaped sequences for a class of single machine
sequencing problems. \emph{Eur. J. Oper. Res.},~\textbf{88} (1996), 345--347.
\bibitem{TSPSurvSIAM} 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. \emph{SIAM Rev.},~\textbf{40} (1998), 496--546.
\bibitem{AssignBook} R. Burkard, M. Dell'amico, and S. Martello, \emph{%
Assignment Problems}. SIAM, Philadelphia, 2009.
\bibitem{Doslic09} T. Do\v{s}li\'{c}, Log-convexity of combinatorial
sequences from their convexity, \emph{J. Math. Inequal.},~\textbf{3} (2009),
437--442.
\bibitem{FederMosh97} A. Federgruen and G. Mosheiov, Single machine
scheduling problems with general breakdowns, earliness and tardiness costs,
\emph{Oper. Res.},~\textbf{45} (1997), 66--71.
\bibitem{GrahamBook} R. L. Graham, D. E. Knuth, and O. Patashnik, \emph{%
Concrete Mathematics}. Addison-Wesley, New York, 1989.
\bibitem{KabadiTSP} S. N. Kabadi, Polynomially solvable cases of the TSP. In
\emph{The Traveling Salesman Problem and Its Variations}, G. Gutin and A.P.
Punnen (Eds.), Springer, 2007, pp.\ 489--583.
\bibitem{MarshallOlkin} A. W. Marshall and I. Olkin, \emph{Inequalities: The
Theory of Majorization and Its Applications}, Academic Press, 1979.
\bibitem{Mercer05} A. M. Mercer, Polynomials and convex sequence
inequalities. \emph{J. Inequal. Pure Appl. Math.},~\textbf{6} (2005), 1--4.
\bibitem{Mitten} 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. \emph{Eur. J. Oper. Res.},~\textbf{86}
(1995), 262--269.
\bibitem{Mosheiov91} G. Mosheiov, V-shaped policies for scheduling
deteriorating jobs, \emph{Oper. Res.},~\textbf{39} (1991), 979--991.
\bibitem{Nyblom} M. A. Nyblom, Some curious sequences involving floor and
ceiling functions. \emph{Am. Math. Mon.},~\textbf{109} (2002), 559--564.
\bibitem{Toader96} G. Toader, On Chebychev's inequality for sequences. \emph{%
Discrete Math.},~\textbf{161} (1996), 317--322.
\bibitem{WuDebnath07} S. Wu and L. Debnath, Inequalities for convex
sequences and their application. \emph{Int. J. Comput. Math. Appl.,}~\textbf{%
54} (2007), 525--534.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B99; Secondary 90C27.
\noindent \emph{Keywords: } convex sequence, V-shaped sequence,
ceiling function.
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received October 5 2010;
revised version received January 31 2011.
Published in {\it Journal of Integer Sequences}, February 7 2011.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}