Optimal Online Algorithms for One-Way Trading and Online Knapsack Problems: A Unified Competitive Analysis

Ying Cao, Bo Sun and Danny H.K. Tsang This work was supported by the Hong Kong Research Grants Councils General Research Fund through Project 16211220. The authors are with Dept. of Electronic and Computer Engineering, the Hong Kong University of Science and Technology. Emails: {ycaoan, bsunaa, eetsang}@ust.hk

Abstract

We study two canonical online optimization problems under capacity/budget constraints: the fractional one-way trading problem (OTP) and the integral online knapsack problem (OKP) under an infinitesimal assumption. Under the competitive analysis framework, it is well-known that both problems have the same optimal competitive ratio. However, these two problems are investigated by distinct approaches under separate contexts in the literature. There is a gap in understanding the connection between these two problems and the nature of their online algorithm design. This paper provides a unified framework for the online algorithm design, analysis and optimality proof for both problems. We find that the infinitesimal assumption of the OKP is the key that connects the OTP in the analysis of online algorithms and the construction of worst-case instances. With this unified understanding, our framework shows its potential for analyzing other extensions of OKP and OTP in a more systematic manner.

I INTRODUCTION

Online optimization under capacity/budget constraints is a classical and challenging problem. Two well-known examples are the one-way trading problem (OTP) and the online knapsack problem (OKP).

In the OTP, an investor plans to trade a total amount of 1 dollar into yen. The exchange rates $p_{i}$ arrive online and are bounded, i.e., $p_{i}\in[L,U]$ , and the investor must immediately decide how much to trade at each exchange rate. If $x_{i}$ dollars are traded at the $i$ th exchange rate $p_{i}$ , $p_{i}x_{i}$ is the amount of yen the investor gains. Let $N$ denote the total number of exchange rates. The goal is to maximize the amount of yen traded after processing the $N$ th exchange rate $\sum_{i=1}^{N}p_{i}x_{i}$ , while respecting the budget limit $\sum_{i=1}^{N}x_{i}\leq 1$ . It is well-known that $(\ln(U/L)+1)$ -competitive algorithms can be designed, e.g., the threat-based algorithm in [1] and the CR-Pursuit algorithm in [2].

The 0-1 knapsack problem is a classic problem in computer science, where a decision-maker maximizes the total value of the items selected while the total weight does not exceed the normalized knapsack capacity limit of $1$ . In the OKP, the items come one by one. The value $v_{i}$ and the weight $w_{i}$ of the $i$ th item are only revealed upon its arrival. An online decision is made on whether to accept the item ( $z_{i}=1$ ) or not ( $z_{i}=0$ ). There exist no online algorithms with bounded competitive ratios for the OKP in the general setting [3]. However, ( $\ln(U/L)+1$ )-competitive algorithms can be designed [4, 5, 6] under the bounded value-to-weight ratio assumption (i.e., $v_{i}/w_{i}\in[L,U]$ ) and the infinitesimal assumption that the weight of each item is much smaller than the capacity (i.e., $\max_{i}w_{i}\ll 1$ ). The infinitesimal assumption is a technical simplification, but it has been shown to hold in practical applications such as cloud computing systems [6] and is widely accepted in the literature. In this paper, we make the same assumptions.

Both problems have appeared in numerous applications, including portfolio selection, cloud resource allocation, keyword auctions, etc. Thus, considerable attention has been paid to both problems and their many variants. Unbounded prices [7] and interrelated prices [8] have been considered for the OTP recently, and knapsacks with unknown capacity [9] and removable items [10] are interesting generalizations for the OKP. Additionally, different arrival models have been studied, such as stochastic arrivals [11, 12] and random order [13]. In this paper, we make no assumptions on the arrival model.

Motivated by the gaps in the understanding of the nature of challenges in the online algorithm design, we aim to unify the online algorithms for the OTP and the OKP into one algorithmic framework, namely, a threshold-based algorithm, the competitive performance of which mainly depends on the threshold function. We provide a sufficient condition on the threshold function that can ensure a bounded competitive ratio, and design the best possible threshold function based on this sufficient condition. Finally, we derive the lower bound of the competitive ratios of the OTP and the OKP. Although all results match those in the literature, the existing works approach the results by distinct methods and lack a systematic way of designing and analyzing related problems. This paper mainly focuses on the analysis and proofs rather than on the results. Our contributions are two-fold.

•

We unify the online algorithms for the OTP and the OKP into a threshold-based algorithm and show that the unified algorithm can achieve the optimal competitive ratios under a unified competitive analysis.
•

We provide new proofs for the lower bound of competitive ratios for the OTP and the OKP. The connection between these two problems is founded in the construction of the worst-case instances.

II A UNIFIED ALGORITHM and Our Results

II-A Notations

Since the two problems have originally distinct sets of terms, we unify the notations for the brevity of problem formulation and clarify the different meanings here. Let $x_{i}$ denote the amount of dollars traded at the $i$ th exchange rate for the OTP, while for the OKP, it represents the capacity used after processing the $i$ th item $w_{i}z_{i}$ . Let $b_{i}$ denote the exchange rate (i.e., $p_{i}$ ) in the OTP and the value-to-weight ratio of the $i$ th item in the OKP (i.e., ${v_{i}}/{w_{i}}$ ). The following optimization problem characterizes the offline problem of the OTP:

$\displaystyle\underset{\bm{x}}{\text{maximize}}$	$\displaystyle\sum_{i=1}^{N}b_{i}x_{i}$	(1)
$\displaystyle{\rm s.t.}$	$\displaystyle\sum_{i=1}^{N}x_{i}\leq 1,$
	$\displaystyle x_{i}\geq 0,\forall i\in[N].$

The dual problem of (1) is

	$\displaystyle\underset{\lambda}{\text{minimize}}$	$\displaystyle\lambda$		(2)
	$\displaystyle{\rm s.t}.$	$\displaystyle\lambda\geq b_{i},\forall i\in[N].$		(2)

By changing the last constraint of (1) to $0\leq x_{i}\leq w_{i}$ , the resulting problem serves as an upper bound of the OKP due to the LP relaxation, and its dual is

$\displaystyle\underset{\lambda,\bm{\beta}}{\text{minimize}}$	$\displaystyle\lambda+\sum_{i=1}^{N}w_{i}\beta_{i}$	(3)
$\displaystyle{\rm s.t.}$	$\displaystyle\lambda+\beta_{i}\geq b_{i},\forall i\in[N],$
	$\displaystyle\lambda\geq 0,\beta_{i}\geq 0,\forall i\in[N],$

where $\lambda$ and $\beta_{i}$ s are the dual variables of the corresponding dual programs.

II-B A Unified Algorithm

Both the OTP and the OKP target allocating one budget-constrained resource sequentially. Since the current decision affects the future decisions through the budget constraint, we need an estimation of the value of the remaining resource to facilitate decision-making. We use a threshold function to estimate the value of resources.

Definition 1.

A threshold function $\phi(y):[0,1]\to[0,\infty)$ estimates the marginal cost of a resource at utilization $y$ .

Denote the utilization level after the $i$ th arrival by $y^{(i)}$ . Given $\phi(y)$ , we can estimate the pseudo-cost of allocating $x_{i}$ amount of resource by $\int_{y^{(i-1)}}^{y^{(i-1)}+x_{i}}\phi(\delta)d\delta$ . Our unified algorithm then decides $x_{i}$ that maximizes the pseudo-revenue $b_{i}x_{i}-\int_{y^{(i-1)}}^{y^{(i-1)}+x_{i}}\phi(\delta)d\delta$ . The overall algorithm is summarized in Algorithm 1.

Algorithm 1 A Unified Algorithm

Initialize:

\phi(y)

y^{(0)}=0

b_{i}\in[L,U]

;

for the

i

th time slot do

x_{i}=\arg\max_{x\in\mathbb{S}}b_{i}x-\int_{y^{(i-1)}}^{y^{(i-1)}+x}\phi(\delta)d\delta.

2. Update

y^{(i)}=y^{(i-1)}+x_{i}

;

3. If

y^{(i)}>1,x_{i}=0.

end for

$\mathbb{S}$ denotes the set of all positive real numbers for the OTP and the set $\{0,w_{i}\}$ for the OKP, separately. Note that for the OKP, step 1 reduces to $x_{i}=\begin{cases}w_{i},&b_{i}\geq\phi(y^{(i-1)})\\ 0,&otherwise\end{cases}$ , which corresponds to the update equation in [4]. Algorithm 1 can be easily applied in the posted-price setting by its nature.

II-C Main Results

A standard measure for the performance of an online algorithm is the competitive ratio. Under the unified notation, define an arrival instance $\mathcal{A}$ as $\{b_{i}\}_{\forall i\in[N]}$ for the OTP, and as $\{b_{i},w_{i}\}_{\forall i\in[N]}$ for the OKP. Denote the objective value achieved by the online algorithm and the offline optimal by $\text{ALG}(\mathcal{A})$ and $\text{OPT}(\mathcal{A})$ , respectively, given the arrival instance $\mathcal{A}$ . If $\alpha=\max_{\mathcal{A}}{}\frac{\text{OPT}(\mathcal{A})}{\text{ALG}(\mathcal{A})}$ , then we say the online algorithm is $\alpha$ -competitive. The competitive ratio of Algorithm 1 depends only on the choice of the function $\phi$ . We find the sufficient conditions for $\phi$ for Algorithm 1 to be $\alpha$ -competitive in the following theorem.

Theorem 2 (Sufficiency).

Algorithm 1 is $\alpha$ -competitive for both the OTP and the OKP if $\phi$ is given by

\phi(y)=\left\{\begin{array}[]{cc}L&y\in[0,\omega]\\ \varphi(y)&y\in[\omega,1]\end{array},\right.

where $\omega$ is a budget/capacity utilization level that satisfies $\frac{1}{\alpha}\leq\omega\leq 1$ , and $\varphi(y)$ is an increasing function that satisfies

\left\{\begin{array}[]{l}\varphi(y)\geq\frac{1}{\alpha}\varphi^{\prime}(y),y\in[\omega,1]\\ \varphi(\omega)=L,\varphi(1)\geq U.\end{array}\right.

(4)

In the theorem, $\phi$ is composed of two segments, one constant and the other exponential. Note that the functions used in [4] and [6] satisfy the conditions. However, the basis of the functions is unknown; the authors do not explain the intuition behind the functions nor rigorously characterize the properties of the functions. In contrast, by the following theorem, we can characterize the performance limit over the space of all eligible functions and rigorously show the function that admits the smallest (best) competitive ratio.

Theorem 3.

Given $L$ and $U$ , the best competitive ratio that can be achieved by Algorithm 1 is $(\ln\theta+1)$ , where $\theta=U/L$ , and the corresponding $\phi^{*}$ is unique.

We show that no other online algorithms can perform better than Algorithm 1 using the following theorem.

Theorem 4.

Given $L$ and $U$ , $(\ln\theta+1)$ is the lowest possible competitive ratio for both the OTP and the OKP.

In the next section, we introduce the primal-dual analysis framework, with which we prove Theorem 2. Subsequently, we prove Theorem 3 by Gronwall’s inequality. In Section IV, we show Theorem 4 by adversarial arguments.

III COMPETITIVE ANALYSIS

III-A Primal-Dual Competitive Analysis

Given the arrival instance $\mathcal{A}$ , we denote the primal and dual objective values after processing $b_{n}$ by $P_{n}(\mathcal{A})$ and $D_{n}(\mathcal{A})$ , respectively. For simplicity, we drop the parenthesis and write $P_{n}$ and $D_{n}$ hereafter. We briefly introduce the framework by giving the following lemma.

Lemma 1.

An online algorithm is $\alpha$ -competitive if it can determine the primal variables $x$ and construct dual variables $\lambda$ based on the primal variables such that

•

(Feasible Solutions) $x$ and $\lambda$ are feasible solutions of the primal and the dual,
•

(Initial Inequality) there exists an index $k\in[N]\cup\{0\}$ such that $P_{k}\geq\frac{1}{\alpha}D_{k}$ ,
•

(Incremental Inequalities) for $i\in\{k+1,\dots,N\}$ ,

$P_{i}-P_{i-1}\geq\frac{1}{\alpha}(D_{i}-D_{i-1}).$

Proof.

The primal feasibility is trivial since any online algorithm must first produce a feasible solution to the problem. It suffices to prove $P_{N}\geq\frac{1}{\alpha}D_{N}$ since

\text{ALG}=P_{N}\geq\frac{1}{\alpha}D_{N}\overset{(a)}{\geq}\frac{1}{\alpha}D^{*}\overset{(b)}{\geq}\frac{1}{\alpha}\text{OPT},

where ( $a$ ) is due to the dual feasibility, and ( $b$ ) is due to the weak duality. Suppose there exists a $k$ such that $P_{i}-P_{i-1}\geq\frac{1}{\alpha}(D_{i}-D_{i-1})$ holds for all $i\in\{k+1,\dots,N\}$ , then we have $P_{N}-P_{k}\geq\frac{1}{\alpha}(D_{N}-D_{k}).$ Combining this with the initial inequality leads to $P_{N}\geq\frac{1}{\alpha}D_{N}$ . We thus complete the proof. ∎

Note that the primal-dual competitive analysis framework that we use is more general than those used in the existing works, in that the initial inequality starts from $k\in[N]\cup\{0\}$ rather than the original $0$ .

Next, we show the proofs of Theorems 2 and 3 for the OTP, and highlight the differences between them and those for the OKP.

III-B Analysis of OTP

Proof of Theorem 2.

(Feasible Solutions) First we show that the primal and dual solutions given by Algorithm 1 are feasible:

\displaystyle x_{i}=\begin{cases}\phi^{-1}(b_{i})-y^{(i-1)}&b_{i}\geq\phi(y^{(i-1)})\\ 0&b_{i}<\phi(y^{(i-1)})\end{cases},

(5)

where $\phi^{-1}(b)=\begin{cases}\omega&b=L\\ \varphi^{-1}(b)&b>L\end{cases}$ . (5) ensures $\forall i,x_{i}\geq 0$ , and $\phi(1)\geq U$ ensures $\phi^{-1}(U)\leq 1$ . Since $y^{(N)}=\phi^{-1}(\max_{i\in[N]}b_{i})$ , we have $y^{(N)}\leq\phi^{-1}(U)\leq 1$ . Thus, the primal solutions are feasible. Construct the dual variables as $\lambda_{i}=\phi(y^{(i)}).$ Since $\phi(y)$ is non-decreasing, $\lambda_{N}=\phi(y^{(N)})\geq\phi(y^{(i)}),\forall i\in[N]$ . Thus, $\lambda_{N}$ is a feasible solution to the dual.

(Initial Inequality) For the OTP, $P_{0}=0,D_{0}=\phi(y^{(0)})=L>0$ . When $k\geq 1$ , the primal objective at the end of the $k$ th time slot is $P_{k}=\sum_{i=1}^{k}b_{i}x_{i},$ while the dual objective is $D_{k}=\lambda_{k}=\phi(y^{(k)}).$

Since $y^{(0)}=0$ and $\phi(0)=L\leq b_{i},\forall i$ , by (5), we have

x_{1}=\phi^{-1}(b_{1})=\begin{cases}\omega&b_{1}=L\\ \varphi^{-1}(b_{1})&b_{1}>L\end{cases}.

Because $\varphi(y)$ is an increasing function, we have $x_{1}\geq\omega\geq\frac{1}{\alpha}.$ Since $b_{1}=\phi(x_{1})$ , it follows that

P_{1}=b_{1}x_{1}\geq\frac{b_{1}}{\alpha}=\frac{1}{\alpha}\phi(x_{1})=\frac{1}{\alpha}D_{1}.

(Incremental Inequalities) Next we show the incremental inequalities for $i>1$ . Note that when $x_{i}=0$ , $P_{i}=P_{i-1}$ and $D_{i}=D_{i-1}$ . In this case, the incremental inequality $P_{i}-P_{i-1}\geq\frac{1}{\alpha}(D_{i}-D_{i-1})$ always holds. Thus, we only need to focus on the case where $x_{i}>0,\forall i>1$ , when the behavior of the algorithm is controlled by the second segment of $\phi$ , which satisfies $\varphi(y)\geq\frac{1}{\alpha}\varphi^{\prime}(y)$ for $y\in[\omega,1]$ and two boundary conditions $\varphi(\omega)=L$ and $\varphi(1)\geq U$ .

The change in the primal objective is given as follows:

P_{i}-P_{i-1}=b_{i}x_{i}\overset{(a)}{=}\phi(y^{(i)})x_{i},

where ( $a$ ) is due to (5) and $y^{(i)}=y^{(i-1)}+x_{i}$ .

The change in the dual objective is given as follows: $D_{i}-D_{i-1}=\varphi(y^{(i)})-\varphi(y^{(i-1)}).$ By the Cauchy mean value theorem, for every segment $[y^{(i-1)},y^{(i)}]$ , there exists a $\delta_{i}\in[y^{(i-1)},y^{(i)}]$ such that

\frac{\varphi(y^{(i)})-\varphi(y^{(i-1)})}{y^{(i)}-y^{(i-1)}}=\varphi^{\prime}(\delta_{i}).

Since $\forall y\in[\omega,1],\varphi(y)\geq\frac{1}{\alpha}\varphi^{\prime}(y)$ , and $\varphi(y)$ is increasing, we have $\alpha\varphi(y^{(i)})\geq\alpha\varphi(\delta_{i})\geq\frac{\varphi(y^{(i)})-\varphi(y^{(i-1)})}{y^{(i)}-y^{(i-1)}}.$ Because $y^{(i)}-y^{(i-1)}>0$ , we have $\varphi(y^{(i)})(y^{(i)}-y^{(i-1)})\geq\frac{1}{\alpha}(\varphi(y^{(i)})-\varphi(y^{(i-1)})),$ where the LHS is $P_{i}-P_{i-1}$ , and the RHS is $\frac{1}{\alpha}(D_{i}-D_{i-1})$ . Thus, $P_{i}-P_{i-1}\geq\frac{1}{\alpha}(D_{i}-D_{i-1})$ holds for all $i>1$ .

Therefore, Theorem 2 holds for the OTP. ∎

Theorem 3 characterizes the performance limit of Algorithm 1.

Proof of Theorem 3.

(Best Competitive Ratio) By the differential form of Gronwall’s Inequality [14], if there exists a $\varphi$ that satisfies $\varphi(y)\geq\frac{1}{\alpha}\varphi^{\prime}(y),y\in[\omega,1],$ where $\omega\in[\frac{1}{\alpha},1]$ , it is bounded as follows:

\varphi(y)\leq\varphi(\omega)\exp{\bigg{(}\int_{\omega}^{y}\alpha dt\bigg{)}},y\in[\omega,1].

Substituting the first boundary condition $\varphi(\omega)=L$ , we have $\varphi(y)\leq L\exp{\big{(}\alpha(y-\omega)\big{)}},y\in[\omega,1].$ If the other boundary condition $\varphi(1)\geq U$ holds, it implies $L\exp{\big{(}\alpha(1-\omega)\big{)}}\geq U,$ otherwise $\varphi(1)\leq L\exp{\big{(}\alpha(1-\omega)\big{)}}<U$ , which incurs infeasibility. From the inequality above, we have $\omega\leq 1-\frac{1}{\alpha}\ln\theta.$ A necessary condition for $\omega\geq\frac{1}{\alpha}$ to hold is $1-\frac{1}{\alpha}\ln\theta\geq\frac{1}{\alpha},$ and thus the competitive ratio $\alpha\geq\ln{\theta}+1.$

( $\Phi^{*}$ and Its Uniqueness) When $\alpha$ takes the smallest possible $\alpha^{*}=\ln\theta+1$ , the corresponding $\phi^{*}$ s satisfy

\phi^{*}(y)=\left\{\begin{array}[]{cc}L&y\in[0,\omega]\\ \varphi^{*}(y)&y\in[\omega,1]\end{array},\right.

where $\omega\in[\frac{1}{\ln\theta+1},1]$ and $\varphi^{*}$ s are given by

\left\{\begin{array}[]{l}\varphi^{*}(y)\geq\frac{1}{\ln\theta+1}{\varphi^{*}}^{\prime}(y),y\in[\omega,1]\\ \varphi^{*}(\omega)=L,\varphi^{*}(1)\geq U.\end{array}\right.

(6)

By Gronwall’s inequality, we have

	$\displaystyle\varphi^{*}(y)$	$\displaystyle\leq L\exp\big((\ln\theta+1)(y-\omega)\big{missing})$		(7)
		$\displaystyle\overset{(a)}{\leq}L\exp\big((\ln\theta+1)y-1\big{missing}),y\in[\omega,1],$

where ( $a$ ) is due to $\omega\geq\frac{1}{\ln\theta+1}$ . Then we have $\varphi^{*}(1)\leq L\exp(\ln\theta)=L\theta=U.$ Combining with the second boundary condition $\varphi^{*}(1)\geq U$ , we have $\varphi^{*}(1)=U$ . Substituting this into (7), we have $\omega\leq\frac{1}{\ln\theta+1}.$ Because $\omega\geq\frac{1}{\ln\theta+1}$ as stated in Theorem 2, we have $\omega=\frac{1}{\ln\theta+1}$ . Therefore, the solution space of (6) is equivalent to the solution space of the following differential inequality with equality boundary conditions:

\left\{\begin{array}[]{l}u(y)\geq\frac{1}{\ln\theta+1}{u}^{\prime}(y),y\in[\frac{1}{\ln\theta+1},1]\\ u(\frac{1}{\ln\theta+1})=L,u(1)=U.\end{array}\right.

(8)

The differential equation counterpart is as follows:

\left\{\begin{array}[]{l}v(y)=\frac{1}{\ln\theta+1}{v}^{\prime}(y),y\in[\frac{1}{\ln\theta+1},1]\\ v(\frac{1}{\ln\theta+1})=L,v(1)=U.\end{array}\right.

(9)

The unique solution to (9) is $v(y)=\frac{L}{e}e^{(\ln\theta+1)y}$ . Suppose $u$ is a feasible solution to (8), by Gronwall’s inequality, $u(y)\leq v(y),\forall y\in[\frac{1}{\ln\theta+1},1]$ . Next, we are going to show that the solution of (8) is unique and is exactly $v(y)$ .

Suppose $u(y)<v(y)$ for $y\in\mathbb{I}$ , where $\mathbb{I}\subset[\frac{1}{\ln\theta+1},1]$ . We know that for any $y\in[\frac{1}{\ln\theta+1},1]$ , $v^{\prime}(y)=(\ln\theta+1)v(y).$ Thus, for $y\in\mathbb{I}$ , we have

v^{\prime}(y)=(\ln\theta+1)v(y)>(\ln\theta+1)u(y)\geq u^{\prime}(y).

Take the integral of $u^{\prime}$ over $[\frac{1}{\ln\theta+1},1]$ , we have $\int_{\frac{1}{\ln\theta+1}}^{1}u^{\prime}(y)dy=u\big{|}_{\frac{1}{\ln\theta+1}}^{1}=U-L,$ which can also be expressed as

	$\displaystyle\int_{\frac{1}{\ln\theta+1}}^{1}u^{\prime}(y)dy$	$\displaystyle=\int_{\mathbb{I}}u^{\prime}(y)dy+\int_{[\frac{1}{\ln\theta+1},1]\backslash\mathbb{I}}u^{\prime}(y)dy$
		$\displaystyle<\int_{\mathbb{I}}v^{\prime}(y)dy+\int_{[\frac{1}{\ln\theta+1},1]\backslash\mathbb{I}}u^{\prime}(y)dy$
		$\displaystyle=\int_{\frac{1}{\ln\theta+1}}^{1}v^{\prime}(y)dy=v\big{\|}_{\frac{1}{\ln\theta+1}}^{1}=U-L,$

which shows $U-L<U-L$ . Thus, $u(y)=v(y)$ for $y\in[\frac{1}{\ln\theta+1},1]$ . In conclusion, the optimal $\phi^{*}$ achieving competitive ratio $(\ln\theta+1)$ is unique, and

\phi^{*}(y)=\left\{\begin{array}[]{cc}L&y\in[0,\frac{1}{\ln\theta+1}]\\ \frac{L}{e}e^{(\ln\theta+1)y}&y\in(\frac{1}{\ln\theta+1},1]\end{array}.\right.

∎

III-C Analysis of OKP

We highlight the differences in the analysis of the OKP. The primal feasibility holds trivially and the dual variables are constructed as follows:

\displaystyle\lambda=\lambda_{N},\quad\beta_{i}=\begin{cases}b_{i}-\lambda_{i}&x_{i}=w_{i}\\ 0&x_{i}=0\end{cases},

where $\lambda_{i}=\phi(y^{(i-1)})$ . When $x_{i}=w_{i}$ , based on the decision-making rule (Step 1 in the algorithm), we must have $b_{i}\geq\phi(y^{(i-1)})$ . Therefore, $\beta_{i}\geq 0,\forall i\in[N]$ . The constraint of the dual problem is

\displaystyle\lambda+\beta_{i}-b_{i}=\begin{cases}\lambda-\lambda_{i}\geq 0&x_{i}=w_{i}\\ \lambda-b_{i}\geq 0&x_{i}=0\end{cases}.

Thus, the dual feasibility holds.

Assume that the online algorithm will accept the first $k$ items, and $\omega=\sum_{i=1}^{k}w_{i}$ . Also note that $\lambda_{i}=L,\forall i\in[k]$ . Then we have

	$\displaystyle D_{k}$	$\displaystyle=\lambda_{k}+\sum_{i=1}^{k}w_{i}\beta_{i}=\lambda_{k}+\sum_{i=1}^{k}w_{i}(b_{i}-\lambda_{i})$
		$\displaystyle=L(1-\omega)+\sum_{i=1}^{k}w_{i}b_{i}$
		$\displaystyle\leq\frac{1}{\omega}(\sum_{i=1}^{k}w_{i}b_{i})\leq\alpha\sum_{i=1}^{k}w_{i}b_{i}=\alpha P_{k}.$

Thus, there exists $k$ that satisfies the initial inequality.

With regard to the incremental inequalities, we have $P_{i}-P_{i-1}=b_{i}w_{i},D_{i}-D_{i-1}=\varphi(y^{(i)})-\varphi(y^{(i-1)})+w_{i}(b_{i}-\varphi(y^{(i-1)})\overset{(a)}{=}w_{i}[\varphi^{\prime}(y^{(i-1)})+b_{i}-\varphi(y^{(i-1)})],$ where $(a)$ is due to the fact $\varphi^{\prime}(y^{(i-1)})=\frac{\varphi(y^{(i)})-\varphi(y^{(i-1)})}{w_{i}}$ and $w_{i}=y^{(i)}-y^{(i-1)}$ (using the infinitesimal weight assumption). Combining the ODE (4) with the fact that $b_{i}\geq\phi(y^{(i-1)})=\varphi(y^{(i-1)})$ , the incremental inequality holds for $i\in[N]$ . Thus, Theorem 2 holds for the OKP. Note that the proof of Theorem 3 holds generally for the two problems.

IV Lower Bounds

In this section, we show that the lower bound of the OTP and that of the OKP coincide. Denote Algorithm 1 with $\phi^{*}$ by $\text{ALG}_{\phi^{*}}$ . We first present the proofs for the OTP, then call attention to the differences for the OKP case.

IV-A Lower Bounds of OTP

Below we find the family of the worst-case sequences under which $\text{ALG}_{\phi^{*}}$ incurs a ratio of $\ln\theta+1$ .

Lemma 2.

Given $L$ and $U$ , the family of the worst-case sequences of $\text{ALG}_{\phi^{*}}$ in the OTP are denoted by $\{\hat{\delta}_{k}\}_{k\in\mathbb{N}^{+}}$ , where $\hat{\delta}_{k}=\{\hat{b}_{1},\dots,\hat{b}_{k}\}$ , $\hat{b}_{i}\in[L,U]$ and the rates satisfy

\hat{b}_{1}=L,\hat{b}_{i}=\hat{b}_{i-1}+\epsilon_{i-1},i>1,\lim_{k\rightarrow\infty}\hat{b}_{k}=U,

where $\epsilon_{i}$ s are infinitesimal positive values. The amount traded by $\text{ALG}_{\phi^{*}}$ at the exchange rate $\hat{b}_{i}$ is denoted by $\hat{x}_{i}$ , which satisfies

\hat{x}_{1}=\frac{1}{\ln\theta+1},\hat{x}_{i}=\frac{\ln\hat{b}_{i}/\hat{b}_{i-1}}{\ln\theta+1},i>1,\lim_{k\rightarrow\infty}\sum_{i=1}^{k}\hat{x}_{i}=1.

Proof.

The proof of Lemma 2 is in the Appendix. ∎

Proof of Theorem 4.

Let ALG be any online algorithm different from $\text{ALG}_{\phi^{*}}.$ We show that ALG cannot achieve a competitive ratio smaller than $\ln\theta+1$ by using an adversarial argument.

Let $\hat{\delta}=\{L,L+\epsilon_{1},\dots,U\}$ . First present $\hat{b}_{1}=L$ to ALG. If ALG exchanges $x^{\prime}_{1}<\hat{x}_{1}=1/(\ln\theta+1)$ , then we end the sequence, and on doing so, ALG cannot achieve $\ln\theta+1$ , because $\frac{\text{OPT}(\hat{\delta}_{1})}{\text{ALG}(\hat{\delta}_{1})}=\frac{1}{x^{\prime}_{1}}>\ln\theta+1.$ Thus, we can assume that ALG spends an amount $x^{\prime}_{1}\geq\hat{x}_{1}$ , in this case, we continue and present $\hat{b}_{2}$ to ALG. In general, if after processing the $k$ th exchange rate, the total amount of dollars spent is less than $\sum_{i=1}^{k}\hat{x}_{i}$ , we immediately end the sequence. Otherwise, we continue to present $\hat{b}_{k+1}$ , etc.

Let $f(k)=\sum_{i=1}^{k}(x^{\prime}_{i}-\hat{x}_{i})$ . Let $\mathbb{K}=\{k\in\mathbb{N}|f(k)<0\}$ , denote the minimum in $\mathbb{K}$ as $j$ , we have

	$\displaystyle x^{\prime}_{1}\geq\hat{x}_{1},$
	$\displaystyle x^{\prime}_{1}+x^{\prime}_{2}\geq\hat{x}_{1}+\hat{x}_{2},\dotsc$
	$\displaystyle\sum_{i=1}^{j-1}x^{\prime}_{i}\geq\sum_{i=1}^{j-1}\hat{x}_{i},$
	$\displaystyle\sum_{i=1}^{j}x^{\prime}_{i}<\sum_{i=1}^{j}\hat{x}_{i}.$

Thus, ALG can gain more by spending exactly the same as $\text{ALG}_{\phi^{*}}$ at the first $(j-1)$ exchange rates and by spending $\tilde{x^{\prime}_{j}}=x^{\prime}_{j}+\sum_{i=1}^{j-1}(x^{\prime}_{i}-\hat{x}_{i})$ at the $j$ th exchange rate. Since $\tilde{x^{\prime}_{j}}<\hat{x}_{j}$ , ALG cannot guarantee the competitive ratio of $\ln\theta+1$ . If $f(k)\geq 0$ for all $k\in\mathbb{N}^{+}$ , we have

\displaystyle\liminf_{k\rightarrow\infty}f(k)\geq 0,\limsup_{k\rightarrow\infty}f(k)\geq 0.

Since ALG cannot exceed the capacity limit, we have $\lim_{k\rightarrow\infty}\sum_{i=1}^{k}x^{\prime}_{i}\leq 1,$ and we also have $\lim_{k\rightarrow\infty}\sum_{i=1}^{k}\hat{x}_{k}=1$ , therefore, we have $\lim_{k\rightarrow\infty}f(k)\leq 0.$ For an infinite sequence $f(k)$ , the limit exists iff

\limsup f(k)=\liminf f(k)=\lim f(k),

so we have $\lim_{k\rightarrow\infty}f(k)=0.$ By the Abel transformation, we have $\sum_{i=1}^{k}\hat{b}_{i}(x^{\prime}_{i}-\hat{x}_{i})=\sum_{i=1}^{k-1}f(i)(\hat{b}_{i}-\hat{b}_{i+1})+f(k)\hat{b}_{k}\\ \overset{(a)}{\leq}f(k)\hat{b}_{k},$ where ( $a$ ) is due to the monotonicity of $\{\hat{b}_{i}\}$ .

Thus, the performance gap between ALG and $\text{ALG}_{\phi^{*}}$ for this infinite exchange rate sequence is $\lim_{k\rightarrow\infty}\sum_{i=1}^{k}\hat{b}_{i}(x^{\prime}_{i}-\hat{x}_{i})\leq\lim_{k\rightarrow\infty}f(k)\hat{b}_{k}=0.$

Therefore, any online algorithm for the OTP cannot achieve a better competitive ratio than $\text{ALG}_{\phi^{*}}$ . The lowest possible competitive ratio is $\ln\theta+1$ .

∎

IV-B Lower Bounds of OKP

We show that with a slight modification, $\{\hat{\delta}_{k}\}_{k\in\mathbb{N}^{+}}$ are also the worst-case sequences for the OKP.

Consider a family of the value-to-weight ratio sequences $\{I_{b}\}$ indexed by $b\in[L,U]$ . $I_{b}$ is composed of a continuum of subsequences, with the ratios in the $i$ th subsequence all being $\hat{b}_{i},i\in\mathbb{N}^{+}$ , where $\hat{b}_{i}\leq b$ , which is given in Lemma 2. The length of each subsequence is sufficiently large so that it can fulfill the capacity of the knapsack even if it is presented alone. Note that given $I_{b}$ , the resource allocation strategy is analogous to the OTP case. The offline optimal solution is to only select from the subsequence with $\hat{b}_{i}=b$ until reaching the capacity limit, whereas $\text{ALG}_{\phi^{*}}$ will select a value-to-weight ratio as long as it is no less than $\phi^{*}(y)$ , where $y$ is the current capacity utilization level. Therefore, $\{I_{b}\}_{b\in[L,U]}$ are the worst-case sequences for the OKP.

With regards to the proof of Theorem 4, one can replace the worst sequence $\hat{\delta}$ with $I_{U}$ , present a subsequence instead of an arrival at a time to ALG, and act adversarially in the same way in response to the decisions made by ALG, and the results still hold.

V CONCLUSION

We provide a unified threshold-based algorithm for two well-known online problems, namely, the one-way trading problem and the online knapsack problem. We show the sufficient conditions for the algorithm to have a bounded competitive ratio for both problems via a unified competitive analysis. We reveal the threshold function that can achieve the best (smallest) competitive ratio, show that it matches the lower bounds, and present new proofs for the lower bounds for both problems. This is the first work that introduces the connections between the OTP and the OKP and provides a unified algorithmic framework for both of them, and we believe there is much more to be explored in this direction, i.e., unifying the online algorithm design.

APPENDIX

Proof of Lemma 2.

Denote any strictly-increasing sequence with length $k$ by $\delta_{k}=\{b_{1},\dots,b_{k}\}$ . We can simply focus on the strictly-increasing sequences, because $\text{ALG}_{\phi^{*}}$ only trades something when the current exchange rate is the new high observed. Any normal sequences can be transformed into a strictly-increasing sequence by keeping the exchange rate higher than all of its predecessors and omitting the rest, and the optimal in hindsight is not affected by this transformation. By (5), we have

	$\displaystyle x_{1}$	$\displaystyle={\phi^{*}}^{-1}(b_{1})=\frac{\ln(b_{1}e/L)}{\ln\theta+1},$
	$\displaystyle x_{i}$	$\displaystyle={\phi^{}}^{-1}(b_{i})-{\phi^{}}^{-1}(b_{i-1})$
		$\displaystyle=\frac{\ln(b_{i}/b_{i-1})}{\ln\theta+1},i\geq 2.$

Denote the total amount of yen $\text{ALG}_{\phi^{*}}$ trades for $\delta_{k}$ by ALG( $\delta_{k}$ ) and the offline optimal amount by OPT( $\delta_{k}$ ). We have $\text{OPT}(\delta_{k})=b_{k},$ and

\displaystyle\text{ALG}(\delta_{k})=\sum_{i=1}^{k}b_{i}x_{i}=\frac{b_{1}\ln(b_{1}e/L)+\sum_{i=2}^{k}b_{i}\ln(b_{i}/b_{i-1})}{\ln\theta+1}.

Let $r_{k}(b_{1},\dots,b_{k})=\frac{b_{1}\ln(b_{1}e/L)+\sum_{i=2}^{k}b_{i}\ln(b_{i}/b_{i-1})}{b_{k}}$ . Thus, the competitive ratio for $\text{ALG}_{\phi^{*}}$ can be expressed as

\displaystyle\underset{\{b_{1},\dots,b_{k},k\}}{\max}\frac{\text{OPT}(\delta_{k})}{\text{ALG}(\delta_{k})}

\displaystyle=\frac{\ln\theta+1}{\underset{\{b_{1},\dots,b_{k},k\}}{\min}r_{k}(b_{1},\dots,b_{k})}.

Because $\text{ALG}_{\phi^{*}}$ can achieve $\ln\theta+1$ with $\phi^{*}$ by Theorem 3, we know that $\underset{\{b_{1},\dots,b_{k},k\}}{\min}r_{k}=1$ . Next, we look for $\{b_{1},\dots,b_{k}\}$ that minimize $r_{k}(b_{1},\dots,b_{k})$ for each $k$ . When $k=1$ , $r_{1}(b_{1})=\ln(b_{1}e/L)\geq 1$ , therefore, $\hat{\delta}_{1}=\{L\}$ , $\hat{x}_{1}=\frac{1}{\ln\theta+1}$ and $\frac{\text{OPT}(\hat{\delta}_{1})}{\text{ALG}(\hat{\delta}_{1})}=\ln\theta+1$ . When $k=2$ ,

\displaystyle r_{2}(b_{1},b_{2})=\frac{b_{1}\ln(b_{1}e/L)+b_{2}\ln(b_{2}/b_{1})}{b_{2}}.

The first order derivatives are

	$\displaystyle\frac{\partial r_{2}}{\partial b_{1}}$	$\displaystyle=\frac{\ln(b_{1}e/L)+1-b_{2}/b_{1}}{b_{2}},$
	$\displaystyle\frac{\partial r_{2}}{\partial b_{2}}$	$\displaystyle=\frac{b_{2}-b_{1}\ln(b_{1}e/L)}{{b_{2}}^{2}}.$

We notice that $\partial r_{2}/\partial b_{1}$ and $\partial r_{2}/\partial b_{2}$ cannot be zero simultaneously. This means that $r_{2}$ has no critical points, and the minimum value of $r_{2}$ on $[L,U]\times[L,U]$ must be on one of the four boundary points. It turns out that $r_{2}$ reaches minimum when $(b_{1},b_{2})=(L,L)$ . We need to find a close neighbor to $(L,L)$ with $b_{2}>b_{1}$ and whose value does not increase too much. Notice that $\partial r_{2}/\partial b_{1}\big{|}_{(L,L)}>0,\partial r_{2}/\partial b_{2}\big{|}_{(L,L)}=0$ , increasing $b_{2}$ to $b_{2}+\epsilon$ with infinitesimal positive $\epsilon$ should incur the least inaccuracy, thus, $\hat{\delta}_{2}=\{L,L+\epsilon\}$ and $\frac{\text{OPT}(\hat{\delta}_{2})}{\text{ALG}(\hat{\delta}_{2})}\rightarrow(\ln\theta+1)^{-}$ as $\epsilon\rightarrow 0^{+}$ . For general $k\geq 3$ ,

\displaystyle r_{k}(b_{1},\dots,b_{k})=\frac{b_{1}\ln(b_{1}e/L)+\sum_{i=2}^{k}b_{i}\ln(b_{i}/b_{i-1})}{b_{k}}.

The first order derivatives are:

\displaystyle\frac{\partial r_{k}}{\partial b_{1}}=\frac{\ln(b_{1}e/L)+1-b_{2}/b_{1}}{b_{2}},

\displaystyle\frac{\partial r_{k}}{\partial b_{k}}=\frac{b_{k}-b_{k-1}r_{k-1}(b_{1},\dots,b_{k-1})}{{b_{k}}^{2}},

\displaystyle\frac{\partial r_{k}}{\partial b_{i}}=\frac{\ln(b_{i}/b_{i-1})+1-b_{i+1}/b_{i}}{b_{k}},i=2,\dots,k-1.

A commonality is that, $\partial r_{k}/\partial b_{k}$ and $\partial r_{k}/\partial b_{k-1}$ cannot be zero at the same time, and $r_{k}$ reaches minimum when $b_{i}=L,i\in[k]$ . The increasing sequence closest to the minimum point is $\{L,L+\epsilon_{1},\dots,L+\sum_{i=1}^{k-1}\epsilon_{i}\}$ , where $\epsilon_{i}$ s are infinitesimal positive values, and we have $\frac{\text{OPT}(\hat{\delta}_{k})}{\text{ALG}(\hat{\delta}_{k})}\rightarrow(\ln\theta+1)^{-}$ as $\sum_{i=1}^{k-1}\epsilon_{i}\rightarrow 0^{+}.$ Actually, each $\hat{\delta}_{k}$ is the prefix of $\hat{\delta}_{m},m\geq k.$ From these observations, we claim that as long as the exchange rate sequence increases slowly enough from $L$ , it is the worst-case sequence for $\text{ALG}_{\phi^{*}}$ .

To verify the claim, let $\hat{b}_{k}$ be $L+\sum_{i=1}^{k-1}\epsilon_{i}$ , we have

	$\displaystyle\text{ALG}(\hat{\delta}_{k})$	$\displaystyle=\sum_{i=1}^{k}\hat{b}_{i}x_{i}$
		$\displaystyle=\frac{L}{\ln\theta+1}+\sum_{i=2}^{k}\hat{b}_{i}\bigg{(}\frac{\ln(\hat{b}_{i})-\ln(\hat{b}_{i-1})}{\ln\theta+1}\bigg{)}$
		$\displaystyle=\frac{L}{\ln\theta+1}+\int_{L}^{\hat{b}_{k}}\gamma\cdot\frac{d\ln(\gamma)}{\ln\theta+1}=\frac{\hat{b}_{k}}{\ln\theta+1},$

and thus

\frac{\text{OPT}(\hat{\delta}_{k})}{\text{ALG}(\hat{\delta}_{k})}=\underset{\{b_{1},\dots,b_{k},k\}}{\max}\frac{\text{OPT}(\delta_{k})}{\text{ALG}(\delta_{k})}=\ln\theta+1.

Since the exchange rate is upper bounded by $U$ , by the monotone convergence theorem, we have

\lim_{k\rightarrow\infty}\hat{b}_{k}=U,

and thus $\lim_{k\rightarrow\infty}\sum_{i=1}^{k}\hat{x}_{i}=1$ . ∎

References

[1] R. El-Yaniv, A. Fiat, R. M. Karp, and G. Turpin, “Optimal search and one-way trading online algorithms,” Algorithmica, vol. 30, no. 1, pp. 101–139, 2001.
[2] Q. Lin, H. Yi, J. Pang, M. Chen, A. Wierman, M. Honig, and Y. Xiao, “Competitive online optimization under inventory constraints,” Proceedings of the ACM on Measurement and Analysis of Computing Systems, vol. 3, no. 1, pp. 1–28, 2019.
[3] M. Babaioff, N. Immorlica, D. Kempe, and R. Kleinberg, “A knapsack secretary problem with applications,” in Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Springer, 2007, pp. 16–28.
[4] Y. Zhou, D. Chakrabarty, and R. Lukose, “Budget constrained bidding in keyword auctions and online knapsack problems,” in International Workshop on Internet and Network Economics. Springer, 2008, pp. 566–576.
[5] X. Tan, B. Sun, A. Leon-Garcia, Y. Wu, and D. H. Tsang, “Mechanism design for online resource allocation: A unified approach,” Proc. ACM Meas. Anal. Comput. Syst., vol. 4, no. 2, June 2020. [Online]. Available: https://doi.org/10.1145/3392142
[6] Z. Zhang, Z. Li, and C. Wu, “Optimal posted prices for online cloud resource allocation,” Proceedings of the ACM on Measurement and Analysis of Computing Systems, vol. 1, no. 1, pp. 1–26, 2017.
[7] F. Y. Chin, B. Fu, J. Guo, S. Han, J. Hu, M. Jiang, G. Lin, H.-F. Ting, L. Zhang, Y. Zhang, et al., “Competitive algorithms for unbounded one-way trading,” Theoretical Computer Science, vol. 607, pp. 35–48, 2015.
[8] P. Schroeder, R. Dochow, and G. Schmidt, “Optimal solutions for the online time series search and one-way trading problem with interrelated prices and a profit function,” Computers & Industrial Engineering, vol. 119, pp. 465–471, 2018.
[9] Y. Disser, M. Klimm, N. Megow, and S. Stiller, “Packing a knapsack of unknown capacity,” SIAM Journal on Discrete Mathematics, vol. 31, no. 3, pp. 1477–1497, 2017.
[10] X. Han, Y. Kawase, and K. Makino, “Randomized algorithms for removable online knapsack problems,” in Frontiers in Algorithmics and Algorithmic Aspects in Information and Management. Springer, 2013, pp. 60–71.
[11] L. Tran-Thanh, Y. Xia, T. Qin, and N. R. Jennings, “Efficient algorithms with performance guarantees for the stochastic multiple-choice knapsack problem,” in Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.
[12] H. Fujiwara, K. Iwama, and Y. Sekiguchi, “Average-case competitive analyses for one-way trading,” Journal of Combinatorial Optimization, vol. 21, no. 1, pp. 83–107, 2011.
[13] S. Albers, A. Khan, and L. Ladewig, “Improved online algorithms for knapsack and gap in the random order model,” in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
[14] D. S. Mitrinovic, J. Pecaric, and A. M. Fink, Inequalities involving functions and their integrals and derivatives. Springer Science & Business Media, 1991, vol. 53.