A Dynamic Near-Optimal Algorithm for Online Linear Programming

Author(s): Shipra Agrawal, Zizhuo Wang and Yinyu Ye

Source: Operations Research, July-August 2014, Vol. 62, No. 4 (July-August 2014), pp. 876-
890
Published by: INFORMS
Stable URL: [Link]
JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide
range of content in a trusted digital archive. We use information technology and tools to increase productivity and
.facilitate new forms of scholarship. For more information about JSTOR, please contact support@[Link]

Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at
[Link]

INFORMS is collaborating with JSTOR to digitize, preserve and extend access to Operations Research

This content downloaded from

[Link] on Fri, 17 Apr 2026 16:31:53 UTC
All use subject to [Link]
Operations Research jnfflut
Vol. 62, No. 4, July-August 2014, pp. 876-890
ISSN 0030-364X (print) | ISSN 1526-5463 (online) [Link]
©2014 INFORMS

A Dynamic Near-Optimal Algorithm for

Online Linear Programming
Shipra Agrawal
Microsoft Research India, Bangalore, India, shipra@[Link]

Zizhuo Wang
Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455, zwang@[Link]

Yinyu Ye
Department of Management Science and Engineering, Stanford University, Stanford, California 94305, yinyu-ye@[Link]

A natural optimization model that formulates many online resource allocation problems is the online linear programming (LP)
problem in which the constraint matrix is revealed column by column along with the corresponding objective coefficient.
In such a model, a decision variable has to be set each time a column is revealed without observing the future inputs, and the
goal is to maximize the overall objective function. In this paper, we propose a near-optimal algorithm for this general class
of online problems under the assumptions of random order of arrival and some mild conditions on the size of the LP
right-hand-side input. Specifically, our learning-based algorithm works by dynamically updating a threshold price vector at
geometric time intervals, where the dual prices learned from the revealed columns in the previous period are used to
determine the sequential decisions in the current period. Through dynamic learning, the competitiveness of our algorithm
improves over the past study of the same problem. We also present a worst case example showing that the performance of our
algorithm is near optimal.

Subject classifications: online algorithms; linear programming; primal-dual; dynamic price update.
Area of review. Optimization
History. Received August 2013; revision received December 2013; accepted April 2014. Published online in Articles in
Advance June 13, 2014.

1. Introduction (Sometimes, people consider the corresponding integer pro

.. - ... . .. ... . • , •« ., .. gram. Although our discussion focuses on the LP relaxation
Online optimization is attracting increasingly wide attention , ,, , „ ,
of these problems, our results naturally extend to integer
in the computer science, operations research, and manage

ment science communities. In many practical problems, data

programs. See §5.2 for the discussion on this.) An online
LP problem takes a linear program as its underlying form,
are not revealed at the beginning, but rather come in an
, ,. _ , . ,. and the constraint matrix is revealed column by column with
online fashion. For example, Y in online revenue management
b . cc . . . .■ f . ,v
. . the corresponding coefficient in the objective function. After
problems, consumers arrive sequentially, each requesting a an immediate decision must be made
obserying ^ ^
subset of goods (e.g., multileg flights or a period of stay in
without obserying ^ future data To be predse> we consider
a hotel) and offering a bid price. On observing a request,
{he following (offline) linear program;
the seller needs to make an irrevocable decision whether to n
accept or reject the bid, with the overall objective of maxi- maximize x
mizing the revenue while satisfying the resource constraints. j=i
Similarly, in online routing problems, the network capacity „
(1)
manager receives a sequence of requests from users with subject to ^avXj ^ /?,, i = I,..., m
intended usage of the network, each with a certain utility. i=>
His objective is to allocate the network capacity to maximize 0< x < 1, j = 1,..., n,
the social welfare. A similar format also appears in online , , ,
,. ,• , At u- Ki r v where for all j, it, ^ 0, a;1 = fa,,}™ , € [0, l]"1,1 and b =
auctions, online keyword matching problems, online packing ^ r „
,. , . . , [b,,\z,
1 e K . In the corresponding
r c online LP problem, at
problems, and various other online revenue management and „ . , , ,r ,
each time t, the coefficients (irt, a,) are revealed, and the
resource allocation problems. For an overview of the online
decision variable x, has to be chosen. Given the previous
optimization literature and its recent development, we refer , , . . , . x , ,,
t — 1 decisions x,,...,
1 decisions xu...,xt_{x._, and and inputs
, , „ . . ,.mn.
the readers to Borodin and El-Yamv (1998),
. ... .
Buchbinder and
.
.. , . . ...
inputs {77-,,
, ac Iuntil
{ttj, a, 1
x fimp t tho frh rlor>ieir\n rmnohlp v hoc rr> J f
/7
tinie t, the fth decision variable x, has to eoncn;
satisfy
Naor (2009a), and Devanur (2011).
In the examples mentioned above, the problem can be
i = 1,..., m and 0 ^ x, ^ 1. (2)
ctijXj < bj,
formulated as an online linear programming (LP) problem. i=1
876

This content downloaded from

[Link] on Fri, 17 Apr 2026 16:31:53 UTC
All use subject to [Link]
Agrawal, Wang, and Ye: A Dynamic Near-Optimal Algorithm for Online Linear Programming
Operations Research 62(4), pp. 876-890, ©2014 INFORMS 877

The goal in the online LP problem is to choose xjs such where the expectation is taken over uniformly random
that the objective function J2"=i 7T,X, is maximized. permutations cr of 1,..., n, and x, is the fth decision made
In this paper, we propose algorithms that achieve good by algorithm si when the inputs arrive in order a.
performance for solving the online LP problem. To define
In {his paper> we present a near_optimal algorithm for the
the performance of an algorithm, we first need to make
online Unear program (2) under the above two assumptions
some assumptions regarding the input parameters. We adopt and a lower bound condition on the size of b We also
the following random permutation model in this paper.
extend our results to the following more general online linear
Assumption 1. The columns a} (with the objective coef- optimization problems with multidimensional decisions at
eac'1 bme Pen°d:
ficient 7Tj) arrive in random order. The set of columns
»Consider a sequence of n nonnegative vectors
(a,, a2,...,a„) can be adversarily picked at the start. How-
ever, the arrival order of {a}, a2,..., fi, fz,.. •, f„ € IR , mn nonnegative vectors
a„) is uniformly dis-
tributed over all the permutations. e jq _
gj g g | m

Assumption 2. We know the total number of columns n

mdK = {xeMk: x7e< l,x>0} (we use e to denote the all
a priori. l vectors). The offline linear program is to choose Xj x„
random permutation model has been adopted in much
The
t0 so've

of the existing literature for online problems (see §1.3 for

a comprehensive review of the related literature). It is an
maximize
Efjx,
intermediate path between using a worst case analysis and
assuming the distribution of the input is known. The worst = 1
subject to Vg-x'' ' <b
^ i m
case analysis, which is completely robust to input uncertainty, ;=1
evaluates an algorithm based on its performance on the
€ K.
worst case input (see, e.g., Mehta et al. 2005, Buchbinder Xj

. and Naor 2009b). However, this leads to very pessimistic In the corresponding online problem, given the previous t— 1
performance bounds for this problem: no online algorithm decisions x,,..., x(_1; each time we choose a ^-dimensional
can achieve better than 0(1 /n)
approximation of the optimal decision xt £ Uk, satisfying
offline solution (Babaioff et al.2008). In contrast, although ,
a priori input distribution can simplify the problem to a E&v*; ^ i = l,... ,m and x, e K, (3)
great extent, the choice of distribution is very critical and i= t
the performance can suffer if the actual input distribution
using the knowledge up to time t. The objective is to
is not as assumed. Specifically, Assumption 1 is weaker maximize £;"=1 fJxj over the entire time horizon. Note that
than assuming that the columns are drawn independently Problem (2) is a special case of Problem (3) with k= 1.
from some (possibly unknown) distribution. Indeed, one
can view n i.i.d. columns as first drawing n samples from 1.1. Specific Applications
the underlying distribution and then randomly permuting
In the followi we show some specific applications of the
them. Therefore, our proposed algorithm and its performance
onbne Lp mode, The examples ^ on|y a few among the
would also apply if the input data are drawn i.i.d. from some
wide r£fflge of applications of this modeL
distribution.
1.1.1. Online Knapsack/Secretary Problem. The one
Assumption 2 is required since we need to use the quantity
n to decide the length of history for learning the threshold dimensional version of the online LP problem studied in
this PaPer is usually referred t0 as the online knapsack
prices in our algorithm. In fact, as shown in Devanur and
or secretary problem. In such problems, a decision maker
Hayes (2009), it is necessary for any algorithm to get a
faces a sequence of options, each with a certain cost and
near-optimal performance.2 However, this assumption can be
relaxed to an approximate knowledge of n (within at most value, and he has to choose a subset of them in an online
fashion 80 as t0 maximize the total value without violating
1 ± e multiplicative error), without affecting our results.
the cost constraint. Applications of this problem arise in
We define the competitiveness of online algorithms as
follows- many contexts, such as hiring workers, scheduling jobs, and
bidding in sponsored search auctions.
Definition 1. Let OPT denote the optimal objective value The random permutation model has been widely adopted
for the offline problem (1). An online algorithm si is c- in the study of this problem (see Kleinberg 2005, Babaioff
competitive in the random permutation model if the expected et al. 2007 and references thereafter). In those papers, either
value of the online solution obtained by using sä is at least c a constant competitive ratio is obtained for finite-sized
factor of the optimal offline solution. That is, problems or a near-optimal algorithm is proposed for large
problems. In this paper, we study an extension of this
> c OPT problem to higher dimension and propose a near-optimal
E„
L/=l algorithm for it.

This content downloaded from

[Link] on Fri, 17 Apr 2026 16:31:53 UTC
All use subject to [Link]
 Agrawal, Wang, and Ye: A Dynamic Near-Optimal Algorithm for Online Linear Programming
878 Operations Research 62(4), pp. 876-890, ©2014 INFORMS

1.1.2. Online Routing Problem. Consider a computer 1.2. Key Ideas and Main Results
network connected by m edges; each edge i has a bounded
The main contribution of this paper is t0 propose an algorithm
capacity (bandwidth) b. There are a large number of requests lhat solyes the online Lp problem with a [Link]
arriving online, each asking for certain capacities a, 6 Rm in
competitive ratio under the random permutation model. Our
the network, along with a utility or price for the request.
algorühm .g based on the observation that the optimal solution
The offline problem for the decision maker is given by the
x» for the offline Hnear program can be largdy determined
o owing integer program.
by [be optjmaj duaj solution p* e [Rm, corresponding to the
"
m inequality constraints. The optimal dual solution acts as
maximize Tf,xt
2^ a threshold so that x* > 0 only if Our
price Vj ^ p*ra;.
online algorithm works by learning a threshold price vector
from some initial inputs. The price vector is then used to
subject to Y^a
~ x^b i— 1 m
(=i determine the decisions for later periods. However, instead
of computing the price vector only once, our algorithm
x, e {0,1}.
initially waits until en steps or arrivals and then computes a
Discussions of this problem can be found in Buchbinder new price vector every time the history doubles, i.e., at time
and Naor (2009b), Awerbuch et al. (1993), and references en, 2en, 4en,... and so on. We show that our algorithm
therein. Note that this problem is also studied under the is 1 — 0(e) competitive in the random permutation model
name of online packing problem. under a size condition of the right-hand-side input. Our main

1.1.3. Online Adwords Problem. results are precisely stated as follows:

Selling online adver-
tisements has been the main revenue driver for many Internet Theorem 1. For any e > 0, our online algorithm is 1 -0(e)
companies such as Google, Yahoo, etc. Therefore, improving competitive for the online linear program (2) in the random
the performance of ad-allocation systems becomes extremely
permutation model, for all inputs such that
important for those companies and thus has attracted great
attention in the research community in the past decade. / m log (n/e) \
B = nunZ>,^n . (5)
In the literature, the majority of the research adopts an
online matching model, see e.g., Mehta et al. (2005), Goel
and Mehta (2008), Devanur and Hayes (2009), Karande An alternative way to state Theorem 1 is that our algorithm
et al. (2011), Bahmani and Kapralov (2010), Mahdian and has a competitive ratio of 1 - 0(Jmlogn/B). We prove
Yan (2011), Feldman et al. (2010, 2009b), and Feldman Theorem 1 in §3. Note that the condition in Theorem 1
et al. (2009a). In such models, there are n search queries depends on log«, which is far from satisfying everyone's
arriving online and m bidders (advertisers) each with a daily demand when n is large. Kleinberg (2005) proves that
budget bt. Based on the relevance of each search keyword, B ^ 1/e2 is necessary to get a 1 - O(e) competitive ratio in
the 2th bidder will bid a certain amount 7ry on query j to the ß-.secretary problem, which is the single dimensional

display his advertisement along with the search result.3 For counterpart of the online LP problem with a, — 1 for all t.
the y'th query, the decision maker (i.e., the search engine) Thus, the dependence on e in Theorem 1 is near optimal,
has to choose an w-dimensional vector x; = ,, where
In the next theorem, we show that a dependence on m is

Xjj € {0, 1} indicates whether the y'th query is allocated to necessary for any online algorithm to obtain a near-optimal
the 2th bidder. The corresponding offline problem can be solution. Its proof will appear in §4.
formulated as.
Theorem 2. For any algorithm for the online LP problem
maximize (2) in the random permutation model, there exists an instance
irj x; such that its ratio is less than 1 — when
;'=i competitive O(e)
n / \
i

subject to J277ijxu ^ bi> i = B = min b, < .

(4) i e1
y_l

xre ^ 1 Or equivalently, no algorithm can achieve a competitive

ratio better than 1 — Cl(yJ\ogm/B).
Xj
e {0, \}m.
We also extend our results to the more general model as
The LP relaxation of (4) is a special case of the general
introduced in (3)
online LP problem (3) with f'■= tt;, gtj — irye,- where e, is
the 2th unit vector of all zeros except 1 for the 2th entry. Theorem 3. For any e > 0, our algorithm is 1 — 0(e)
In the literature, the random permutation assumption competitive for the general online LP problem (3) in the
has attracted great interest recently for its tractability and random permutation model, for all inputs, such that:
generality. Constant competitive algorithms as well as near
m 'e>
optimal algorithms have been proposed. We will give a more ß= mjn b > fi( J (5)
'
comprehensive review in §1.3. Ve/

This content downloaded from

[Link] on Fri, 17 Apr 2026 16:31:53 UTC
All use subject to [Link]
Agrawal, Wang, and Ye: A Dynamic Near-Optimal Algorithm for Online Linear Programming
Operations Research 62(4), pp. 876-890, ©2014 INFORMS 879

Now we make some remarks on the conditions in The- Among this work, two types of results are obtained: one
orems 1 and 3. First, the conditions only depend on the achieves a constant competitive ratio independent of the
right-hand-side input h,'s and are independent of the size of input parameters; the other focuses on the performance of
OPT or the objective coefficients. And by the random per- the algorithm when the input size is large. Our paper falls
mutation model, they are also independent of the distribution into the second category. In the following literature review,
of the input data. In this sense, our results are quite robust in we focus on this category of work,
terms of the input data uncertainty. In particular, one advan- The first result that achieves a near-optimal performance
tage of our result is that the conditions are checkable before in the random permutation model is by Kleinberg (2005), in
the algorithm is implemented, which is unlike the conditions which a 1 - 0( \/^B) competitive algorithm is proposed for
in terms of OPT or the objective coefficients. Even just in the single-dimensional multiple-choice secretary problem,
terms of bt, as shown in Theorem 2, the dependence on e The author also proves that the 1 - 0(1/Vß) competitive
is already optimal and the dependence on m is necessary. rad0 achieved by his algorithm is the best possible for this
Regarding the dependence on n, we only need B to be of problem.
order log n, which is far less than the total number of bids n. Our result extends his work to a mutlidimensional case
Indeed, the condition might be strict for some small problems. with competitiveness 1 —
0(*Jm log n/B). Although the prob
However, if the budget is too small, it is not hard to imagine jem looks similar, because of the multidimensional structure,
that no online algorithm can do very well. On the contrary, in different algorithms are needed and different techniques
applications with large amounts of inputs (e.g., in the online are required for our analysis. Specifically, Kleinberg (2005)
adwords problem, it is estimated that a large search engine
recursively applies a randomized version of the classical sec
could receive several billions of searches per day, and even
retary algorithm, while we maintain a price based on the LP
if we focus on a specific category, the number can still be in
duality theory and have a fixed price updating schedule We
the millions) and reasonably large right-hand-side inputs
also prove that no online algorithm can achieve a competitive
(e.g., the budgets for the advertiser), the condition is not ratio bett£r than , _ for the multidimensional
hard to satisfy. Furthermore, the conditions in Theorems 1
problem To ^ best of our knowledge! this is the first result
and 3 are just theoretical results; the performance of our
^ shows ^ neœssity of dependence on tbe dimension m<
algorithm might still be very good even if the conditions are for ^ best competitive ratio achievable for this problem.
not satisfied (as shown in some numerical tests in Wang
R dearly points ()ut ^ higb dimensionality indeed adds t0
2012). Therefore, our results are of both theoretical and tbe djfbcuity 0f ^isproblem
practical interest. Devanur and Hayes (2009) study an LP-based approach
Finally,
J
we finish this section with the following corollary: ,
tor the
,. , , ,, , . . , .
J
online adwords problem. In their approach, they
Corollary 1. In the online LP problems (2) and (3), if solve a linear program once and utilize its dual solution
the largest entry of constraint coefficients does not equal 1, as a threshold price to make future decisions. The authors
prove a competitive ratio of 1 0(fj ir^m1 log n/OPT) for
then both our Theorems 1 and 3 still hold, with conditions —

(5) and (6) replaced by their algorithm. In our work, we consider a more general
model and develop an algorithm that updates the dual prices
m log (nk/e) ^ . at a carefully chosen pace. By using dynamic updates, we
^
( ratio that
"i \ achieve a competitive can depend only on B:

1 — 0(y/m\ogn/B). This is attractive in practice since B

where, for each row i, û, =
max^{|ai;|} in (2), or ä, = can be checked before the problem is solved while OPT
maxytllM»} in (3)' can not. Moreover, we show that the dependence on B of
our result is optimal. Although our algorithm shares similar
1.3. Related Work ideas to theirs, the dynamic nature of our algorithm requires
The design and analysis of online algorithms have been a a much more delicate design and analysis. We also answer
the important question of how often we should update the
topic of wide interest in the computer science, operations
research, and management science communities. Recently, the dual prices and show that significant improvements can be
random permutation model has attracted growing popularity, made using a dynamic learning algorithm,
since avoids the pessimistic lower bounds of the adversarial
it Recently, Feldman et al. (2010) studied a more general
input model while still capturing the uncertainty of the online packing problem that allows the dimension of the
inputs. Various online algorithms have been studied under choice set to vary at each time period (a further extension
this model, including the secretary problem (Kleinberg 2005, of (3)). They propose a one-time learning algorithm that
Babaioff et al. 2008), the online matching and adwords achieves a competitive ratio that depends both on the right
problem (Devanur and Hayes 2009, Feldman et al. 2009a, hand-side B and OPT. And the dependence on B is of the
Goel and Mehta 2008, Mahdian and Yan 2011, Karande et al. order —
1 0(f/m log n/B). Therefore, comparing to their
2011, Bahmani and Kapralov 2010) and the online packing competitive ratio, our result not only removes the dependence
problem (Feldman et al. 2010, Molinaro and Ravi 2014). on OPT, but also improves the dependence on B by an order.

This content downloaded from

[Link] on Fri, 17 Apr 2026 16:31:53 UTC
All use subject to [Link]
 Agrawal, Wang, and Ye: A Dynamic Near-Optimal Algorithm for Online Linear Programming
880 Operations Research 62(4), pp. 876-890, ©2014 INFORMS

Table 1. Comparison of existing results. a threshold—or "bid"—price is not new. It is initiated in

Williamson (1992) and Simpson (1989) and investigated
Competitiveness
further in Talluri and van Ryzin (1998). In Talluri and van
Kleinberg (2005) 1 — 0{\/sfB)
0(1/V5) (only = 1)
for m
Ryzin (1998), the authors show that the bid price control
Devanur and Hayes (2009) 1 -
0(y irmaxm2 log n/OPT)
0(/7rmaxm2 a/OPT) policy is asymptotically optimal. However, they assume the
Feldman et al. 1— O (max{ J/m log n/B, knowledge on the arrival process, so the price is obtained by
(2010) 0(max{J/m
"forecasting" the future using the distribution information
77maxmlogn/OPT}) rather than "learning" from the past observations, as we do

Molinaro and Ravi (2014) 1— 0(fm2 log m/B)

0(y/m2 in our paper. The idea of using LP to find the dual optimal

This paper 1 — 0(^/m\ogn/B) bid price is discussed in Cooper (2002), where asymptotic
optimality is also achieved. But again, the arrival process
is assumed to be known which makes the analysis quite
We show that the improvement is a result of the use of different.
dynamic learning. This paper contributes in several ways. First, we study a
More recently, Molinaro and Ravi (2014) studied the
general online LP framework, extending the scope of many
same problem and obtain a competitive ratio of 1 —
prior works. And because of its dynamic learning capability,
0(y/m2 log m/B). The main structure of their algorithm our algorithm is distribution free—no knowledge on the
(especially the way they obtain square root rather than cubic input distribution is assumed except for the random order of
root) is modified from that in this paper. They further use a arrival and the total number of entries. Moreover, instead of
novel covering technique to remove the dependence on n in
learning the price just once, we propose a dynamic learning
the competitive ratio, at the expense of increasing an order
algorithm that updates the prices as more information is
of m. In contrast, we present the improvement from the revealed. The of such an answers the
design algorithm
cubic root to square root and how to remove the dependence
question raised in Cooper (2002), which is how often and
on OPT. when should one update the price? We give an explicit
A comparison of the results of Kleinberg (2005), Devanur answer to this question by showing that updating the prices
and Hayes (2009), Feldman et al. (2010), Molinaro and Ravi at geometric time intervals—not too infrequently and not too
(2014), and this work is shown in Table 1. often—is optimal. Thus we present a precisely quantified
Besides the random permutation model, Devanur et al.
strategy for dynamic price update. Furthermore, we provide
(2011) study an online resource allocation problem under a nontrivial lower bound for this problem, which is the first
what they call the adversarial stochastic input model. This 0f jts kjnd and shows that the dimensionality of the problem
model generalizes the case when the columns are drawn adds t0 ds difficulty
from an i.i.d. distribution, however, it is more stringent jn our anaiysjS) we apply many standard techniques
than the random permutation model. In particular, their from probably approximately correct learning, in particular,
model does not allow the situations when there might be a
concentration bounds and covering arguments. Our dynamic
number of "shocks" in the input series. For this input model,
leaming shares a similar idea as the -doubling tnck- used
they develop an algorithm that achieves a competitive ratio in leaming problems. However, unlike the doubling trick,
of 1 - O(max{y/\ogm/B, Amax logm/OPT}). Their result
which is typically applied to an unknown time horizon
is significant in that it achieves near-optimal dependence
(Cesa-Bianchi and Lugosi 2006), we show that a geometric
on m. However, the dependence on OPT and the stronger
pace of price updating in a fixed length of horizon with a
assumption makes it not directly comparable to our results,
careful design could also enhance the perf0rmance of the
and their algorithm uses quite different techniques than ours.
algorithm
In the operations research and management science com

munities, a dynamic and optimal pricing strategy for various

1.4. Organization
online revenue management and resource allocation problems
has always been an important research topic; studies include The rest of the paper is organized as follows. In §§2 and 3,
Elmaghraby and Keskinocak (2003), Gallego and van Ryzin we present our online algorithm and prove that it achieves
(1997, 1994), Talluri and van Ryzin (1998), Cooper (2002) 1- O(e)competitive ratio under mild conditions on the input,
and Bitran and Caldentey (2003). In Gallego and van Ryzin To keep the discussion clear and easy to follow, we start in
(1997, 1994) and Bitran and Caldentey (2003), the arrival §2 with a simpler one-time learning algorithm. Although
processes are assumed to be price sensitive. However, as the analysis for this simpler algorithm will be useful to
commented in Cooper (2002), this model can be reduced to demonstrate our proof techniques, the results obtained in
a price independent arrival process with availability control this setting are weaker than those obtained by our dynamic
under Poisson arrivals. Our model can be further viewed as learning algorithm, which is discussed in §3. In §4, we give
a discrete version of the availability control model that is a detailed proof of Theorem 2, regarding the necessity of
also used as an underlying model in Talluri and van Ryzin lower bound conditions used in our main theorem. In §5, we
(1998) and discussed in Cooper (2002). The idea of using present several extensions of our study. We conclude in §6.

This content downloaded from

[Link] on Fri, 17 Apr 2026 16:31:53 UTC
All use subject to [Link]
Agrawal, Wang, and Ye: A Dynamic Near-Optimal Algorithm for Online Linear Programming
Operations Research 62(4), pp. 876-890, © 2014 INFORMS 881

2. One-Time Learning Algorithm 2.1. Competitive Ratio Analysis

In this section, we propose a one-time learning algorithm Observe that the OLA waits until time s = en and then
(OLA) for the online LP problem. We consider the following sets the solution at time t as x,(p), unless it violates the
partial linear program, defined only on the input until time constraints. To prove its competitive ratio, we follow these
s = en (for the ease of notation, without loss of generality, steps. First, we show that if p* is the optimal dual solution
we assume en is an integer throughout our analysis): to (1), then (x,(p*)} is close to the primal optimal solution x*;

s i.e., learning the dual price is sufficient to determine a close

maximize primal solution. However, since the columns are revealed
^ 7T(X(
t=i in an online fashion, we are not able to obtain p* during

$
the decision period. Instead, in our algorithm,
_ we use _p
C~J
^
subject to E anxt ^ (1 i = as a substitute. We then show that p is a good substitute
,=1
for p*: (1) with high probability, x,(p) satisfies all the
0 ^ x, < 1, t = 1,..., s, constraints of the linear program; (2) the expected value
of E, tt,jc; (p) is close to the optimal offline value. Before
and its dual problem.
we start Qur ana]ySjS; we make the following simplifying
m s technical assumption in our discussion:
s
- - +E
minimize E '(1 e) n y,
,=1 t=l Assumption 3. The problem inputs are in general position—
m Namely, for any price vector p—there can be at most m
/g\
subject to E aitpi + yt > tt, , t = 1,..., s columns such that pra( =
tt,.
<=1
Assumption 3 is not necessarily true for all inputs. How
p„y, ^0, i = l,...,m, t = l,...,s.
ever, as pointed out by Devanur and Hayes (2009), one can
Let (p, y) be the optimal solution to (8). Note that p has always randomly perturb tt, by arbitrarily small amount
the natural meaning of the price for each resource. For any B through adding a random variable taking uniform
distribution on interval [0,17]. In this way, with probability 1,
given price vector p, we define the allocation rule x,(p) as
follows- no P can satisfy m + 1 equations simultaneously among
pra, = 7r(, and the effect of this perturbation on the objective
0 if can be made arbitrarily small. Under this assumption, we
x,( p) = 7T( < p7 a,
1 if 7rf> pra(. can use the complementarity conditions of linear program
(1) to obtain the following lemma.
We now state our OLA:
Lemma 1. jcf (p*) < x* for all t, and under Assumption 3,
Algorithm OLA (One-time learning algorithm) x* an(i X;(p*) differs for no more than m values of t.
1. Initialize x, — 0, for all t ^ s. And p is defined as
above. Proof. Consider the offline linear program (1) and its dual
2. For t = s +1, s + 2,..., n, if ait:c,(p) < b, - Ylf=\ alJxj (let P denote the dual variables associated with the first set
for all i, set x, = x,(p); otherwise, set x, = 0. Output x,. of constraints and y, denote the dual variables associated
with the constraints x, ^ 1):
In the OLA, we learn a dual price vector using the first
en arrivals. Then, at each time t > en, we use this dual price m n
to decide the current allocation and execute this decision as minimize E b<Pi + E>'<
1=1 1=1
long as it doesn't violate any of the constraints. An attractive
feature of this algorithm is that it requires that we solve „ ,_i „ (Id)
subject to J2anPi + yt ^ '77<, t=
only one small linear program, defined on en variables. Note /=!
by a factor 1 e.
—
that the right-hand-side of (7) is modified
Pi,y,^ 0, i = l,...,m, f = l,...,n.
This modification guarantees that with high probability, the
allocation x.(p) does not violate the constraints. This trick _ , , , , r . .
, , . ^ , ., . By the complementarity slackness conditions, for any optimal
is also used in §3, where we study the dynamic learning , . r , . , ,, , , .
, ... T , .. r I, • solution x for the r
primal rproblem \( 1 /) and optimal
e solution
algonthm. In the next subsection, we prove the following / N
,. .... .. f.u y—»t , vr J ' for the dual,
(p*, y*) we must have:
proposition regarding the competitive ratio of the OLA,
which relies on a stronger condition than Theorem 1: , m ,
'
a"p> an^
Proposition 1. For any e > 0, the OLA is 1 - 6e competitive x< y'
~7r'J
for the online linear program (2) in the random permutation
~ ' = d for all t.
model, for all inputs such that 0 U)

l°ë(n/e) If x,(p*) = 1, by (9), tt, > (p*)rar Thus, by the constraint

B = min h' >
' e3 in (10), y* > 0 and finally, by the last complementarity

This content downloaded from

[Link] on Fri, 17 Apr 2026 16:31:53 UTC
All use subject to [Link]
 Agrawal, Wang, and Ye: A Dynamic Near-Optimal Algorithm for Online Linear Programming
882 Operations Research 62(4), pp. 876-890, ©2014 INFORMS

condition, x* = 1. Therefore, we have x,(p*) ^ x* for all t. Furthermore, we have

However, if irt < (p*)ra,, then we must have both x,(p*)
and x* = 0. Therefore, x,(p*) = x* if (p*)ra, + it,. Under
p(yz <^ (1 - e)eb'', V Z' =b )
Assumption 3, there are at most m values of t such that '/
(p*)ra, = Therefore, x* and x,(p*) differs for no more
77,.
than m values of t. □ < p £z,-e£z, >e2b,,yzt = b)
teS teN teN /
Lemma 1 shows that if an optimal dual solution p* to (1)
'

EZ, = b)/
is known, then x,(p*)'s obtained by our decision policy are
> e2b,
close to the optimal offline solution. However, in our online teS teN teN
algorithm, we use the sample dual price p learned from the 3
first few inputs, which could be different from the optimal
^ 2 exp ( — -
) ^ 8,
dual price p*. V 2 + e /
The remaining discussion attempts to show that the sample
dual price p will be sufficiently accurate for our purpose. where 5 = €^m ' The second-to-last step follows from
In the following, we frequently use the fact that the random tbe Hoeffding-Bernstein s Inequality for sampling without

order assumption can be interpreted as the first 5 inputs replacement (Lemma 10 in Appendix A) by treating Z,,
being uniform random samples without replacement of size s
? e S as the samples without replacement from Z,, teN.

from the n inputs. And we use S to denote the sample set of a'so use the fact that 0 < Z, ^ 1 for all t; therefore,
-
size s and N to denote the complete input set of size n. We £e/v (Z, Z)2 ^ EI€NZ2 < bt (and therefore the a2 in
start with Lemma 2, which shows that with high probability, Lemma 10 can be bounded by b,). Finally, the last inequality
the primal solution x,(p) constructed using the sample dual *s due to the assumption made on B.

price is feasible: Next, we take a union bound over all distinct p's. We call
two price vectors p and q distinct if and only if they result
Lemma 2. The primal solution constructed using the sample
in distinct solutions; ^ ^ { (q)} Note that we
dual price is a feasible solution to the linear program (1) , , . ., ,. {.. (p)}
. ., . „
., f. , , ,w . , , , , ; , only need to consider distinct prices, since otherwise all
with high -
ô rprobability. More rprecisely, with 'probability
7 1 e, ,., . . XT . ,
the Y, s are exactly the same. Note that each distinct p is
"
^ characterized by a unique separation of n points ({77,, a,}"=1)
£airxi(p) ^ bj, Vi= 1,..., m
in m+ 1-dimensional space by a hyperplane. By results from

computational geometry, the total number of such distinct

given B ^ 6mlog(n/e)/e3. prices is at most nm (Orlik and Terao 1992). Taking union
bound over the ^ distinct Prices' and i = 1,.... m, we get
Proof. Consider any fixed price p and i. We say a sample
the desired result. □
S is "bad" for this p and i if and only if p is the optimal
dual price to (8) for the sample set S, but £,=J aitxt(p) > bt. We showed that with high probability, x,(p) is a feasible
First, we show that the probability of bad samples is small solution. In the following, we show that it is also a near
for every fixed p and i. Then we take a union bound over
optimal solution
all distinct prices to prove that with high probability the
learned price p will be such that £"=1 aitx,{p) < £>,for all i. Lemma 3. The primal solution constructed using the sam
To start with, we fix p and i. Define Yt= aitx,(p). If p is pie dual price is a near-optimal solution to the linear
an optimal dual solution for the sample linear program on S, program (1) with high probability. More precisely, with
—
applying Lemma 1 to the sample problem, we have probability 1 e,

£ Y,= EaiMP) < < (1 - e)eb,,

£ (p) ^ (1 _ 3e)OPT
reS teS teS
teN

where x is the primal optimal solution to the sample linear

program on S. Now we consider the probability of bad given B~^6m log{n/e)/e .
samples for this p and i. Proof. The proof is based on two observations. First,

—
{x,(p)}"=i and p satisfy all the complementarity conditions,
£ Y, ^ (1 e)ebj, £ Yt ^ bj
j. and hence are the optimal primal and dual solution to the
(\teS teN /
following linear program:
We first define Z, = (biYl)/[Link] Zr It is easy to see that
maximize ir,xt
^
teN
p(yiYl^(l-e)ebi,yYl^b) /
\teS teN
i = l,...,
subject to y aitx, O,-, m (11)
teN
=
^p(£Z,<(l-e)ehi,£Z,
\teS teN
h,).
/ O^x, <1, t = !,...,«,

This content downloaded from

[Link] on Fri, 17 Apr 2026 16:31:53 UTC
All use subject to [Link]
Agrawal, Wang, and Ye: A Dynamic Near-Optimal Algorithm for Online Linear Programming
Operations Research 62(4), pp. 876-890, ©2014 INFORMS 883

where b,
=
Y,teN auxt(P) in the case pt > 0, and bt
= duality theorem:
max{Htew aitxt(P)> bi}, if Pi — 0. ^ ebrp* +
OPT(S) ''
y*.
Second, we show that if p, > 0, then with probability tçS
1 - e, bj > (1 — 3e)h(. To show this, let p be the optimal dual
Therefore '
solution of the sample linear program on set S and x be the
optimal primal solution. By the complementarity conditions
E[OP7,(5)] < ebrp* + E T~]y* =f(bV
'
+ E/I
of the linear program, if p, > 0, the ith constraint must be 'J V /
satisfied with equality. That is, = (1-e)efi,. Then,
— eOPT(N)
~~ □
by Lemma 1 and the condition that B — min, bt > m/e2, we
have Now, we are ready to prove Proposition 1:

Eai»*r(P) ^ Ea«*< 2e)ebl. Proof of Proposition 1. Using Lemmas 2 and 3, with

,eS ,eS —
probability at least 1 2e, the following events happen:
Then, using the Hoeffding-Bernstein's Inequality for sampling
without replacement, in a manner similar to the proof of
Vax " ' (p) ^< b" i= 1 m
Lemma 2, we can show that (the detailed proof is given in l=l
Appendix A.2), given the lower bound on B, with probability „
at least 1 - e, for all i such that p, >0: -
£ 77,x,(p) > (1 3e)OPT.
,=1
h = Jlaitxt(fi)^(l-3e)bi. (12)
'en That is, the decisions x,(p) are feasible and the objective
Combined with the case p, = 0, we know that with probability value taken over the entire period {1,..., n} is near optimal.
1 - e, b,> (1 - 3e)bi for all i. Last, observing that whenever Denote this event by % where P(t) > 1 - 2e. We have by
(12) holds, given an optimal solution x* to (1), (1 - 3e)x* Lemmas 2^1:
will be a feasible solution to (11). Therefore, the optimal r n
value of (11) is at least (1 - 3e)OPT, which is equivalent to E V tt,x, = E
saying that Lf=s+1 •f=l

E*r,*,(p)>(l-3e)OPT. □ >E E «■.*»(&)'(«) -E £w»*,(p)

t= 1 ■t=\ L(=l
Therefore, the objective value for the online solution > (1 — — eOPT > (1 —
3e)P(ré)OPT 6e)OPT
taken over the entire period is near optimal. However, in the
OLA, no decision is made during the learning period S, and where /( • ) is the indicator function, the first inequality is
only the decisions from periods {s + 1,..., n} contribute to because under %, x, = x,(p), and the second last inequal
the objective value. The following lemma, which relates ity uses the fact that x,(p) < x„ which is a result of
the optimal value of the sample linear program (7) to the Lemma 1. □
optimal value of the offline linear program (1), will bound
the contribution from the learning period: 3. Dynamic Learning Algorithm
Lemma 4. Let OPT(S) denote the optimal value of the The algorithm discussed in §2 uses the first en inputs to
linear program (7) over sample S and OPT(N) denote the learn a threshold price and then applies it in the remaining
optimal value of the offline linear program (1) over N. time horizon. Although this algorithm has its own merits—in
Then, particular, it requires solving only a small linear program
< e OPT(N). defined on en variables—the lower bound required on B is
E[OPT(S)]
thanthat claimed in Theorem an e
Proof. Let (x*, p\ r ) and (x, p, y) denote the optimal str°n\er ^ factor",
imP™ed leaming
primal and dual solutions of linear program (1) on N and ,In S^°n; Wue ProP°se^
, ,• r-i\ o ,• , algonthm
6 (DLA) ' that will achieve the result in Theorem 1.
the sample linear program (7) on S, respectively. } .
Instead of computing the pnce only once, the DLA will
T ,
_
(P ' ^ ) ~ m'n ^ T P + E Tr
update the price every time the history doubles, that is,
it learns a new price at time t = en, 2en, 4en, To be
s.t. p a( + y,^7r(, t eN precise, let p' denote the optimal dual solution for the
>0 following partial linear program defined on the inputs until
time I:
(P, y) = arg min (1-e)ebrp + Ey» <
tes maximize
E 7rixt
t=i
s.t. pTstt + yt^ir,, teS
1
-
I (13)
P.y>0. subject to Y^aitX, < (1 he)-bj, i—\,...,m
,=i »
Note that S ÇN, thus (p*, y*) is a feasible solution to the
dual of the linear program on S. Therefore, by the weak Q < x < 1, t = 1,..., I,

This content downloaded from

[Link] on Fri, 17 Apr 2026 16:31:53 UTC
All use subject to [Link]
 Agrawal, Wang, and Ye: A Dynamic Near-Optimal Algorithm for Online Linear Programming
884 Operations Research 62(4), pp. 876-890, ©2014 INFORMS

where the set of numbers he is defined as follows: bound over all distinct prices, all items i and periods I, the
lemma is proved. □
fn
= e In the following, we use LPs(d) to denote the partial linear
ht {—.
' ^
program that is defined on variables till time s with the
Also, for any given dual price vector p, we define the right-hand-side in the inequality constraints set as d. That is,
same allocation rule x,(p) as in (9). Our dynamic learning s
algorithm is stated as follows: maximize E77^

Algorithm DLA (Dynamic learning algorithm) s

1. Initialize t0 = en. Set x, = 0, for all t < t0. ^
subject to E anxt < dit
2. Repeat for t = t0 + 1, t0 + 2,... <=i

x, = x,(p£). Here I = l'en where r is the

(a) Set 0< x < 1, t = l,...,s.
largest integer such that I < t.
(b) If altx, ^ b, - [Link] for all /, then set x, = x,\ And let OPT,(d) denote the optimal objective value for
otherwise, set x, = 0. Output xr LPs(d).
Note that we update the dual price vector [log2 ( 1/e)~| Lemma 6. With probability at least 1 — e, for all I e L.
times during the entire time horizon. Thus, the DLA requires u tit \
more computation. However, as we show next, it requires a ^7r(x,(p l)>{l-2hl-e)OPTJ-b) n
weaker lower bound on B to prove the same competitive '=1 \ /

ratio. The intuition behind this improvement is as follows.

given B = min ' b > (10m log (n/e))/e2
Initially, at I — en, ht = *Je > e. Thus, we have larger u „

slacks at the beginning, and the large deviation argument for Proof. Let £>,= E/=i aijxj(P ) f°r ' suc^ that Pi > 0, and
=
constraint satisfaction (as in Lemma 2) requires a weaker b, max{E2i] ^ijxj(pe), ((2t)/n)bj}, otherwise. Then the
condition on B. As t increases, I increases and ht decreases. solution pair ({xt(pe)}*iv p£) satisfies all the complementar
However, for larger values of I, the sample size is larger, ityconditions; thus, they are optimal solutions (primal and
making a weaker condition on B sufficient to prove the same dual respectively) to the linear program LP2£(b):
error bound. Furthermore, hf decreases rapidly enough, such 2e
that the overall loss on the objective value is not significant. maximize ^ trtxt
As one will see, the careful choice of the numbers hf plays /=i

an important role in proving our results. 21

subject to E anxt ^ b, >

3.1. Competitive Ratio Analysis t=\

0<x, <1, t = \,...,2l.

The analysis for the DLA proceeds in a manner similar to that
for the OLA. However, stronger results for the price learned means
in each period need to be proved here. In the following, we
assume e = 2"£ and let L = {en, len,..., 2 E'len}. =
TTr,x,^l) OPTn{f) > ( min, , -\oPT2l(-b\.
Lemmas 5 and 6 are parallel to Lemmas 2 and 3 in §2 [=1 \ • bffl^/n) J \n J
but require a weaker condition on B: „
Now we analyze the ratio b^Hbi/n). By the definition
Lemma 5. For any e > 0, with probability 1 — e: 0f for ; SUch that = 0,
Otherwise, using
p{ bt f llbjn.

techniques similar to the proof of Lemma 5, we can prove

e {1 L that with probability 1 - e, for all i,
E a„xt(p£) sC -bn for all i m}, t €
n
(=r+l u 21
/ / , b.,= - -
aitxt(pl) ^ (1 2h, e)
— b.. (14)
given B — min, b( ^ (10m log (n/e))/e . n

Proof. The proof is similar to the proof of Lemma 2, but a a detailed proof of (14) appears in Appendix B.2. And the
more careful analysis is needed. We provide a brief outline lemma follows from (14). □
here with a detailed proof in Appendix B.l. First, we fix p, i
, . . ..™ .... cfor .«• Next, similar to Lemma 4, we prove the following lemma
and This time, we say a permutation is bad
I. this p, 1 ... ... , , ,
, „ -c j , -c »er ■ .. 1 j j b the optimal
relating ' value of the sampler linear 'program
0 to
and I if and only if p = p (i.e., p is the learned price under
,he opUn,al ,alue of lhe offllne l,near pro8ram:
the current turival order) but <WP') > (</«)»,• By
using the Hoeffding-Bernstein's Inequality for sampling Lemma 7. For any I,
without replacement, we show that the probability of "bad"
= e/(m -nm -E) for any fixed p, i
I
permutations is less than 8 E OPTi\ ^ —OPT.
n
and I under the condition on B. Then by taking a union

This content downloaded from

[Link] on Fri, 17 Apr 2026 16:31:53 UTC
All use subject to [Link]
Agrawal, Wang, and Ye: A Dynamic Near-Optimal Algorithm for Online Linear Programming
Operations Research 62(4), pp. 876-890, ©2014 INFORMS , 885

The proof of Lemma 7 is exactly the same as the proof 4. Worst C3S6 Bound for Any Algorithm
for Lemma thus, we omit its proof.
4;
In ^ we Theorem the condition
secll0n, prove 2; ie>
Now we are ready to prove Theorem 1.
ß ^ Q(q0g m/e1) is necessary for any online algorithm to
Proof of Theorem 1. Observe that the output of the online achieve a competitive ratio of 1 - 0(e). We prove this by
solution at time t e {I + 1,..., 21} is x,(pe) as long as constructing an instance of (1) with m items and B units
the constraints are not violated. By Lemmas 5 and 6, with of each item such that no online algorithm can achieve a
-
-
probability at least 1 2e: competitive ratio of 1 0(e) unless B > 0(logm/e2).
In this construction, we refer to the 0-1 vectors a,'s as
21 demand and
i vectors, 7r('s as profit coefficients. Assume

E aitxt(P ) ^ ~bj, for all i € {1,..., m}, feL m = 2Z for some integer z. We will construct z pairs of
_L
1 'l
=«+i
demand vectors such that the demand vectors in each pair
21
- -
(21 \ complement each other and do not share any item.
E 77,x,(pe) > (1 2ht e) OPTu for all I e L.
—bJ, However, every set of z vectors consisting of exactly one
vector from each pair will share at least one common item.
Denote this event by % where P(t) > 1 - 2e. The expected To achieve this, consider the 2Z possible Boolean strings
objective value achieved by the online algorithm can be of length z. The yth Boolean string represents yth item for
bounded as follows: j = \,... ,m = 2z (for illustrative purpose, we index the item
from 0 in our later discussion). Let denote the value at
21
fth bit of the y'th string. Then we construct a pair of demand
E E , e {0, l}m, -
UeL t=l+1
vectors v,-, w, by setting vtj = si;-, wtj = 1 stj.
Table 2 illustrates this construction for m = 8 (z = 3):
that the vectors v;, w;, i
= 1,... ,z are complemen
z e w&m)
Note

UeLt=i+1 tary to each other. Consider any set of z demand vectors

formed by picking exactly one of the two vectors v, and

r 2t r t

>EE E^,a,(p')/(^) -EE Etr,x,(pO/C§) w, for each i = 1,..., z. Then form a bit string by setting
IzL L/=l teL Lt=\ = 1 if this set has vector v, and 0 if it has vector w;. Then
all the vectors in this set share the item corresponding to the
^ E(1 —2ht —
e)E OPT2l -b )l(t) Boolean string. For example, in Table 2, the demand vectors
t^L (?■>
v3, w2, and w, share item 4(= "100"), the demand vectors
w3, v2,and V! share item 3(= "Oil"), and so on.
-EE OPT A- b /(«)
eeL Now, we construct an instance consisting of
• B/z inputs with profit coefficient 4 and demand vector

>P(«)-OPT-E2^E v,, for each i = 1,..., z.

ttL oprJ-bjics) • qt inputs with profit 3 and demand vector wi; for each i,

(21 ] — r x qt is a random variable following binomial(2/>/z,

where q, binomial(2B/z, 1/2).
OPT2A —
\
-eEE E[OPTen(eb)I('()] # ^jB/4z inputs with profit.2 and demand vector wh for
CeL bJI(fS)
each i.
• 2B/z — ql inputs with profit 1 and demand vector w„
>(l-2e)OPT-£2/^E OPT2i (
1<=L ^b for each i.

21. Using the properties of demand vectors ensured in the

-eEE OPT 2i I — b —
E[OPTe„(eb)] construction, we prove the following claim:
teL n

>(1
—
2e)OPT — 4 V —OPT — 2eV -OPT — eOPT
leL n
IeL
n Table
Table 2.
2. case bound.
Illustration of the worst case bound.

> (1 — 15e)OPT. Demand vectors Demand vectors

Items v3
U v2 *1 Items w3 w2 w,
The third inequality is from Lemma 6; the second-to-last
inequality is from Lemma 7; and the last inequality follows 0 0 0 0 0 1 1 1

from the fact that 1 0 0 1 1 1 1 0

2 0 1 0 2 1 0 1

3 0 1 1 3 1 0 0

E- = (i-e), and E^~ = eEt/^< 2.5e. 4 1 0 0 4 0 1 1

l,Ln UL
H
^Vn 5 I1 0 1 5 0 1 0
6 1 1 0 6 0 0 1

□ 7 7 0 0 0
Therefore, Theorem 1 is proved.
1 1 1

This content downloaded from

[Link] on Fri, 17 Apr 2026 16:31:53 UTC
All use subject to [Link]
 Agrawal, Wang, and Ye: A Dynamic Near-OptimaI Algorithm for Online Linear Programming
886 Operations Research 62(4), pp. 876-890, ©2014 INFORMS

Claim 1. Let r, denote the number of vectors of type w, with a constant probability. Thus, every decision for (2, w,)
-
accepted by any 1 e competitive solution for the constructed might result in a loss with constant probability, which results
example. Then, it must hold that in a total expected loss of (l(ffB/z) for every i, i.e., a total
loss of
5^ \ri
—
B/z\ < leB. If the number of w,s to be accepted is not exactly B/z,
' some of these ffB/z decisions may not be mistakes, but as
_ t , , ,, „ , in the claim above, such cases cannot be more than leB.
Proof. Let OPT denote the optimal
r value of the offline t,, f , , , „ , ..
. , , . Therefore, the expected value of online solution is
problem. And let OPT, denote the profit obtained from
demands accepted of type i. Let topw,(k) denote the sum of ONLINE < OPT - fl(VzB - leB).
profits of top k inputs with demand vector w, . Then
Since OPT ^ IB, to get (1 —
e) approximation factor, we
z z need
OPT = Y, OPT, > £(4ß/z + topwfB/z))
i= 1 ft(y/z/B -le) <7e => B ^ 0(z/e2) = 0(log(m)/e2).

= 4B + This completes the proof of Theorem 2. A detailed expo

Y] topw ' (B/z)
sition of the steps used in this proof appears in Appendix C.

Let OPT be the objective value of a solution that accepts r, 5. Extensions

vectors of type w;. First, note that E, n < B. This is because
5 -, 0nHne Multidimensional Linear Program
allW;S share one common item, and there are at most B
We consider the following more general onli"e linear Pro"
units of this item available. Let Y be the set {i: r; > B/z)
and X be the remaining Vs; i.e., X = [i : r, ^ B/z). Then, grams with multidimensional decisions x, 6 R at each step,
as dedned 'n W' >n §T
we show that the total number of accepted v,s cannot be
more than B - E,ey T + \Y\B/z. Obviously, the set Y cannot "
T
contribute more than \Y\B/z v,s. Let S ç X contribute the
maximize x<

remaining u,s. Now consider the item that is common to all

w,s in set Y and v,s in the set S (there is at least one such r
/=
subject t0 f ^ 1? ...,m (l5) '
item by construction). Since only B units of this item are (=1
available, the total number of v,s contributed by S cannot be
xfe<l, x,^0, r= 1,..
more than B — E,ey rt. Therefore, the number of accepted
v,s is less than or equal to B
—
E,ey r, + \Y\B/z. x, e IR*, t = 1,..., n.
Denote P = Eier L - |T|B/z, M = |X|B/z - Eiex 6- Then
Our online algorithm remains essentially the same (as
P, M ^ 0 and the objective value
described in §3), with xf(p) now defined as follows:

OPT < Etopw,(r,) + a(b - £rt + 0 if for all j, ftj f E PiSàj

\Y\B/z) i
i= 1 V ieY /

z X,(P) = er otherwise, where

< 52 topw,.(ß/z) + 3P - M + 4(B - P) re arg max -

Ê •
i—l ^ftJ Pign^j
— OFT — P — M
Here er is the unit vector with 1 at the rth entry and 0
__ otherwise. We break ties arbitrarily in our algorithm. Using
Since OPT < IB, this means that P + M must be less than
^ complementarity conditions of (15) and the lower bound
leB to get an approximation ratio of 1 - e or better. □
condition Qn ß as assumed in Theorem 3> we can prove
Here is a brief description of the remaining proof. By the following lemmas.4 The proofs are very similar to the

construction, for every i, there are exactly 2B/z demand proofs for the one-dimensional case and are provided in
vectors w, that have profit coefficients 1 and 3; among them, Appendix D.
each has equal probability to take value 1 or 3. From the Lemma 8 Let x* and p* be the optimal prima[ and duai
previous claim, to get a near-optimal solution, one must solutions to (15) respectively. Then x* and x,(p*) differs for
select close to B/z demand vectors of type w,. Therefore, at most m vaiues 0f t.
if the total number of (3,w,) inputs are more than B/z,
then selecting any (2, w,) will cause a loss of 1 in profit
Lemma 9" P and * to be distinct V ™d only if
Dfne
+ x<^ for some L Then there are at most
compared to the optimal profit; and if the total number of x/p)
— istinct price vectors.
(3, w,) inputs is less than B/z ffB/\z, then rejecting any
(2, w,) will cause a loss of 1 in profit. Using the central With the above lemmas, the proof of Theorem 3 will
limit theorem, at any step, both these events can happen follow exactly as the proof for Theorem 1.

This content downloaded from

[Link] on Fri, 17 Apr 2026 16:31:53 UTC
All use subject to [Link]
Agrawal, Wang, and Ye: A Dynamic Near-Optimal Algorithm for Online Linear Programming
Opérations Research 62(4), pp. 876-890, ©2014 INFORMS 887

5.2. Online Integer Programs Appendix A. Supporting Lemmas for §2

From the definition of x,(p) in (9), our algorithm always A.1 Hoeffding-Bernstein's Inequality for Sampling
Without Replacement
outputs integer solutions. And since the competitive ratio
analysis compares the online solution to the optimal solution By Theorem 2.14.19 in van der Vaart and Wellner (1996):
of the corresponding LP relaxation, the competitive ratio , , „ , , , , ., ,
, . _ , .. . Lemma 10. Let u,,u2,.. .,u. be random samples without replace
stated in Theorem 1 also holds for the online integer pro- men( fmm fhg red numbers ^ ^ > £r} mn for ^ f > Q
grams. The same observation holds for the general online
linear programs introduced in §5.1 since it also outputs / r \ / t2 \
?
integer solutions. T£"'~" 7 CTHt >aJ'
= ~ c = =
5.3. Fast Solution for Large Linear Programs by where
ma^ici min, g> (i/Ä)E, q. and a\
Column Sampling E=i (c> ~c^2

Apart from online problems, our algorithm can also be A.2 Proof of Inequality (12)
applied for solving (offline) linear programs that are too large
We prove that with probability 1 e, b( Eiev AAt(p) ^ (1
to consider all the variables explicitly. Similar to the one-time
,• ,, , 3e)o, given E,e5 a,jc,(p) Ml-2e)eo,. The proof is very similar
learning online solution, one could randomly sample en
{0 the proof of Lemma 2 F(x a price vector p and L Define a
vanables and use the dual solution p for this smaller program as "bad" -
permutation for p, i if both (1) £I€S ait>c,(p) ^ (1 2e)ebi
to set the values of variables Xj as x; (p). This approach and (2) £,6lV a„x,(p) < (1 - 3e)b, hold.
is very similar to the column generation method used for Define Y,
=
ai(x((p). Then the probability of bad permutations
solving large linear programs (Dantzig 1963). Our result is bounded by:

provides the first rigorous analysis of the approximation

achieved by the approach of reducing the linear program p( ^ - e ^ e2b
y, £ Y,
EL<(l-3e)b,)
size a subset of columns. V tes (sw teN
t€N /
by randomly selecting

^P\ Ez,-e£z. EZ, = (l-3e)b,)/

6. Conclusions teS teN teN

In this paper, we provide a 1 - 0(e) competitive algorithm for

^ 2 exp (- )
a general class of online LP problems under the assumption
assumption V 3 /

of random order of arrival and some mild conditions on the

where Z, = ((1 — 3e)b,y,)/£I£jv Y, in the first inequality and the
right-hand-side input. The conditions we use are independent second inequality is because of Lemma 10, and the last inequality
of the optimal objective value, the objective coefficients, and
foUows from that h_^ (6mlog(n/e))/e3 Summing over distinct
the distributions of input data. we get the desired inequality. □
prices and i = 1,..., m,
Our DLA works by dynamically updating a threshold
price vector at geometric time intervals, where the dual Appendix B. Supporting Lemmas for §3
prices learned from the revealed columns in the previous
period are used to determine the sequential decisions in the
B-f Proof of Lemma 5
current period. dynamic Our
learning approach might be Consider £( a,,x, for a fixed i. For ease of notation, we temporarily
useful in designing online algorithms for other problems. omit the subscript i. Define Y, = a,x,(p). If x and p are the optimal
There are many questions for future research. One impor- primal and dual solutions for (13) and its dual respectively, then
tant is whether the current bound on the size of we have:
question
the right-hand inputB is tight. As we show, there is a gap i i i
^
-
between our algorithm and the lower bound. Through some ]TF< = EaA<(P) ^.J^a,x, < (1 ht)b~.
numerical we find that the actual ,=1 ,=1 1=1
experiments, performance
of our algorithm
° is close to the lower bound (see Wang e TI cfirst . .. . , ril_ , . .. r ,
\
Here the inequality is because of the definition of x, (p) and
2012). However, we are not able to prove it. Filling that gap Lemma L Therefore, the probability of "bad" permutations for this
would be a very interesting direction for future research.
p ,•and i ;s bounded by:

Acknowledgments £
p(rY,^l-h()^,
1=1 ,=<+l Yt^\
The authors thank the two anonymous referees and the associate
editor for their insightful comments and suggestions. The research / 1 "
hi 2 bl\
of the third author is supported by the Major Program of National
'~l ,=1 J
Natural Science Foundation of China [Grant 71320107001] and Air
Force Office of Scientific Research (AFOSR) [Grant FA9550-12-1- f 4^v ' v bt if, 2bl\
0396], +\hïh ^~"'hY'**~)'

This content downloaded from

[Link] on Fri, 17 Apr 2026 16:31:53 UTC
All use subject to [Link]
 Agrawal, Wang, and Ye: A Dynamic Near-Optimal Algorithm for Online Linear Programming
Operations Research 62(4), pp. 876-890, ©2014 INFORMS

For the first term, we first define Z, = (2 blYt)/(n Y?,L\ Fj. It is where the last inequality follows from B = min, > m/e1 and

easy to see that I ^ ne. Therefore, the probability of "bad" permutations for p, i, I
is bounded by
/ bl 2bt\
\,=i n ,=i » / P(rv>n , Avv.n
Fl£y,>(l-Ä,-e)-&I.,2>,^(l-2A<-e)—M
™ ï2M
V(=i n i=l n /
/ € 2<
2M\ l 1 21 u 2i
n n )
V,=1 (=i ^F
z n
YY^X-lK-e)-^ n
t=1 f=l ,=x

Furthermore, using Lemma 10, we have i 1 2£ 21

21 \
Ez, = ( l-2A£-e)-M
btl
. , —
Ez^Ez,
t= 1
z
/=!
>ht
n ,=1 « /
/ bl 2 b£\
f(ez,<(i-a,)-,Ez, = —J
V«=1 n n / ,_1
<2expl--^J:
/ < 11
bl
^ Fl EZ, ^ (1 ~ = 2bl\
EZ, ~~T~ ) where Z, = ((1 — 2hl — e)2lbiYt)/{n Y^Li F,) and S = e/(m-nm-E).
\/~~l f 1 / b #,
The last inequality follows from the condition on B. Next, we take
£ i 21 ue
bl
21
2bl \ a union bound over all the nm distinct p's, i = 1,..., m, and E
,
— =
EZr-^EZ,
L (=1
>ht
n
EZ, yy J values of I; we conclude that with probability 1 - e
«/>( (=1

/ e2b \ 8 2£, , 21
< 2exp E^(P)>([Link]-e)-bl
{-ïïhj^r

where S = e/(m ■nm ■E). f°r all ' such that p, > 0 and all I. □
For the second term of (Bl), we can define the same Z„ and we
have Appendix C. Detailed Steps for Theorem 2
Let cx, ...,cn denote the n customers. For each i, the set R, ç
t 1 u
bl 2bl\ of customers with bid vector w, and bid value 1 or 3
^ y <^ {c,,..., c„}
'~
ES-jEr.L
/=1 t=l ^2 n n ) is fixed with |F,| — 2B/z for all i. Conditional on set Rl the bid

I 1 21
values of customers fc,,1 /
e F,} are independent random variables
u up 2.1
7he\
iLlZ = that take value 1 or 3 with equal probability.
^
Ez,-^Ez,
(=i ^
i=i 2 n
y^Z,
I=1 n J
)
Now consider the tth bid of (2, w,). In at least half of the
. £
t , It
2t 21 random permutations, the number of bids from set /?, before the
2bI \
Z, = bid t is less than B/z. Conditional on this event, with a constant
<p[ Ez,-^Ez, 2 2 n n )
)
probability, the bids in Rl before t take values such that the bids
V /=i (=1 (=1
\
g after t can make the number of (3, w,) bids more than B/z with a
^ constant probability and less than B/z- y/B/(4z) with a constant
_8
(f2g + 2h 1 ) 2'
probability. This probability calculation is similar to the one used
bF (2005^ in his Proof of the of condition
where the second-to-last step comes from Lemma 10 and the last Kldnbe2rf For necess,tyu
B > SI( 1/e ). completeness, we denve it in the Lemma 11
step holds because he < 1 and the condition made on B.
toward the end of the proof.
Last, we define two prices to be distinct the same way as in the
In the first type of instances (in which the number of (3, w,)
proof of Lemma 2. Then we take a union bound over all the nm
bids are more than B/z), retaining a (2, w,) bid is a "potential
distinct prices, i = I,..., m, and E values of I, and the lemma is
mistake" of size 1; similarly, in the second type of instances (in
which the number of (3, w,) bids are less than B/z), skipping a
(2, w,) bid is a potential mistake of size 1. This is because it will
B.2 Proof of Inequality (14) cost a profit loss of 1 if the online algorithm decides to pick B/z
—
. . ., c ç- of w,' bids. Among b these mistakes, \rt B/z\ of them may be
The proof is very similar to the proof ofc tLemma 5.
TU , ,,
Fix p, IOAand . ...... ( .,
. „ ... .,, . „ . . , recovered in each instance by •' deciding° to pick r, * B/z ol w, bids.
i e 11,..., ml; we define bad permutations for p, i, I as those ^ , .
r ,. . ,, , f ,, ... . ,, ,,, The total expected number of potential mistakes is SI(vFz)
permutations for which all the following conditions hold: ( 1 ) p = p , , . , rzrrrrz r .
, . . . , , , (since there are JB/(4z)
v ' of (2, w,)' bids for every i). By Claim 1,
that is, p is the price learned as the optimal dual solution for (13), , . .
—a, . , no more than a constant fraction of instances can recover more
< (1 - 2ht - e)((2l)/n)b. We
,
(2) P > 0, and 3) ^ ^ rf ^
will show that the ^ y,(p) of bad is small.
probability permutations Let 0NLINE denote the expected value for the online algorithm
Define If p is an optima dua so ution or (13),
— aitxt{p).
Yt over random permutation and random instances of the problem,
and p; > 0, then by the Karush-Kuhn-Tucher conditions the ith
Therefore
inequality constraint holds with equality. Therefore, by Lemma 1,
we have: ONLINE < OPT - Sl{\fzB - 7e5).

JL S,
u\Eu . , I, Now, observe that OPT ^ 7S. This is because by construction every
E
—
Laitxt(P) ^ \ 1 m ^^ n 1 ''
t
n n set of demand vectors (consisting of either v, or w, for each i)

This content downloaded from

[Link] on Fri, 17 Apr 2026 16:31:53 UTC
All use subject to [Link]
Agrawal, Wang, and Ye: A Dynamic Near-Optimal Algorithm for Online Linear Programming
Operations Research 62(4), pp. 876-890, ©2014 INFORMS 889

will have at least one item in common, and since there are only B Endnotes
units of this item available, at most 2B demand vectors can be 1. The assumption that
ai; ^ 1 is not restrictive, as we can
accepted, giving a profit of at most IB. Therefore, ONLINE ^ normalize the constraint to meet this requirement.
- - and to get (1 - e) approximation factor
OPT(l ilis/z/B le)), 2. An example to show the knowledge of n is necessary to obtain
we need a near-optimal algorithm is as follows. Suppose there is only one

product and the inventory is n. All a,-'s are 1. There might be n or

Q,(y/z/B
—
7e) ^ 0(e) =)► B^kl(z/e2). 2n arrivals. And in either case, half of them have value 1 and half
of them have value 2. Now consider any algorithm. If it accepts
This completes the proof of Theorem 2. less than 2/3 among the first n arrivals, the loss is at least n/3 (or
1 /6 of the optimal value) if in fact there are n arrivals in total. In
Lemma 11. Consider 2k random variables Yj, j = \,... ,2k that
contrast, if it accepts more than 2/3 among the first n arrivals, then
take value 0/1 independently with equal probability. Let r ^ k.
it must have accepted more than n/6 bids with value 1. And if the
Then with constant probability Yx,...,Yr take value such that
true number of arrivals is 2n, then it will also have a loss of at
Yj
can be greater or less than its expected value k by \fk/2 least 1/12 of the true optimal value. Thus if one doesn't know the
with equal constant probability. exact n, there always exists a case where the loss is a constant
fraction of the true optimal value.
2k
3. Here we assume the search engines use a pay-per-impression
ZYj ^ \Vk/2] Yu...,Yr )>c
j=i ■4 scheme. The model can be easily adapted to a pay-per-click scheme
by multiplying the bid value by the click-through rate parameters.
We also assume there is only one advertisement slot for each search
for some constant 0 < c < 1.
result.
Proof of Lemma 11. 4. Here we make an assumption similar to Assumption 3. That is,
• Given -
r ^ k, | Yj r/2| ^ Vk/4 with constant probability for any p, there can be at most m arrivals such that there are ties in
(by central limit theorem). ~
ftj HiPiSitj- As argued in the discussion following Assumption 3,
• Given r ^ k, | —
(2k
—
r)/2)| > 3V&/4 with constant this assumption is without loss of generality.
£J>r Yj
probability.
Given the above events | JN Yj — and by symmetry
k\ > Vfc/2,
both events have equal probability. □
References
Awerbuch B, Azar Y, Plotkin S (1993) Throughput-competitive on-line
Appendix D. Online Multidimensional Linear routing. FOCS'93: Proc. 34th Annual IEEE Sympos. Foundations
Program Comput. Sei. (IEEE Computer Society, Washington, DC), 32-40.
Babaioff M, Immorlica N, Kempe D, Kleinberg R (2007) A knapsack
D.1 Proof of Lemma 8 secretary problem with applications. Approximation, Randomization,
and Combinatorial Optimization. Algorithms and Techniques, Lecture
Using Lagrangian duality, observe that, given optimal dual solution Notes in Computer Science, Vol. 4627 (Springer-Verlag, Berlin,
p*, optimal solution x* is given by: Heidelberg), 16-28.
Babaioff M, Immorlica N, Kempe D, Kleinberg R (2008) Online auctions
maximize f[ x,-J2 P* 8lxt and generalized secretary problems. SIGecom Exch. 7(2): 1-11.
Bahmani B, Kapralov M (2010) Improved bounds for online stochastic
(D1) matching. ESA'10: Proc. 18th Annual Eur. Conf. Algorithms: Part I
subject to eTx < 1, x( ^ 0. (Springer-Verlag, Berlin, Heidelberg), 170-181.
Bitran G, Caldentey R (2003) An overview of pricing models for revenue
Therefore, it must be true that if x*r
= 1, then r e arg max , \ftj — management. Manufacturing Service Oper. Management 5(3):203—229.
— 0. This means that for t's such Borodin A, El-Yaniv R (1998) Online Computation and Competitive
(P*)rSr;}
and f,r (p*)7g/r ^
— Analysis (Cambridge University Press, New York).
that
m'dXjlfj (p*)7g,j}
is strictly positive and argmax; returns a
Buchbinder N, Naor J (2009a) The design of competitive online algorihms
unique solution, x,(p*) and x* are identical. By random perturbation via a primal-dual approch. Foundations and Trends Theoret. Comput.
argument there can be at most m values of t that does not satisfy Sei. 3(2-3):93-263.
this condition (for each such t, p satisfies an equation - = Buchbinder N, Naor J (2009b) Online primal-dual algorithms for covering
ftJ p'gy
- for some j, I, or - = 0 for some j). This means and packing. Math. Oper. Res. 34(2):270-286.
fn p'g,; ftj p'g(J
Cesa-Bianchi N, Lugosi G (2006) Prediction, Learning, and Games
x* and x,(p*) differ for at most m values of t. □
(Cambridge University Press, New York).
Cooper WL (2002) Asymptotic behavior of an allocation policy for revenue
D.2 Proof of Lemma 9 management. Oper. Res. 50(4):720-727.
Dantzig G (1963) Linear Programming and Extensions (Princeton University
Consider nk2 expressions
Press, Princeton, NJ).
Devanur N (2011) Online algorithms with stochastic input. SIGecom Exch.
~ ~ ~ 1 k, j # I, 1 ^ t < n
ftj PTg,j (f,i PT8ti)> h I< 10(2):40-49.
Devanur N, Hayes T (2009) The adwords problem: Online keyword
ftj-PT8tj' Uj^,U«n, matching with budgeted bidders under random permutations. EC'09:
Proc. 10th ACM Conf. Electronic Commerce (ACM, New York),
71-78.
we note that x;(p) is completely determined once we determine the
Devanur N, Jain K, Sivan B, Wilkens C (2011) Near optimal online
subset of expressions out of these nk2 expressions that are assigned
algorithms and fast approximation algorithms for resource allocation
a nonnegative value. By theory of computational geometry, there problems. EC'll: Proc. 12th ACM Conf. Electronic Commerce (ACM,
can be at most (nk2)m such distinct assignments. □ New York) 29-38.

This content downloaded from

[Link] on Fri, 17 Apr 2026 16:31:53 UTC
All use subject to [Link]
 Agrawal, Wang, and Ye: A Dynamic Near-Optimal Algorithm for Online Linear Programming
890 Operations Research 62(4), pp. 876-890, ©2014 INFORMS

Elmaghraby W, Keskinocak P (2003) Dynamic pricing in the presence of Orlik P, Terao H (1992) Arrangement of Hyperplanes. Grandlehren der Math

inventory considerations: Research overview, current practices and ematischen Wissenschaften [Fundamental Principles of Mathematical
future directions. Management Sei. 49( 10): 1287—1389.
Sciences] (Springer-Verlag, Berlin).
Feldman J. Mehta A, Mirrokni V, Muthukrishnan S (2009a) Online stochastic
Simpson RW (1989) Using network flow techniques to find shadow prices
-
matching: Beating 1 \/e. FOCS'09: Proc. 50th Annual IEEE Sympos. for market and seat inventory control. MIT Flight Transportation
Foundations Comput. Sei. (IEEE Computer Society, Washington, DC),
Laboratory Memorandum M89-1, Cambridge, MA.
117-126. Talluri K, van Ryzin G (1998) An analysis of bid-price controls for network
Feldman J, Henzinger M, Korula N, Mirrokni V, Stein C (2010) Online
revenue management. Management Sei. 44(11):1577—1593.
stochastic packing applied to display ad allocation. Algorithms-ESA
van der Vaart A, Wellner J (1996) Weak Convergence and Empirical
2010 (Springer-Verlag, Berlin, Heidelberg), 182-194.
Processes: With Applications to Statistics. Springer Series in Statistics
Feldman J, Korula N, Mirrokni V, Muthukrishnan S, Pal M (2009b) Online
ad assignment with free disposal. WINE'09: Proc. 5th Workshop on (Springer, New York).
Internet and Network Econom. (Springer-Verlag, Berlin, Heidelberg), Wang Z (2012) Dynamic learning mechanism in revenue management
374-385. problems. Unpublished doctoral thesis, Stanford University, Palo
Gallego G, van Ryzin G (1994) Optimal dynamic pricing of inventories Alto, CA.
with stochastic demand over finite horizons. Management Sei. 40(8): Williamson EL (1992) Airline network seat control. Unpublished doctoral
999-1020. thesis, MIT, Cambridge, MA.
Gallego G, van Ryzin G (1997) A multiproduct dynamic pricing problem and
its application to network yield management. Oper. Res. 45(1):24-41.
Goel G, Mehta A (2008) Online, budgeted matching in random input models Shipra Agrawalis a researcher at Microsoft Research India
with applications to adwords. SODA'08: Proc. 19th Annual ACM-S1AM in Bangalore. Her research interests lie in the intersection of
Sympos. Discrete Algorithms (SIAM, Philadelphia), 982-991. theoretical computer science and machine learning. Some other
Karande C, Mehta A, Tripathi P (2011) Online bipartite matching with
topics of interest include stochastic optimization, online learning,
unknown distributions. STOC'll: Proc. 43rd Annual ACM Sympos.
approximation algorithms, prediction markets, and computational
Theory Comput. (ACM, New York), 587-596.
Kleinberg R (2005) A multiple-choice secretary algorithm with applications game theory.
to online auctions. SODA'05: Proc. 16th Annual ACM-SIAM Sympos. Zizhuo Wang is an assistant professor in the Department of
Discrete Algorithms (SIAM, Philadelphia), 630-631. Industrial and Systems Engineering at University of Minnesota. His
Mahdian M, Yan Q (2011) Online bipartite matching with random arrivals:
research focuses on optimization and stochastic modeling, with
An approach based on strongly factor-revealing LPs. STOC'll: Proc.
43rd Annual ACM Sympos. Theory Comput. (ACM, New York), applications in dynamic pricing, revenue management, and service
597-606. management.
Mehta A, Saberi A, Vazirani U, Vazirani V (2005) Adwords and general Yinyu Ye is K. T. Li Professor of Engineering in the Department
ized on-line matching. FOCS'05: Proc. 46th Annual IEEE Sympos. of Management Science and Engineering at Stanford University. His
Foundations Comput. Sei. (IEEE Computer Society, Washington, DC),
research interests include mathematical programming, optimization
264-273.
Molinaro M, Ravi R (2014) Geometry of online packing linear programs. algorithm design and analysis, computational complexity, and
Math. Oper. Res. 39(l):46-59. operations research and its applications.

This content downloaded from

[Link] on Fri, 17 Apr 2026 16:31:53 UTC
All use subject to [Link]