\documentclass[11pt,draftclsnofoot,onecolumn]{IEEEtran}
%\documentclass[11pt,journal,cspaper,compsoc]{IEEEtran}
%\documentclass[11pt] {article}
\usepackage{ amsfonts}
\usepackage{ amsthm}
%The cite package sorts numerical citations in ascending order and compresses lists of at least three consecutive numerical citations that occur together in the text. The sorted and compressed citations appear inline by default but can be superscripted.
\usepackage{cite}
% LaTeX-CAD is a drawing package for creating LATEX-compatible line diagrams under the Windows environment. It can create a variety of lines and shapes incorporating LATEX fonts and symbols.
%\usepackage{stylefiles/latexcad}
% The algorithmic package provides an environment for describing algorithms and the algorithm package provides a “float” wrapper for algorithms.
\usepackage{algorithmic,algorithm}
%Provides support for setting the spacing between lines in a document. Package options include singlespacing, onehalfspacing, and %doublespacing. Alternatively the spacing can be changed as required with the \singlespacing , \onehalfspacing , and \doublespacing %commands. Other size spacings also available.
\usepackage{setspace} \onehalfspacing
%The package manages culturally-determined typographical (and other) rules, and hyphenation patterns for a wide range of languages. A document may select a single language to be supported, or it may select several, and the document may then switch from one language to another in a variety of ways.
\usepackage[english]{babel}
%The subfigure package supports the use of small figures and tables within a single floating figure or table environment. The package %supports the positioning, captioning, and labeling of small figures and tables and, perhaps most significantly, the inclusion of %their captions in the list of figures or tables.
\usepackage[tight]{subfigure}
% The amsmath package provides many useful and powerful commands for dealing with mathematics. If using it, be sure to load this package with the cmex10 option to ensure that only type 1 fonts will utilized at all point sizes. Also, note that the amsmath package sets \interdisplaylinepenalty to 10000 thus preventing page breaks from occurring within multiline equations. Use: \interdisplaylinepenalty=2500 after loading amsmath.
% The amsthm package provides an enhanced version of LATEX's \newtheorem command for defining theorem-like environments.
% The amsfonts package is a collection of additional TeX fonts designed for use in mathematical material with AmS-TeX.
\usepackage[cmex10]{amsmath}
%\usepackage{amsthm,amsfonts,amssymb}
\usepackage{amsfonts,amssymb}
\interdisplaylinepenalty=2500
\sloppy % This declaration makes TeX less fussy about line breaking.
%The bm package defines a command \bm which makes its argument bold. The argument may be any maths object from a single symbol to %an expression. This is closely related to the specification of the \boldsymbol amsbsy command in AMS-LaTeX, but \bm is rather %more careful in the way it does things.
\usepackage{bm}
%The array package extends the implementation of the LaTeX array and tabular environments by providing options for column formatting, %including lines and paragraph indention.
\usepackage{array}
\usepackage{dsfont}
%Enhanced support for graphics.
\usepackage[dvips]{graphicx}
%The color package provides both foreground (text, rules, etc.) and background colour management; it uses the device driver configuration mechanisms of the graphics package to determine how to control its ouptut.
\usepackage{color}
% Flexible and complete interface to document dimensions.
\usepackage[letterpaper,top=1in,bottom=1in,left=0.75in,right=0.75in,bindingoffset=0in]{geometry}
%\oddsidemargin=-0.25in \evensidemargin=-0.25in \textwidth=7in
%\topmargin=-0.25in \headsep=0.2in \textheight=8.75in
%\usepackage[dvips,colorlinks=true]{hyperref}
%\hypersetup{
% bookmarksnumbered=true,
% linkcolor=black,
% citecolor=black,
% pagecolor=black,
% urlcolor=black,
% hyperfigures =true,
% hyperfootnotes=true,
%}
\input{abbreviations}
\setlength\arraycolsep{1pt}
\newtheorem{definition}{Definition}
\newtheorem{corollary}{Corollary}
\newtheorem{remark}{Remark}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{prof}{Proof}
\newtheorem{assumption}{Assumption}
\def\IR{{\mathbb R}}
\def\IC{{\mathbb C}}
\newcommand{\test}{\mbox{$
\begin{array}{c}
\stackrel{
\stackrel{\textstyle H_1}{\textstyle >}
}
{
\stackrel{\textstyle <}{\textstyle H_0}
}
\end{array}
$}}
\renewcommand{\baselinestretch}{1.6}
\begin{document}
\section{Appendix: Modeling 3GPP LTE Control Channel Constraints}
Note that by placing restrictions on the location where a particular user's control packet can be sent and the size of that packet, the system can reduce the number of blind decoding attempts that have to be made by that user in order to receive its control packet. We note that a user is unaware of whether there is a control packet intended for it and consequently must check all possible locations where its control packet could be present assuming each possible packet size. Each control packet carries a CRC bit sequence scrambled using the unique user identifier which helps the user deduce whether the examined packet is meant for it. % \cite{3gpp:rel8}.
In the 3GPP LTE system, the minimum allocation unit in the downlink control channel is referred to as the control channel element (CCE). Let $\{1,\cdots,R\}$ be a set of CCEs available for conveying UL grants. A contiguous chunk of CCEs from $\{1,\cdots,R\}$ that can be be assigned to a user is referred to as a PDCCH. The size of each PDCCH is referred to as an aggregation level and must belong to the set $\{1,2,4,8\}$. Let $\Dc$ denote the set of all possible such PDCCHs. For each user the BS first decides an aggregation level, based on its average (long-term) SINR. Then, using that users' unique identifier (ID) together with its aggregation level, the BS obtains a small subset of non-overlapping PDCCHs from $\Dc$ (of cardinality no greater than $6$) that are eligible to be assigned to that user. Let $\Dc_u$ denote this subset of eligible PDCCHs for a user $u$. Then, if user $u$ is scheduled only one PDCCH from $\Dc_u$ must be assigned to it, i.e., must be used to convey its UL grant. Note that while the PDCCHs that belong to the eligible set of any one user are non-overlapping, those that belong to eligible sets of any two different users can overlap.
As a result, the BS scheduler must also enforce the constraint that two PDCCHs that are assigned to two different scheduled users, respectively, must not overlap.
Next, the constraint that each scheduled user can be assigned only one PDCCH from its set of eligible PDCCHs can be enforced as follows. First, define a set $\Vc_u$ containing $|\Dc_u|$ {\em virtual users} for each user $u,\;1\leq u\leq K$, where each virtual user in $\Vc_u$ is associated with a unique PDCCH in $\Dc_u$ and all the parameters (such as uplink channels, queue size etc.) corresponding to each virtual user in $\Vc_u$ are identical to those of user $u$.
Let $\tilde{\Uk}$ be the set of all possible subsets of such virtual users, such that each subset has a cardinality no greater than $T$ and contains no more than one virtual user corresponding to the same user. Defining $\tilde{\Mk}=\tilde{\Uk}\times\Ck$, we can then pose (P1) over $\tilde{\Mk}$ after setting $L=K$ with $\Gc_s=\Vc_s,\;1\leq s\leq K$. Consequently, by defining the virtual users corresponding to each user as being mutually incompatible, we have enforced the constraint that at-most one virtual user for each user can be selected, which in turn is equivalent to enforcing that each scheduled user can be assigned only one PDCCH from its set of eligible PDCCHs.
Finally, consider the set of all eligible PDCCHs, $\{\Dc_u\}_{u=1}^K$. Note that this set is decided by the set of active users and their long-term SINRs. % and can be regarded as invariant in the schceduling
Recall that each PDCCH in $\{\Dc_u\}_{u=1}^K$ maps to a unique virtual user.
To ensure that PDCCHs that are assigned to two virtual users corresponding to two different users do not overlap, we can define multiple binary knapsack constraints. Clearly $R$ such knapsack constraints suffice (indeed can be much more than needed), where each constraint corresponds to one CCE and has a weight of one for every pair $(\tilde{\Uc},\cb)\in\tilde{\Mk}$ wherein $\tilde{\Uc}$ contains a virtual user corresponding to a PDCCH which includes that CCE. Then, a useful consequence of the fact that in LTE the set $\Dc_u$ for each user $u$ is extracted from $\Dc$ via a well designed hash function (which accepts each user's unique ID as input), is that these resulting knapsack constraints are {\em column-sparse}.
\section{Appendix: Proposition I and its Proof}
\begin{proposition}
Let $\hat{W}^{\rm opt,narrow}$ denote the optimal weighted sum rate obtained by solving (P1) albeit where all pairs $(\Uc,\cb)$ are restricted to lie in $\Mk^{\rm narrow}$. Then, we have that
\begin{eqnarray}\label{eq:pRAlte2}
\hat{W}^{\rm narrow}\geq
\frac{\hat{W}^{\rm opt,narrow}}{1+T+\Delta+2J}.
\end{eqnarray}
\end{proposition}
\proof Note that Algorithm IIa builds up the stack $\Sc$ in $N$ steps. In particular let $S_j,\;j=1,\cdots,N$ be the element that is added in the $j^{th}$ step and note that either $S_j=\phi$ or it is equal to some pair $(\Uc_j^*,\cb_j^*)$. We use two functions $p^{(j)}_1: \Mk^{\rm narrow}\to\Reals_+$ and $p^{(j)}_2: \Mk^{\rm narrow}\to \Reals_+$ for $j=0,\cdots,N$ to track the function $p'(,)$ as the stack $\Sc$ is being built up over $N$ steps and in particular we set
$p^{(0)}_1(\Uc,\cb)=0,\;\forall\;(\Uc,\cb)\in\Mc^{\rm narrow}$ and
$p^{(0)}_2(\Uc,\cb)=p(\Uc,\cb),\;\forall\;(\Uc,\cb)\in\Mc^{\rm narrow}$. %Note that we use the functions
%$\{p^{(j)}_2(\Uc,\cb)\}$ These
For our problem at hand, we define $\{p^{(j)}_1(\Uc,\cb),p^{(j)}_2(\Uc,\cb)\}$ recursively as
\begin{eqnarray}\label{eq:pRAlte3}
\nonumber p^{(j)}_1(\Uc,\cb) &=& \left\{\begin{array}{c} (p^{(j-1)}_2(\Uc_j^*,\cb_j^*))^+\Xc\left(p^{(j-1)}_2(\Uc,\cb)>0\right),\;\; \;{\rm If}\;\cb_j^*\cap\cb\neq \phi \\
(p^{(j-1)}_2(\Uc_j^*,\cb_j^*))^+\Xc\left(p^{(j-1)}_2(\Uc,\cb)>0\right),
{\rm Else If}\;\exists\;\Gc_s:\Uc\cap\Gc_s\neq\phi\;\&\;\Uc^*_j\cap\Gc_s\neq \phi\\
(p^{(j-1)}_2(\Uc_j^*,\cb_j^*))^+\Xc\left(p^{(j-1)}_2(\Uc,\cb)>0\right),\;\; {\rm Else If}\;\exists\;q\in\Ic:\alpha^q( \Uc,\cb)=\alpha^q(\Uc_j^*,\cb_j^*)=1\\
2(p^{(j-1)}_2(\Uc_j^*,\cb_j^*))^+\Xc\left(p^{(j-1)}_2(\Uc,\cb)>0\right)\max_{1\leq q\leq J}\beta^q( \Uc,\cb),\;\;{\rm Otherwise}\end{array}\right.\\
p^{(j)}_2(\Uc,\cb)&=& p^{(j-1)}_2(\Uc,\cb) - p^{(j)}_1(\Uc,\cb),
\end{eqnarray}
where $(x)^+=\max\{x,0\},\;x\in\Reals$, $\Xc(.)$ denotes the indicator function and $(\Uc_j^*,\cb_j^*)=\arg\max_{(\Uc,\cb)\in\Mk^{\rm narrow}\atop {\rm Tail}(\cb)=j}p^{(j-1)}_2 (\Uc,\cb)$. Hence, we have that
\begin{eqnarray}
p^{(j-1)}_2(\Uc,\cb) = p^{(j)}_2(\Uc,\cb) + p^{(j)}_1(\Uc,\cb),\;\;\forall\; (\Uc,\cb)\in\Mk^{\rm narrow},\;j=1,\cdots,N.
\end{eqnarray}
It can be noted that
\begin{eqnarray}\label{eq:pRAlte4}
\nonumber p^{(j)}_2(\Uc,\cb) \leq 0,\;\;\forall\; (\Uc,\cb)\in\Mk^{\rm narrow}: {\rm Tail}(\cb)\leq j\\
p^{(k)}_2(\Uc,\cb) \leq p^{(j)}_2(\Uc,\cb),\;\;\forall\; (\Uc,\cb)\in\Mk^{\rm narrow}\;\&\;k\geq j.
\end{eqnarray}
Further, to track the stack $\Sc'$ which is built in the while loop of the algorithm, we define stacks $\{\Sc^*_j\}_{j=0}^N$ where $\Sc_N^*=\phi$ and $\Sc_j^*$ is the value of $\Sc'$ after the Algorithm has tried to add $\cup_{m=j+1}^N S_m$ to $\Sc'$ (starting from $\Sc'=\phi$) so that $\Sc_0^*$ is the stack $\Sc'$ that is the output of the Algorithm. Note that $\Sc_{j+1}^*\subseteq\Sc_j^*\subseteq \Sc_{j+1}^*\cup S_{j+1}$.
Next, for $j=0,\cdots,N$, we let $W^{(j)\;{\rm opt}}$ denote the optimal solution to (P1) but where $\Mk$ is replaced by
$\Mk^{\rm narrow}$ and the function $p(,)$ is replaced by $p_2^{(j)}(,)$. Further, let $W^{(j)}=\sum_{(\Uc,\cb)\in \Sc_j^*}p_2^{(j)}(\Uc,\cb)$ and note that $\hat{W}^{\rm opt, narrow}=W^{(0)\;{\rm opt}}$ and $\hat{W}^{\rm narrow}=W^{(0)}$.
We will show via induction that
\begin{eqnarray}\label{eq:pRAlte5}
W^{(j)\;{\rm opt}}\leq (T+1+\Delta+2J)W^{(j)},\;\forall\;j=N,\cdots,0,
\end{eqnarray}
which includes the claim in (\ref{eq:pRAlte2}) at $j=0$.
First note that the base case $W^{(N)\;{\rm opt}}\leq (T+1+\Delta+2J)W^{(N)}$ is readily true since $\Sc_N^*=\phi$ and
$p^{(N)}_2(\Uc,\cb) \leq 0,\;\;\forall\; (\Uc,\cb)\in\Mk^{\rm narrow}$. Then,
assume that (\ref{eq:pRAlte5}) holds for some $j$. We focus only on the main case in which $S_j=(\Uc_j^*,\cb_j^*)\neq \phi$ (the remaining case holds trivially true). Note that
since $(\Uc_j^*,\cb_j^*)$ is added to the stack $\Sc$ in the algorithm, $p^{(j-1)}_2 (\Uc_j^*,\cb_j^*)>0$. Then from the update formulas (\ref{eq:pRAlte3}), we must have
that $p^{(j)}_2 (\Uc_j^*,\cb_j^*)=0$. Using the fact that $\Sc_{j-1}^*\subseteq \Sc_{j}^*\cup (\Uc_j^*,\cb_j^*)$ together with the induction hypothesis, we can conclude that
\begin{eqnarray}\label{eq:pRAlte5b}
W^{(j)}=\sum_{(\Uc,\cb)\in \Sc_j^*}p_2^{(j)}(\Uc,\cb)=\sum_{(\Uc,\cb)\in \Sc_{j-1}^*}p_2^{(j)}(\Uc,\cb)\geq
\frac{W^{(j)\;{\rm opt}}}{T+1+\Delta+2J}.
\end{eqnarray}
Upon invoking Lemma \ref{lem:prophelp}, which is stated and proved below, we obtain that
\begin{eqnarray}\label{eq:pRAlte6}
\sum_{(\Uc,\cb)\in \Sc_{j-1}^*}p_1^{(j)}(\Uc,\cb)\geq p^{(j-1)}_2 (\Uc_j^*,\cb_j^*).
\end{eqnarray}
Then, let $V^{(j)\;{\rm opt}}$ denote the optimal solution to (P1) but where $\Mk$ is replaced by
$\Mk^{\rm narrow}$ and the function $p(,)$ is replaced by $p_1^{(j)}(,)$. Upon invoking Lemma \ref{lem:prophelp2}, also stated and proved below, we can conclude that
\begin{eqnarray}\label{eq:pRAlte7}
p^{(j-1)}_2 (\Uc_j^*,\cb_j^*)\geq
\frac{V^{(j)\;{\rm opt}}}{T+1+\Delta+2J}.
\end{eqnarray}
%Towards this end, from (\ref{eq:pRAlte3}) we note that for any pair $(\Uc,\cb)\in\Mk^{\rm narrow}$, $p_1^{(j)}(\Uc,\cb)\leq p^{(j-1)}_2 (\Uc_j^*,\cb_j^*)$. Let $\Vc_1^{(j)\;{\rm opt}}$ be an optimal allocation of pairs that results in $V^{(j)\;{\rm opt}}$. For any two pairs $(\Uc_1,\cb_1),(\Uc_2,\cb_2)\in \Vc_1^{(j)\;{\rm opt}}$ we must have that for each $\Gc_s\;1\leq s\leq L$, at-least one of $\Uc_1\cap\Gc_s$ and $\Uc_2\cap\Gc_s$ is $\phi$, as well as $\cb_1\cap\cb_2=\phi$. In addition, $|\Uc_1|$ and $|\Uc_2|$ are no greater than $T$. Thus we can have at-most $T$ such pairs $\{(\Uc,\cb)\}$ in $\Vc_1^{(j)\;{\rm opt}}$ for which $\exists\;\Gc_s:\Uc\cap\Gc_s\neq\phi\;\&\;\Uc^*_j\cap\Gc_s\neq \phi$. Further, using the first inequality in (\ref{eq:pRAlte4}) we see that any pair $(\Uc,\cb)$ for which $\cb\cap\cb_j^*\neq \phi$ and $p_1^{(j)}(\Uc,\cb)= p^{(j-1)}_2 (\Uc_j^*,\cb_j^*)$ must have ${\rm Tail}(\cb)\geq j$ so that $j\in\cb$. Thus, $\Vc_1^{(j)\;{\rm opt}}$ can include at-most one pair $(\Uc,\cb)$ for which $\cb\cap\cb_j^*\neq \phi$. Next, there can be at-most $\Delta$ constraints in $\Ic$ for which $\alpha^q(\Uc_j^*,\cb_j^*)=1,q\in\Ic$ is satisfied. For each such constraint $q\in\Ic$ we can pick at-most one pair $(\Uc,\cb)$ for which $\alpha^q(\Uc,\cb)=1$ and $p_1^{(j)}(\Uc,\cb)= p^{(j-1)}_2 (\Uc_j^*,\cb_j^*)$. Thus, $\Vc_1^{(j)\;{\rm opt}}$ can include at-most $\Delta$ such pairs, one for each constraint.
% Now the remaining pairs in $\Vc_1^{(j)\;{\rm opt}}$ (whose users do not intersect $\Uc_j^*$ and whose chunks do not intersect $\cb_j^*$ and which do not violate any binary knapsack constraint in the presence of $(\Uc_j^*,\cb_j^*)$) must satisfy the generic knapsack constraints. Let these pairs form the
% set $\tilde{\Vc}_1^{(j)\;{\rm opt}}$ so that,
% \begin{eqnarray*}
% \sum_{(\Uc,\cb)\in \tilde{\Vc}_1^{(j)\;{\rm opt}}}p_1^{(j)}(\Uc,\cb)=\sum_{(\Uc,\cb)\in \tilde{\Vc}_1^{(j)\;{\rm opt}}}2p^{(j-1)}_2 (\Uc_j^*,\cb_j^*)\max_{1\leq q\leq J}\beta^q(\Uc ,\cb)\leq 2p^{(j-1)}_2 (\Uc_j^*,\cb_j^*)\sum_{q=1}^J\sum_{(\Uc,\cb)\in \tilde{\Vc}_1^{(j)\;{\rm opt}}}\beta^q(\Uc ,\cb)\\
% \leq 2Jp^{(j-1)}_2 (\Uc_j^*,\cb_j^*).
% \end{eqnarray*}
%Combining these observations we have that
%\begin{eqnarray}
% V^{(j)\;{\rm opt}}= \sum_{(\Uc,\cb)\in \Vc_1^{(j)\;{\rm opt}}}p_1^{(j)}(\Uc,\cb)\leq (1+T+\Delta+2J)p^{(j-1)}_2 (\Uc_j^*,\cb_j^*),
% \end{eqnarray}
%which is the desired result in (\ref{eq:pRAlte7}).
Thus, using (\ref{eq:pRAlte5b}), (\ref{eq:pRAlte6}) and (\ref{eq:pRAlte7}) we can conclude that
\begin{eqnarray}
(1+T+\Delta+2J) \sum_{(\Uc,\cb)\in \Sc_{j-1}^*}(\underbrace{p_1^{(j)}(\Uc,\cb)+p_2^{(j)}(\Uc,\cb)}_{p_2^{(j-1)}(\Uc,\cb)}\geq V^{(j)\;{\rm opt}} + W^{(j)\;{\rm opt}}\geq W^{(j-1)\;{\rm opt}}.
\end{eqnarray}
which proves the induction step and proves the claim in (\ref{eq:pRAlte2}). \endproof
\begin{lemma}\label{lem:prophelp}
For all $j$ we have that
\begin{eqnarray}\label{eq:pRAlte6l}
\sum_{(\Uc,\cb)\in \Sc_{j-1}^*}p_1^{(j)}(\Uc,\cb)\geq p^{(j-1)}_2 (\Uc_j^*,\cb_j^*).
\end{eqnarray}
\end{lemma}
\proof
Suppose that $\Sc_{j-1}^*= \Sc_{j}^*\cup (\Uc_j^*,\cb_j^*) $. Then, recalling (\ref{eq:pRAlte3}) we can deduce that (\ref{eq:pRAlte6l}) is true since $p_1^{(j)}(\Uc_j^*,\cb_j^*)= p^{(j-1)}_2 (\Uc_j^*,\cb_j^*)$.
Suppose now that $\Sc_{j-1}^*= \Sc_{j}^*$. In this case we can have two possibilities. In the first one $(\Uc_j^*,\cb_j^*)$ cannot not be added to $\Sc_{j}^*$ due to the presence of a pair
$(\Uc',\cb')\in\Sc_j^*$ for which at-least one of these three conditions are satisfied: $\exists\;\Gc_s:\Uc'\cap\Gc_s\neq\phi\;\&\;\Uc^*_j\cap\Gc_s\neq \phi$; $\cb'\cap\cb_j^*\neq \phi$ and $\exists\;q\in\Ic:\alpha^q( \Uc',\cb')=\alpha^q(\Uc_j^*,\cb_j^*)$=1 . Since any pair $(\Uc',\cb')\in\Sc_j^*$ was added to $\Sc$ in the algorithm after the $j^{th}$ step, from the second inequality in (\ref{eq:pRAlte4}) we must have that $p^{(j-1)}_2(\Uc',\cb')>0$. Recalling (\ref{eq:pRAlte3}) we can then deduce that $p_1^{(j)}(\Uc',\cb')= p^{(j-1)}_2 (\Uc_j^*,\cb_j^*)$ which proves (\ref{eq:pRAlte6l}). In the second possibility, $(\Uc_j^*,\cb_j^*)$ cannot not be added to $\Sc_{j}^*$ due to a generic knapsack constraint being violated. In other words, for some $q\in\{1,\cdots,J\}$, we have that
\begin{eqnarray}
\sum_{(\Uc ,\cb)\in\Sc_j^*}\beta^q(\Uc ,\cb)>1-\beta^q(\Uc_j^*,\cb_j^*).
\end{eqnarray}
Since $(\Uc_j^*,\cb_j^*)\in\Mk^{\rm narrow}$, $\beta^q(\Uc_j^*,\cb_j^*)\leq 1/2$ so that
\begin{eqnarray}
2\sum_{(\Uc ,\cb)\in\Sc_j^*}\max_{1\leq q\leq J}\beta^q(\Uc ,\cb)\geq 2 \sum_{(\Uc ,\cb)\in\Sc_j^*}\beta^q(\Uc ,\cb)>1,
\end{eqnarray}
which along with (\ref{eq:pRAlte3}) also proves (\ref{eq:pRAlte6l}). Thus, we have established the claim in (\ref{eq:pRAlte6l}).\endproof
\begin{lemma}\label{lem:prophelp2}
Let $V^{(j)\;{\rm opt}}$ denote the optimal solution to (P1) but where $\Mk$ is replaced by
$\Mk^{\rm narrow}$ and the function $p(,)$ is replaced by $p_1^{(j)}(,)$. Then, we have that
\begin{eqnarray}\label{eq:pRAlte7l}
p^{(j-1)}_2 (\Uc_j^*,\cb_j^*)\geq
\frac{V^{(j)\;{\rm opt}}}{T+1+\Delta+2J}.
\end{eqnarray}
\end{lemma}
\proof
First, from (\ref{eq:pRAlte3}) we note that for any pair $(\Uc,\cb)\in\Mk^{\rm narrow}$, $p_1^{(j)}(\Uc,\cb)\leq p^{(j-1)}_2 (\Uc_j^*,\cb_j^*)$. Let $\Vc_1^{(j)\;{\rm opt}}$ be an optimal allocation of pairs that results in $V^{(j)\;{\rm opt}}$. For any two pairs $(\Uc_1,\cb_1),(\Uc_2,\cb_2)\in \Vc_1^{(j)\;{\rm opt}}$ we must have that for each $\Gc_s\;1\leq s\leq L$, at-least one of $\Uc_1\cap\Gc_s$ and $\Uc_2\cap\Gc_s$ is $\phi$, as well as $\cb_1\cap\cb_2=\phi$. In addition, $|\Uc_1|$ and $|\Uc_2|$ are no greater than $T$. Thus we can have at-most $T$ such pairs $\{(\Uc,\cb)\}$ in $\Vc_1^{(j)\;{\rm opt}}$ for which $\exists\;\Gc_s:\Uc\cap\Gc_s\neq\phi\;\&\;\Uc^*_j\cap\Gc_s\neq \phi$. Further, using the first inequality in (\ref{eq:pRAlte4}) we see that any pair $(\Uc,\cb)$ for which $\cb\cap\cb_j^*\neq \phi$ and $p_1^{(j)}(\Uc,\cb)= p^{(j-1)}_2 (\Uc_j^*,\cb_j^*)$ must have ${\rm Tail}(\cb)\geq j$ so that $j\in\cb$. Thus, $\Vc_1^{(j)\;{\rm opt}}$ can include at-most one pair $(\Uc,\cb)$ for which $\cb\cap\cb_j^*\neq \phi$. Next, there can be at-most $\Delta$ constraints in $\Ic$ for which $\alpha^q(\Uc_j^*,\cb_j^*)=1,q\in\Ic$ is satisfied. For each such constraint $q\in\Ic$ we can pick at-most one pair $(\Uc,\cb)$ for which $\alpha^q(\Uc,\cb)=1$ and $p_1^{(j)}(\Uc,\cb)= p^{(j-1)}_2 (\Uc_j^*,\cb_j^*)$. Thus, $\Vc_1^{(j)\;{\rm opt}}$ can include at-most $\Delta$ such pairs, one for each constraint.
Now the remaining pairs in $\Vc_1^{(j)\;{\rm opt}}$ (whose users do not intersect $\Uc_j^*$ and whose chunks do not intersect $\cb_j^*$ and which do not violate any binary knapsack constraint in the presence of $(\Uc_j^*,\cb_j^*)$) must satisfy the generic knapsack constraints. Let these pairs form the
set $\tilde{\Vc}_1^{(j)\;{\rm opt}}$ so that,
\begin{eqnarray*}
\sum_{(\Uc,\cb)\in \tilde{\Vc}_1^{(j)\;{\rm opt}}}p_1^{(j)}(\Uc,\cb)=\sum_{(\Uc,\cb)\in \tilde{\Vc}_1^{(j)\;{\rm opt}}}2p^{(j-1)}_2 (\Uc_j^*,\cb_j^*)\max_{1\leq q\leq J}\beta^q(\Uc ,\cb)\leq 2p^{(j-1)}_2 (\Uc_j^*,\cb_j^*)\sum_{q=1}^J\sum_{(\Uc,\cb)\in \tilde{\Vc}_1^{(j)\;{\rm opt}}}\beta^q(\Uc ,\cb)\\
\leq 2Jp^{(j-1)}_2 (\Uc_j^*,\cb_j^*).
\end{eqnarray*}
Combining these observations we have that
\begin{eqnarray}
V^{(j)\;{\rm opt}}= \sum_{(\Uc,\cb)\in \Vc_1^{(j)\;{\rm opt}}}p_1^{(j)}(\Uc,\cb)\leq (1+T+\Delta+2J)p^{(j-1)}_2 (\Uc_j^*,\cb_j^*),
\end{eqnarray}
which is the desired result in (\ref{eq:pRAlte7l}).\endproof
\end{document}