How the Experts Algorithm Can Help Solve LPs Online∗
Anupam Gupta†

Marco Molinaro‡

arXiv:1407.5298v2 [] 26 Nov 2015

November 30, 2015

Abstract
We consider the problem of solving packing/covering LPs online, when the columns of the
constraint matrix are presented in random order. This problem has received much attention and
the main focus is to figure out how large the right-hand sides of the LPs have to be (compared to
the entries on the left-hand side of the constraints) to allow (1 + ε)-approximations online. It is
known that the right-hand sides have to be Ω(ε−2 log m) times the left-hand sides, where m is the
number of constraints.
In this paper we give a primal-dual algorithm that achieve this bound for mixed packing/covering
LPs. Our algorithms construct dual solutions using a regret-minimizing online learning algorithm
in a black-box fashion, and use them to construct primal solutions. The adversarial guarantee
that holds for the constructed duals helps us to take care of most of the correlations that arise in
the algorithm; the remaining correlations are handled via martingale concentration and maximal
inequalities. These ideas lead to conceptually simple and modular algorithms, which we hope will
be useful in other contexts.

1

Introduction

Sequential decision-making is one of the most important topics in Operations Research. While several
sequential decision models are available, the common feature is that items/requests come over time
and at a given time only partial information about the future items/requests is known. Decisions need
to be made over time only with the information available at that point. Moreover, typically decisions
are irrevocable.
While such problems have been extensively studied in the worst-case competitive analysis [BN09,
ABFP13], in order to avoid the pessimistic achievable guarantees a lot of recent research has focused
on the random-order model, which can be broadly described as follows: while the underlying instance is
arbitrary (i.e. chosen adversarially), the items/requests come in a random order (i.e. the adversary
cannot control the order in which the instance is presented). Several sequential decision problems
have been considered in this model, starting from a classic maximization version of the secretary
problem [Dyn63], to single-knapsack problems [Kle05, BIKK07], the AdWords problem [MSVV07,
GM08, DH09], matroid secretary problems [BIK07, BIKK08], and packing LPs [FHK+ 10, AWY14,
MR12, KRTV13, AD15, ESF14].
In this paper we consider a broad class of such problems, namely that of solving online packing/covering multiple-choice LPs; this class includes most of the examples above.
∗

A preliminary version of this work appeared in ESA 2014.
Computer Science Department, Carnegie Mellon University, Pittsburgh, PA. Research partly supported by NSF
awards CCF-1016799 and CCF-1319811, and by a grant from the CMU-Microsoft Center for Computational Thinking.
‡
EWI, TU Delft.
†

1

1.1

Model and prior results

The offline version of the packing/covering multiple-choice LPs we consider have the form
Pn
max
π t xt
Pnt=1 t t
st
Ax ≤b
Pnt=1 t t
t=1 C x ≥ d
xt ∈ N k

(PCMC)

∀t ∈ [n]

where
all the data π t , At , C t , b, d is non-negative and Nk denotes the “full simplex” {x P
∈ [0, 1]k :
P
t
t
t
t
j xj ≤ 1
j xj ≤ 1}. Note that the variables {x1 , x2 , . . . , xk } in each block t are bound together by
— this is the “multiple-choice” setting, which is useful in many contexts. In the case k = 1, the
multiple-choice model degenerates to the standard online packing-covering LP model where a single
variable xt is revealed at each time, and must be assigned a fractional value in [0, 1].
In the random-order model, the number n of columns and the right-hand sides b and d are known a
priori but the columns of the LP are revealed one by one in random order, that is, their arrival order
is chosen uniformly at random out of all possible permutations. When a column-block (π t , At , C t ) is
revealed, the corresponding xt variables need to be irrevocably set before the next column-blocks are
revealed. The goal is to obtain a feasible solution for the LP that tries to obtain as much value (in
expectation or with high probability) as the optimal offline solution. This is exactly the model we
consider here.
Packing/covering multiple-choice LPs form a broad classP
of problems. Special cases of this model with
packing-only constraints (i.e. without the constraints nt=1 C t xt ≥ d) have been extensively studied
[Dyn63, Kle05, BIKK07, MSVV07, GM08, DH09, FHK+ 10, AWY14, MR12, KRTV13, AD15, ESF14].
These models have a vast range of applications, like online advertisement, online routing, and airline
revenue management.
Most of these results show that one can obtain online an (1−ε)-approximation for the LP as long as the
right-hand side of the constraints are sufficiently (depending on ε) larger than any entry in the left-hand
side matrix. This direction started with the work of Kleinberg [Kle05], P
who considered the case without
multiple choices (i.e. k = 1) and with a single cardinality constraint t xt ≤ b. He showed a (1 − ε)approximation in expectation as long as maxbt at ≥ Ω(ǫ−2 ), which is best possible. Subsequently, Devanur and Hayes considered the AdWords problem [DH09], which was then extended to general packing
multiple-choice LPs [FHK+ 10, AWY14, MR12]. These results provide an (1−ε)-approximation as long
mini bi
≥ Ω(ε−2 ) min{m2 log(m/ε), m log(n/ε)},
as the right-hand sides/item sizes ratio satisfies max
At
t,i,j

ij

where m is the number of packing constraints and n the number of column-blocks. Agrawal et
al. [AWY14] also showed that Ω(ε−2 log m) ratio is required for (1 − ε)-approximations, which was
believed to be the right answer.
However, despite the increasing interest of solving LPs online, to the best of our knowledge no guarantee is known for online optimization of LPs with covering constraints, even in the weaker i.i.d.
model (see [MR12] for discussion of random order vs. i.i.d.)1

1.2

Our results

Packing/covering multiple-choice LPs. Our main contribution is the first set of algorithms
with provable guarantees for packing/covering multiple-choice LPs in the random-order model. Our
algorithm handles general packing/covering multi-choice LPs and achieves the optimal guarantee even
1

[DJSW11] presents an online for the feasibility version of packing-covering multi-choice LPs in the i.i.d. model.

2

when only packing constraints are present. For example, in case an estimate of the optimal value is
present we have the following guarantees.
Informal Theorem 1.1 (Packing/covering LPs). Consider a feasible packing/covering multiplechoice LP in the random-order model. Given ε, δ, assume that each right-hand side in the LP is at
least Ω( log(m/δ)
) times the maximum coefficient of the left-hand side in its row, and that the optimal
ε2

value is at least Ω( log(m/δ)
) times each individual item’s profit. Then given an (under)estimate O ∗ for
ε2
the optimal value of the offline LP, the algorithm LPviaLB computes an ε-feasible solution online
that achieves a value of (1 − ε) O ∗ with probability 1 − δ.
(For the formal version, see Theorem 4.1.) Moreover, the algorithm is very efficient and does not need
to solve any (offline) Linear Programs. Also, as is common in this context, our algorithm produces
integer solutions that compare favorably to the optimal offline fractional solution.
The assumption of the availability of an estimate for the optimal value is often a reasonable one (e.g.
when enough historic knowledge of the problem directly provides such an estimate). Nonetheless,
we show how to construct such an estimate as the columns arrive online. However, to obtain good
estimates we need to consider stable LPs, which informally means that allowing solutions to violate
the covering constraints by a small factor does not increase the optimal value by much (see Definition
5.2, and also Lemma 5.3 for a simple sufficient condition for stability). We note that a packing-only
LP is vacuously stable.
Informal Theorem 1.2 (Packing/covering LPs II). Consider a feasible, stable, packing/covering
multiple-choice LP in the random-order setting. Given ε, δ, assume that each right-hand side in the
) times the maximum coefficient of the left-hand side in its row, and that the
LP is at least Ω( log(m/δ)
ε2

optimal value is at least Ω( log(m/δ)
) times each individual item’s profit. Then with probability at least
ε2
1 − δ the algorithm DLA computes an ε-feasible solution online that has value at least (1 − ε) times
the optimal value of the offline LP.
(The formal version appears as Theorem 6.2.) The high-level idea to obtain an estimate of the
optimum is reasonably standard at this point ([Kle05, DJSW11, AWY14, MR12, ESF14]: one solves
an LP with the columns seen so far to obtain an estimate, which is updated at doubling times.
However, the presence of covering constraints introduces additional technical difficulties, and we need
the assumption of stability of the LP to control the variance of estimate produced (this issue is further
discussed in §1.4.1).
Packing LPs. Informal Theorem 1.2 assumes that individual item profits are small compared to
the optimal value. While this is often reasonable, can we remove this assumption? Our final result
removes all assumptions about the magnitude of the profit whenever
P t we are dealing with packing-only
LPs (and without multiple-choice constraints of the form
j xj ≤ 1). Obtaining good estimates
of opt without any assumptions on the item values in our setting requires significantly new ideas
(also discussed further below in §1.4.1). (The formal version of the following theorem appears as
Theorem 7.11.)
Informal Theorem 1.3 (Ultimate packing LP). Consider a packing LP in the random-order setting.
) times any left-hand side entry. Then the
Given ε > 0, suppose the right-hand sides are Ω( log(m/ε)
ε2
algorithm mDLA computes a solution online with expected value at least (1 − ε) times the optimal
value of the offline LP.
Generalized load balancing. The main building block for our algorithms for packing/covering
LPs is the ability to solve the following generalized load-balancing problem: We have a set of m
3

machines. For each arriving job t, there are k different options on how to serve it, and the j th choice
requires some amount of processing on each of the machines, given by the vector (at1j , at2j , . . . , atmj ).
When the job arrives, we must (fractionally) choose one of these options. The goal is to minimize
the makespan, i.e., the maximum total processing assigned to any machine. Notice that when the
matrices At ’s are diagonal m × m, the j th choice places atjj load only on the j th machine, and hence
captures the classic problem of scheduling on unrelated machines.
Informal Theorem 1.4 (Load-balancing). Consider the load-balancing problem where the jobs arrive
in random order. Given ε > 0, if the optimal makespan λ∗ is at least Ω( log(m/δ)
) times the maximum
ε2
amount of processing required by any option for any job, the algorithm expertLB constructs an online
solution with makespan at most (1 + ε)λ∗ with probability 1 − δ.
(The formal version in Theorem 3.3 proves this with respect to a generic low-regret online learning
algorithm for the prediction-with-experts problem. For readability, here we instantiate it with parameters from the Multiplicative Weights Update algorithm.) The case where the jobs are i.i.d. draws
from some unknown distribution was considered in [DJSW11, Section 3], where with probability 1 − δ,
)
a (1 + ε)-approximation to the optimum makespan is obtained assuming the optimum is Ω( log(m/δ)
ε2
t
times the maximum processing aij . Our theorem above shows that the same guarantee holds in the
more general random-order model, answering an open question from [DJSW11].
In fact, we can handle processing requirements that can be both positive or negative, as long as for each
machine the jobs are mostly positive or mostly negative (see Definition 3.1). Handling negative processing requirements is crucial for addressing covering constraints when we reduce packing/covering
LPs to the generalized load-balancing problem. We note that [DJSW11] also considered this generalized load-balancing problem in connection with packing/covering LPs; however, they do not consider
negative processing times and thus do not provide a direct reduction between the problems.

1.3

The Road-map

Our algorithmic development is modular: before elaborating on our technique, let us lay out the plan
of attack.
• In §3 we show our results for generalized load-balancing on random-order arrival streams via
online learning algorithms.
• In §4 we give a simple reduction that reduces solving packing/covering LPs with an estimate of
the optimal value to generalized load-balancing, and hence prove Theorem 1.1.
• In §5 we show how to estimate the optimal value for packing/covering LPs.
• In §6, we combine ideas from §4 and §5 to prove Theorem 1.2, our main result about packing/covering LPs.
• Finally, in §7 we refine the results of §6 for packing-only LPs: we remove the requirement that
the individual item profits should be small, and get Theorem 1.3.

1.4

Our Techniques

Decoupling primal and dual via online learning. Dual-based method are very important in
optimization under uncertainty and have been used extensively in the Operations Management literature [Sim89, Wil92, TR98]. One advantage of primal-dual methods is that they typically have
fast update times, and avoid solving an LP at every step of the process. In addition, the computed
duals can be used as a good heuristic to estimate the importance of each constraint and to perform
sensitivity analysis.
Most of the works on packing LPs in the random-order model [DH09, FHK+ 10, AWY14, MR12]
use the following form of the primal-dual approach (the primal-only algorithm of [KRTV13] being a
4

notable exception)2 : a good dual LP solution is estimated based on the columns seen so far, then the
reduced costs defined by this dual are used to decide how to set the primal variables. While being
a natural idea, analyzing it poses the following crucial difficulty: the primal and dual solutions, by
construction, are correlated in a non-trivial manner. In order to deal with these correlations, all of
the above analyses resort to a massive union bound, which is the root of the extra log n and m factors
over the right ratio bound Ω(ǫ−2 log m).
One of our contributions is an alternative algorithmic construction where the primal and the dual are
only loosely coupled. For that, we construct duals using a generic regret-minimizing online learning
algorithm (which offers adversarial guarantees); in the primal, we use a greedy strategy which ensures
that, with respect to these duals, we are doing at least as well as the optimal offline solution.
The fact that the guarantees for the dual hold in the adversarial setting, together with the greedy
primal step, reduces the analysis of the algorithm to that of comparing the dual solution constructed
to the offline optimal solution (see §3.4). Since the latter is a fixed solution (modulo the permutation
of the columns), it is only loosely correlated with our constructed dual; in fact, correlations only arise
because in the random-order model we are sampling without replacement (in particular, in the weaker
i.i.d. model there are no such correlations, see §3 up to equation (3.1)).

As far as we know, this is the first explicit black-box connection between online learning and optimization in the random-order model (see §1.5 for independent and subsequent work); in the offline
packing/covering LP setting such a connection was implicit in, e.g., [PST95, You01, GK07] and
made explicit in, e.g., [Kha04, Haz06, AHK12, CHW12]. In the simpler i.i.d. setting, [DJSW11] uses
multiplicative-weights based dual updates. This is reminiscent of the Multiplicative Weight Update
algorithm for online learning. Our analysis abstracts out the reliance on the details of that technique,
giving a clean conceptual explanation of what is happening. It also allows us to use any experts online
learning algorithm in our reductions, where the quality of the LP solution depends on the parameters
in the rate of regret. Importantly, this isolation between the analysis of the online learning algorithm
and the comparison of our dual solution and the offline optimum is instrumental in dealing with the
dependencies arising in the random-order model.
Handling dependencies in random permutations. Despite the loose coupling of primal and
dual solutions, the correlations arising from sampling without replacement cannot be immediately
handled: the known bounds on the statistical distances between sampling with and without replacement (e.g. [DF80]) do not seem to be strong enough, and a simple approach requires taking a union
bound across all time steps, leading again to extra log n factors. To overcome this, we instead use a
maximal inequality for sampling without replacement to compare sampling with/without replacement
at every time step while avoiding a union bound, together with martingale concentration inequalities.
The arguments we develop are quite general and may find use in other problems in the random-order
model.
1.4.1

Estimating OPT: Challenges and Ideas

In our approach we need to estimate (with high probability) the optimal value opt of the offline LP.
Under the assumption that the individual item profits are small compared to opt, such estimate can
be obtained by solving the LP comprising the first few columns seen in random order, and scaling its
optimal value appropriately (actually for packing/covering LPs even this case is not that easy, and we
require stability from the LP to provide guarantees for such estimates). However, without assuming
anything on the individual item sizes, as we do for the packing-only case in §7, the high-valued items
make this estimate have too high a variance and precludes the high-probability guarantees required.
2

Primal-dual methods of a slightly different flavor are also extensively used in the worst-case model of online algorithms
[BN09].

5

In fact all previous approaches that use explicit estimates of opt make the additional assumption
2
that each item profit is at most O( logε m ) opt [DJSW11, ESF14, AD15]3 To remove such assumptions,
we show that one can simply pick all items with sufficiently high value and add them to an (1 − ε)approximation for the remaining LP (which then does not contain high-valued items) and this only
incur a small loss in total profit (see §7, in particular Lemma 7.3). Unfortunately we also need to
estimate the threshold of what constitutes high enough value; this is however an easier task, since we
only need weak guarantees for this estimate. This estimate is obtained by again looking at the LP
comprising the first few columns seen in random order but removing the K highest valued items in this
sample; this provides sufficient control on the remaining item values for the analysis to go through.

1.5

Independent and subsequent work

Independent to our work, Kesselheim et al. [KRTV13] present a primal algorithm that achieves the
first optimal guarantee for packing-only multiple-choice LPs. More precisely, if d is the columnsparsity of the LP (i.e., maximum number of non-zero entries in each column), they obtain an (1 −
ε)-approximation as long as the right-hand sides/item sizes ratios are at least Ω(ǫ−2 log d). The
dependence on the column-sparsity d rather than the number of constraints m (and the fact they
handle multi-choice constraints) makes their result quantitatively stronger than our Theorem 1.3,
while both results coincide and are optimal for d = Ω(m) [AWY14]. However, our algorithm is more
efficient since it requires us to solve only a small number of offline LPs, while their algorithm solves an
LP at each of the n timesteps (in the experiments presented in [ESF14], the algorithm from [KRTV13]
is 2 to 3 orders of magnitude slower than algorithms that solve roughly as many LPs as ours does).
Subsequent to our work, Eghbali et al. [ESF14] provided a primal-dual algorithm for solving more
general packing-type convex programs. They also propose a primal-dual algorithm that draws inspiration from [DJSW11]; in particular, they also use a sort of exponential update of duals. In their
analysis, they also employ martingale methods and a (Doob’s) maximal inequality.
Also subsequent to our work, Agrawal and Devanur [AD15] consider an even broader class of online
convex programs (see the paper for proper description). Their primal-dual algorithm extends the
one we present in §3 for the load-balancing problem and generalizes our connection between online
(convex) learning and i.i.d./random-order convex optimization. A key element for this generalization
is the use of Fenchel duality. One drawback is that their general result only satisfies the constraints
in expectation. However, for the case of packing-only LPs their techniques are able to give bona fide
feasible solutions also with optimal guarantees.
Finally, independently Agrawal and Devanur [AD14] used a similar technique to devise efficient an
algorithm for the Bandits with concave rewards and concave knapsacks problem (Algorithm 3), again
using Fenchel duality. They trace back the inspiration for this approach to [ABH11], which show how
solve the Blackwell approachability problem (which at a very high-level asks for a sequence of iterates
that approaches a convex set) using online convex optimization.

2

Preliminaries

For a vector v ∈ Rk , define its max-norm kvkmax := maxj vj ; notice this does not involve absolute
values as in the definition of the ℓ∞ norm. Also, we use |v| := (|v1 |, |v2 |, . . . , |vk |) to denote
P the
k
k
component-wise absolute value of a vector. Recall that
P ∆ denotes the simplex {p ∈ [0, 1] : i pi =
1}, and Nk denotes the “full simplex” {x ∈ [0, 1]k : j xj ≤ 1}.
3

The requirement in [AD15] comes from the use of Lemma 14 from [DJSW11], which uses this assumption.

6

2.1

Prediction-with-experts problem

As mentioned before, our primal-dual algorithms will have their dual solutions constructed via an
algorithm for maximization version of the classic prediction-with-experts problem [CBL06]. In this
online problem, adversarial vectors o1 , o2 , . . . , on ∈ [−M, M ]m are presented one by one to the
algorithm. At time t, using only the information o1 , . . . , ot−1 up to time t − 1, the algorithm needs to
compute a vector wt in the P
simplex ∆m ; it then incurs a reward of wt , ot . The goal is to maximize
the total reward obtained t wt , ot . (Note we have stated this problem with the domain of the
adversarial vectors being the scaled one [−M, M ]m instead of [−1, 1]m .)
The quality of the solution constructed by the algorithm is measured using the notion of regret,
which compares
againstP
the best fixed w ∈ ∆m that knows all the vectors ot in hindsight, namely
P
t
maxw∈∆ t w, o = k t ot kmax . Here we consider a slightly different parametrization of regret,
which is also used in [AHK12, KV05].
Definition 2.1 (Regret). We say that an algorithm for the prediction-with-experts problem has (α, R)regret if the solution w1 , . . . , wn constructed satisfies
n
X

t

w ,o

t

t=1

≥

n
X
t=1

t

o −α

n
X

ot

t=1

max

− R.

This problem has been extensively
studied and many algorithms achieving optimal regret are known
√
[SS11]. The traditional (0, M n log m)-regret is attained by several algorithms and is known to be
optimal if the first parameter α in the regret is kept at 0. However, the guarantee that works best for
our purposes is attained by the well-known Multiplicative Weights Update algorithm, which gives an
(α, R)-regret with (typically) much smaller value of R at the expense of a non-zero α.
Theorem 2.2 (Theorem 2.5 of [AHK12]). For every ǫ ∈ [0, 1], the Multiplicative Weights Update
m
)-regret.
(MWU) algorithm with learning parameter ǫ achieves (ǫ, M log
ǫ

2.2

Concentration inequalities

Another important tool for our analyses are strong concentration inequalities for non-independent
processes. First we need a version of Bernstein’s inequality for sampling without replacement.
Theorem 2.3 (Theorem 2.14.19 in [vdVW96]). Let Y = {Y1 , . . . , Yn } be
Pa set of real numbers1 in
P the
interval [0, M
P]. Let S be a random subset of Y of size s and let YS = i∈S Yi . Setting µ = n i Yi
and σ 2 = n1 i (Yi − µ)2 , we have that for every τ > 0


τ2
Pr(|YS − sµ| ≥ τ ) ≤ 2 exp −
2sσ 2 + τ M
Notice that we can use the fact Yi ∈ [0, M ] to upper bound the variance σ 2 as
!
X
X
X
M
M
|Yi − µ| ≤
|Yi | +
|µ| = 2M µ,
σ2 ≤
n
n
i

i

i

which directly gives the following.

Corollary 2.4. Let Y = {Y1 , . . . , Yn } be a P
set of real numbers in the
P interval [0, M ]. Let S be a
random subset of Y of size s and let YS = i∈S Yi . Setting µ = n1 i Yi , we have that for every
τ > 0,


 2


τ
τ
τ2
,
≤ 2 exp − min
.
Pr(|YS − sµ| ≥ τ ) ≤ 2 exp −
M (4sµ + τ )
8M sµ 2M
7

We also need a maximal Bernstein’s inequality for sampling without replacement. While we could
not find such inequality explicitly stated in the literature, it easily follows from Theorem 2.3 and a
Levy-type maximal inequality for exchangeable random variables of [Pru98]; its proof is presented in
Appendix A.
Lemma 2.5. Consider a set of real values x1 , . . . , xn in [0, 1], and let X1 , . . . , Xk be sampled
without
1 P
replacement
from
this
collection.
Assume
k
≤
n/2.
Let
S
=
X
+
.
.
.
X
.
Also
let
µ
=
i
1
i
i xi and
n
1 P
2
2
σ = n i (xi − µ) . Then for every α > 0




(α/24)2
.
Pr max |Si − iµ| ≥ α ≤ 30 exp
i≤k
2kσ 2 + (α/24)
Finally, we need the following classic martingle concentration inequality.
Theorem 2.6 (Freedman’s Inequality [Fre75]). Let X0 , X1 , . . . , Xn be a real-valued martingale, with
X0 = 0, with respect to a filtration F0 ⊆ F1 ⊆ . . . ⊆ Fn . Let
PYt = Xt − Xt−1 be the martingale
differences, let M be such that |Yt | ≤ M for all t and let L = i≤n Var(Yt | Fi−1 ) be the predictable
variance. Then for every real numbers α, σ 2 ≥ 0,



α2
Pr Xn ≥ α and L ≤ σ 2 ≤ exp − 2
2σ + 2M α

3

Load-balancing using experts

In this section we formally define the generalized load-balancing problem and present our online
algorithm for it. In the next section, we will use this algorithm to solve packing/covering LPs given
an estimate of the optimal value.

3.1

Definitions: offline and online instances

An instance of the offline version of the generalized load-balancing problem isP
a set of matrices {At }t ,
m×k
1
2
n
k
each in R
. The goal is to find vectors p , p , . . . , p ∈ ∆ to minimize k nt=1 At pt kmax , the load
of the most-loaded machine. We use λ∗ throughout to denote the offline optimum value. Notice that,
by adding a column of zeroes, we canPget an instance where one option is to do nothing, i.e., we can
change the problem to minimizing k nt=1 At pt kmax over pt ∈ Nk .

In the online version of this problem, we consider the random permutation model. Now the number
of time steps n is the only information known upfront. Let A1 , A2 , . . . , An be matrices sampled from
the set {A1 , . . . , An } uniformly without replacement. At time step t, the algorithm has seen matrices
A1 , . . . , At and must decide on a (random) vector pt ∈ ∆; the randomness is both due to the random
matrices
seen so far and the internal coin flips of the algorithm (if any). The goal is to minimize
Pn
t
k t=1 A pt kmax . The vectors {pt }t output by the algorithm are called the online solution for the
online instance {At }t corresponding to the offline instance {At }t .
P
Ideally we want guarantees that for any given ε, δ > 0, we get k nt=1 At pt kmax ≤ (1 + ε)λ∗ with
probability (1 − δ). Due to the online nature of the problem, such a guarantee is only conceivable if
λ∗ is “large” compared to the maximum size of the loads. In the rest of this section we show how to
get the best possible such guarantee.

3.2

Well-bounded instances

While instances arising from scheduling-type applications usually consist solely of positive loads, our
reduction used for packing/covering LPs generates instances where some entries Atij are also negative.
8

In order to get good guarantees, we need to control how negative these entries can be. Loosely
speaking, while the entries of the load matrices At can be in the symmetric interval [−M, M ], for each
machine we require that either the loads are mostly positive on all time steps (with any negative loads
being tiny), or they are mostly negative on all time steps.
Definition 3.1 (Well-bounded instance). For M, γ ≥ 0, an instance A1 , . . . , An of the load-balancing
problem is (M, γ)-well-bounded if Atij ∈ [−M, M ] for all i, j, t, and moreover for each i ∈ [m] we
∗
∗
have: either Atij ≥ − γλn for all j and t ∈ [n], or Atij ≤ γλn for all j and t ∈ [n].
In particular, this is satisfied with γ = 0 if the At ’s are non-negative. The reader can think of γ as a
small constant, say one. The main motivation behind this definition is that it allows us to control the
variation of random processes defined over {At }t in a way similar to how we obtained Corollary 2.4.
Lemma 3.2. Suppose {At }nt=1 is an (M, γ)-well-bounded instance for some M, γ ≥ 0, and consider
p̄1 , . . . , p̄n ∈ ∆k . Let the sequence A1 p̄1 , . . . An p̄n be sampled without replacement from the set {At p̄t }t .
Then for every event E and for every i ∈ [m] and t ∈ [n],




2γλ∗
t t
t t
E Ai p̄ − E[Ai p̄ | E] E ≤
+ 2 E Ati p̄t | E .
n
∗

Proof. Fix i ∈ [m]. Using the well-boundedness condition, define v̄it as follows: if Ati p̄t ≥ − γλn for all
∗
∗
t, set v̄it = Ati p̄t + γλn for all t; else set v̄it = γλn − Ati p̄t . By definition for all t we have v̄it ≥ 0, and
since we did a uniform shift
h
i
h
i






E Ati p̄t − E[Ati p̄t | E] E = E v̄it − E[v̄it | E] E ≤ E |v̄it | E + E v̄it | E = 2E v̄it | E .

But it is easy to see that E[v̄it | E] ≤

3.3

γλ∗
n

+ E[Ati p̄t | E] , which concludes the proof.

The expertLB algorithm and its guarantee

Given an online instance {At }t to the generalized load-balancing problem and values n, M , and ε, the
following algorithm expertLB (for “expert load-balancing”) runs a primal greedy strategy and for
the dual any prediction-with-experts algorithm, restarting at timestep n/2.
Algorithm 1 expertLB
for each time t do
let At be the arriving random item
primal step: choose pt ∈ ∆k to minimize wt At , pt
⊲ play best-response
dual step: feed At pt to a prediction-with-experts algorithm (whose current state is wt )
let wt+1 be the resulting state of the algorithm.
if t = n/2 then
restart the state of the prediction-with-experts algorithm ⊲ restart algorithm at half-time
end if
end for
Note the simplicity of the algorithm: it is perhaps the “natural” algorithm, once we decide to reduce
load-balancing to a prediction-with-experts algorithm. The only non-intuitive step is perhaps that we
restart the process at time n/2. This ensures that at each step, the current state depends on at most
n/2 − 1 of the random choices from the A1 , . . . , An , and hence the next random item still has “enough
9

randomness” for our analysis to go through4 . Also, another interpretation of the algorithm is that
the dual vectors wt ∈ ∆m are providing (adaptive) aggregations of the m machines into a single one,
in which case the best action is just to minimize the load on this machine (which is exactly what our
best-response primal step is doing).
The following theorem shows if the offline optimal load λ∗ is not too small, then expertLB obtains
value almost equal to λ∗ up to the regret of the prediction-with-experts algorithm used.
Theorem 3.3 (Load-balancing guarantee). Suppose {At }t is (M, γ)-well-bounded load-balancing in1
and δ ∈ (0, ε] are such that
stance for γ ≥ 1. Let λ∗ be its optimal load and suppose ε ≤ ε1 := 84
3M log(m/δ)
∗
λ ≥
. If the algorithm expertLB is run with any prediction-with-experts algorithm with
ε2
(α, R)-regret, then it returns a solution {pt }t such that with probability at least 1 − δ
X
t

At pt − α

X

At pt
max

t

≤ λ∗ (1 + c1 γε) + 2R,

for a universal constant c1 . In particular, if the MWU algorithm from Theorem 2.2 is used with
learning parameter ε, the guarantee becomes (for a slightly larger constant c1 )
X
t

At p t − ε

X

At pt
max

t

≤ λ∗ (1 + c1 γε).

The case when the load matrices are non-negative is of independent interest (generalizing scheduling
on unrelated machines); in this case well-boundedness means Atij ∈ [0, M ] and we can set γ = 1 to
get:
Corollary 3.4 (Positive loads guarantee). Suppose {At }t is a load-balancing instance with Atij ∈

1
[0, M ], and optimal load λ∗ . Suppose ε ≤ ε1 := 84
and δ ∈ (0, ε] satisfy λ∗ ≥ 3M log(m/δ)
. Given n, M
ε2
t } such that
and
ε,
the
algorithm
expertLB
(with
the
MWU
algorithm)
finds
an
online
solution
{p
t
P t t
k t A p k∞ ≤ (1 + O(ε))λ∗ with probability at least 1 − δ.

In the rest of §3 we prove Theorem 3.3. We first show in §3.4 that the maximum load is close in
expectation to λ∗ . We then extend these ideas to prove the high-probability guarantee in §3.5.

3.4

The guarantee in expectation

Let p∗ 1 , . . . , p∗ n be the optimal solution for the offline instance. We see this as a mapping from matrix
At to solution p∗ t (say φ(At ) = p∗ t ); this way, define p∗ t as the random solution with respect to the
random matrix At (i.e. p∗t = φ(At )).
To simplify the notation, let ot := At pt denote the load vector incurred at step t by our algorithm.
Also, for an integer ℓ, we use A≤ℓ to denote the sequence A1 , . . . , Aℓ , and similarly for other objects.
P t
P t
Theorem 3.3 seeks to bound
to −α
t |o | max . By the exchangeability of sampling without
1
n/2
replacement, (A , . . . , A ) has the same distribution as (An/2+1 , . . . , An ). This implies that our
algorithm, with its half-time reset, behaves in the same way in the two halves of the process, namely
(A≤n/2 , p≤n/2 ) has the same distribution as (A>n/2 , p>n/2 ); thus, it suffices to analyze the first half.
P
P
t
t
Fact 3.5 (Suffices to analyze first half). The random variables
t≤n/2 o − α
t≤n/2 |o | max and
P
P
t
t
t>n/2 o − α
t>n/2 |o | max have the same distribution.
4

The formal reason why we need this restart is that Lemma 2.5 (because of Theorem A.1) can only handle up to half
of the random sequence.

10

Now
need that
the computed dual solutions wt capture our (non-linear) total load, i.e., that
P we
P
t
t t
t w ,o ≈ k
t o kmax ; but this follows directly from the fact we used an (α, R)-regret predictionwith-experts algorithm.
Fact 3.6 (Dual captures load). For every scenario we have
n/2
X

wt , ot

t=1

≥

X

t≤n/2

ot − α

X

t≤n/2

|ot |

max

− R.

Furthermore, let o∗ t := At p∗ t denote the load incurred by the optimal solution p∗ at step t. By our
primal greedy choice of the pt ’s, we directly have the following.
Fact 3.7 (Optimality of algorithm wrt duals).
n/2
X
t=1

wt , ot =

n/2
X
t=1

w t At p t ≤

n/2
X
t=1

w t At p ∗ t =

n/2
X

wt , o∗ t .

t=1

P
P
Pn/2 t ∗t
t
t
Together these give
and so in order to upper
t=1 w , o
t≤n/2 o − α
t≤n/2 |o | max ≤ R +
bound our load in expectation it suffices to show that


 X
 X
X
λ∗
∗t
t ∗t
t
∗t
.
(3.1)
o
w ,o
E[w ], E[o ] ≤ E
=
.
E
2
max
t≤n/2

t≤n/2

t≤n/2

Notice that these are easy implications if we were sampling with replacement, since in that case wt
and o∗ t are independent. For the random permutation model we need to work harder because they
are dependent: wt is determined by the history A<t and the optimal solution’s load o∗ t at time t
depends on the history A<t (since items that have occurred in the history cannot occur at time t).
However, this dependence of o∗ t on the history A<t should be quite small. In fact this is the main
<t
∗t
tool for our analysis: we show that E[o∗t
i | A ] ≈ E oi happens for most histories, for all t, i. ∗More
γλ
<t
∗t
∗t
precisely, we show that for each i, with high probability E[o∗t
i | A ] = E oi ± O(ε) · (|E oi | + n ) for
∗t
all t ≤ n/2 simultaneously. Note that applying Bernstein’s inequality to each oi and taking a union
γλ∗
<t
∗t
∗t
bound over the t’s would only give E[o∗t
i | A ] = E oi ± O(ε log n) · (|E oi | + n ), with an extra log n
factor. To avoid this we employ a maximal version of Bernstein’s inequality. To simplify the notation,
we use the shorthand Et X := E[X | A<t ] for expectations conditioned on the history before time t.
∗t
Lemma 3.8. Consider i ∈ [m]. Then with probability at least 1 − mδ2 we have Et [o∗t
i ] ∈ E oi ±
∗
γλ
n
80ε(|E o∗t
i | + n ) for all t ≤ 2 simultaneously.
P
∗
Proof. Let µ = n1 t≤n Ati p∗ t ≤ λn be the expected value of o∗t
i , which is independent of t. Notice
Pn
P
∗j
∗j
th
that in every scenario j=1 oi − j<t oi gives the total i load from items that have not shown
up at times j < t. Therefore, the conditional expected ith load at time t is the average over these
remaining items:
Pn
P
P
∗j
∗j
nµ − j<t o∗j
j=1 oi −
j<t oi
i
∗t
=
.
(3.2)
Et [oi ] =
n − (t − 1)
n − (t − 1)
P
∗j
Thus, to control Et [o∗t
i ] it suffices to control the sum
j<t oi , which should be highly concentrated
around the mean (t − 1)µ.

For that, let α = n|µ| + γλ∗ ; we want to use the maximal Bernstein’s inequality
for sampling without
P
replacement (Lemma 2.5) to bound the maximum deviation maxt≤n/2 | j≤t o∗j
i − tµ| ≤ 40εα with
11

P
probability at least 1 − mδ2 . For that, we need to bound the variance V := n1 t≤n (Ati p∗t − µ)2 =

 ∗t
∗t . Then employing Lemma
∗t 2
∗t
E(o∗t
i − E oi ) . Since oi ∈ [−M, M ], we have that V ≤ M · E oi − E oi
∗
3.2 to bound this absolute value we get V ≤ M (2|µ| + 2γλ
n ) = 2M α/n. Thus, applying the maximal
Bernstein’s inequality Lemma 2.5 we obtain
!




P
40ε 2
α2
∗j
Pr max | j≤t oi − tµ| ≤ 40εα ≤ 30 exp −
24
nV + 40εα(M/24)
t≤n/2
!

 2 ∗

40ε 2
ε γλ
α
δ
≤ 30 exp −
≤ 30 exp −
≤ 2,
24
(2 + 40ε/24)M
M
m
where we used δ ≤ ε ≤

1
80 ,

γ ≥ 1, and λ∗ ≥

3M log(m/δ)
.
ε2

Whenever this event holds equation (3.2) gives that for any t ≤ n/2
Et [o∗t
i ]∈

(n − (t − 1)) µ ± 40εα
40εα
80εα
=µ±
∈µ±
,
n − (t − 1)
n − (t − 1)
n

where the last inequality uses t ≤ n/2. The lemma then follows from the definition of α.
Using this lemma it is not difficult to show that inequality (3.1) approximately holds. We sketch how
this can be done in order to illustrate that little of the structure of the problem is actually used (and
thus might carry over to other settings). This inequality plus Facts 3.5–3.7 imply that the bound in
Theorem 3.3 holds in expectation. (We remark that this guarantee in expectation does not require
Lemma 3.8 to hold simultaneously for all t ≤ n/2; this will only be required below for our guarantee
with high probability.)
hP
i
∗
t , o∗ t
Lemma 3.9. We have E
≤ λ2 + O(εγλ∗ ).
w
t≤n/2
Proof sketch. Let E denote the event that the approximation from Lemma 3.8 holds for every i ∈ [m],
δ
which from a union bound then holds with probability at least 1 − m
. Let us split the expectation in
the left-hand side of the lemma based on E:


 X

 X
 X
t ∗t
t ∗t
t ∗t
w ,o
E Pr(E).
(3.3)
w ,o
E Pr(E) + E
w ,o
=E
E
t≤n/2

t≤n/2

t≤n/2

To upper bound the first term we further split the expectation by conditioning on the history up to
time t − 1 and recalling that wt is defined by it:

 X
i
i
i
X h h
X h
t ∗t
w ,o
E =
E E wt , o∗ t | A<t , E E =
E wt , E[o∗t | A<t , E] E . (3.4)
E
t≤n/2

t≤n/2

t≤n/2

Recalling the guarantee of Lemma 3.8 for E, we can bounds the innermost expectation by
E[o∗t | A<t , E] ≤ E o∗t + 80ε|E o∗t | + O(εγ)

λ∗
λ∗
λ∗
1 ≤ max{(1 + 80ε)E o∗t , 0} + O(εγ) 1 ≤ (1 + O(εγ)) 1,
n
n
n

1
where the second inequality uses that ε ≤ 80
and the last one uses the optimality o∗t ≤ (λ∗ /n)1.
Plugging this bound onto inequality (3.4) gives that we can upper bound the first term in equation
∗
(3.3) by (1 + O(εγ)) λ2 .

To upper bound the second term in equation (3.3), using the well-boundedness
of the instance it is
P
∗
not hard to show that in every scenario the sum of optimal loads satisfies t≤n/2 o∗t
i ≤ O(γ)λ , and
P
ε
δ
≤ m
, we can upper bound
thus t≤n/2 wt , o∗t ≤ O(γ) mλ∗ . Since E¯ only holds with probability m
∗
the second term in equation (3.3) by O(εγ) λ .

Putting these bounds together concludes the proof of the lemma.
12

3.5

The guarantee with high probability

We now show that Lemma 3.9 actually holds with high probability.
Lemma 3.10. With probability at least 1 − 3δ we have
P
t ∗ t ≤ (1 + 168εγ) λ∗ .
t≤n/2 w , o
2

Again, if we were sampling with replacement, then it would not be difficult to show that wt , o∗ t − wt , E o∗ t
is a P
martingale difference
martingale concentration inequalities would imPsequence, and consequently
P
∗
ply t≤n/2 wt , o∗ t . t≤n/2 wt , E o∗ t ≤ t≤n/2 kE o∗ t kmax . λ2 with good probability. For our
case of sampling without replacement,
we proceed similarly, but using the martingale difference se
t
t
t
∗
t
∗
quence w , o − w , Et [o ] t (notice the conditioning on the history), and then using Lemma
3.8 to get that with good probability for all t we have Et [o∗t ] ≈ E[o∗t ].
So define the random variable Yt := wt , o∗ t − Et [o∗ t ] . Since wt is determined by A<t , we have that
Et [Yt ] = 0 and hence (Yt )t is indeed a martingale difference sequence (adapted to (At )t ). In order
to obtain concentration for this martingale, we first need to control its conditional variance, which is
accomplished in the next lemma.
δ
we have
Lemma 3.11. With probability at least 1 − m
X
X
wt , E o∗ t
Var(Yt | A<t ) ≤ 4M ·
t≤n/2

+ 4M γλ∗ .

t≤n/2

2
Proof. Since o∗t
i ∈ [−M, M ], we have Yt ∈ [−2M, 2M ] and hence Yt ≤ 2M |Yt |. Since Et [Yt ] = 0,
for all the histories we have
 X


∗t
Var(Yt | A<t ) = Et [Yt2 ] ≤ 2M · Et |Yt | = 2M · Et
wit o∗t
−
E
[o
]
t i
i
i

≤ 2M

X
i

wit Et



 Lemma 3.2
∗t
≤
4M wt , Et [o∗t ]
o∗t
i − Et [oi ]

+

4M γλ∗
,
n

where the last inequality uses wt ∈ ∆m .

To conclude the proof, we need the approximation E[o∗t ] ≈ Et [o∗t ]. For that, let E be the event that
the guarantees from Lemma 3.8 hold for all i ∈ [m]; by a union bound, we have that E happens with
δ
probability at least 1 − m
. Under the event E, we have that for all t ≤ n/2
∗t
∗t
|Et o∗t
i | ≤ |E oi | + 80ε|E oi | +

γλ∗
80εγλ∗
≤ 2|E o∗t
|
+
,
i
n
n

1
. Thus, under the event E we have Var(Yt | A<t ) ≤ 8M wt , |E o∗t | +
where the last inequality uses ε ≤ 80
8M γλ∗
. Adding over all t ≤ n/2 then gives the lemma.
n

Now we can use our martingale to prove Lemma 3.10.
Proof of Lemma
employ Freedman’s inequality to the martingale (Yt )t . For that,
P 3.10.t We first
∗t
let α := 4 t≤n/2 w , |E o | + 4γλ∗ , so that M α upper bounds the conditional variance σ 2 :=
P
δ
<t
t≤n/2 Var(Yt | A ) with probability 1 − m . Then from Freedman’s inequality (Theorem 2.6) we get
that
 2 ∗

 2 2
 X
ε γλ
δ
ε α
2
≤ exp −
≤ ,
Yt > εα and σ ≤ M α ≤ exp −
Pr
4M α
M
m
t≤n/2

13



t

δ
. Since Pr(σ 2 ≤ M α) ≥ 1 − m
where the last inequality uses γ ≥ 1 and λ∗ ≥ 3M log(m/δ)
, a union
ε2
P
2δ
bound gives that with probability at least 1 − m we have t≤n/2 Yt ≤ εα. Expanding the definition
of Y and α, this is equivalent to
X
X
wt , Et o∗t + 4ε|E o∗t | + 4εγλ∗ .
(3.5)
wt , o∗t ≤
t≤n/2

t≤n/2

To upper bound the first term in the right-hand side, employing Lemma 3.8 to each i ∈ [m] we have
δ
the following holds for all t ≤ n/2:
that with probability at least 1 − m
Et o∗t + 4ε|E o∗t | ≤ E o∗t + 84ε|E o∗t | +

80εγλ∗
80εγλ∗
λ∗
1 ≤ max{(1 + 84ε)E o∗t , 0} +
1 ≤ (1 + 164εγ) ,
n
n
n

1
where the second inequality follows from the fact ε ≤ 84
and E o∗t ≤ (λ∗ /n)1. Plugging this bound
on inequality (3.5) and taking a union bound, we have that with probability at least 1 − 3δ
m

X

t≤n/2

wt , o∗t ≤ (1 + 168εγ)

λ∗
.
2

This concludes the proof.
Proof of Theorem 3.3. From triangle inequality we have
X
t

ot − α

X
t

ot
max

≤

X

t≤n/2

ot − α

X

ot

t≤n/2

+
max

X

t>n/2

ot − α

X

t>n/2

ot

.
max

Using Facts 3.6 and 3.7 and Lemma 3.10, with probability at least 1 − 3δ the first term in the right∗
hand side is at most (1 + 168εγ) λ2 + R. Since from Fact 3.5 the same bound holds for the second term
of the right-hand side, a union bound concludes the proof of the theorem with constant c1 = 168.

4

Solving packing-covering multi-choice LPs given estimate of OPT

This section shows how to solve packing/covering multiple-choice (PCMC) LPs via a simple reduction
to the generalized load-balancing problem from the previous section, provided an estimate of the
optimal value is available. In the following sections we show how to get such an estimate.
From §1.1, recall that a PCMC LP has the form:
Pn
max
π t xt
Pnt=1 t t
st
Ax ≤b
Pnt=1 t t
t=1 C x ≥ d

xt ∈ N k

(PCMC)
(4.6)
(4.7)
∀t ∈ [n],

(4.8)

where
all the data π t , At , C t , b, d is non-negative and Nk denotes the “full simplex” {x ∈ [0, 1]k :
P
j xj ≤ 1}. We use mp to denote the number packing constraints (4.6) and mc to denote the number
m ×k

mc ×k
. Given a
of covering constraints (4.7), so our matrices have dimensions At ∈ R+ p , and C t ∈ R+
PCMC LP L, we use opt(L) to denote its optimal value; we use simply opt when the LP is clear from
context.

In the online version of the problem there is a fixed PCMC LP L whose blocks {(π t , At , C t )}t are
presented one-by-one in random order. More precisely, the number of time steps n and the righthand sides b, d are known upfront, and the triples (π 1 , A1 , C1 ), . . . , (π n , An , Cn ) are sampled from
14

{(π t , At , C t )}t uniformly without replacement. Then define the randomly permuted LP L
(
)
X
X
X
t t
t t
t t
t
k
L = max
πx :
A x ≤ b,
C x ≥ d, x ∈ N ∀t
t

t

(4.9)

t

At time step t, the algorithm computes a (random) vector xt ∈ Nk based on the information seen up
to time t, i.e., (π 1 , A1 , C1 ), . . . , (π t , At , Ct ), plus n and b, d. We call the sequence {xt }t an online
solution.
We
an online solution {xt }t is ε-feasible for L if it satisfies
constraints (i.e.,
P say tthat
P the tpacking
t
t ≥ (1 − ε)d). The goal
A
x
≤
b)
and
almost
satisfies
the
covering
constraints
(i.e.,
C
x
t≤n
t≤n
in the online PCMC LP problem is P
to obtain an online solution {xt }t which (with high probability)
is ε-feasible, and obtains a reward t≤n π t xt ≥ (1 − O(ε))opt(L). Notice that opt(L) = opt(L), so
again we are comparing against the optimal offline solution.

4.1

The algorithm LPviaLB

We now give an algorithm LPviaLB that solves PCMC LPs via a natural reduction to the Load-balance
problem. The idea
Pis simple: The Load-balance problem can be thought as a congestion-minimization
problem min{λ : nt=1 At pt ≤ λ · 1, pt ∈ ∆k ∀t}, which is reminiscent of a packing-only LP where all
right-hand sides are the same.
bring a PCMC LP into this form, we introduce the objective function
Pn To
t
t
c (thereby requiring an estimate of opt), multiply the covering
as a covering constraint t=1 π x ≥ opt
constraints by −1 to obtain packing constraints, and shift/scale to ensure uniform right-hand sides.
Observe that the reduction creates negative entries on the left-hand side, which is why we considered
the Load-balance problem with possibly negative loads.
c of opt, define the matrices H 1 , . . . , H n with
More precisely, given a PCMC LP L and an estimate opt
k + 1 columns and mp + mc + 1 rows (indexed from 0 to m := mp + mc ) as follows: the zeroth row of
H t equals the vector
πkt 2 
π1t
t
2
H0,⋆
:= n2 − opt
c , . . . , n − opt
c,n ;
for i ∈ {1, . . . , mp }, the ith row of H t is

t
Hi,⋆
:=


atik
ati1
bi , . . . , bi , 0 ,

and for i ∈ {mp + 1, . . . , mp + mc }, the (mp + i)th row of H t is
t
Hm
:=
p +i,⋆

2
n

−

cti1
2
di , . . . , n

−

ctik 2 
di , n .

The algorithm LPviaLB can be thought of as running in phases, where it constructs the instance
{H t }t , feeds it to the algorithm expertLB, and outputs a scaling of the solution returned.
Algorithm 2 . LPviaLB
c ε, δ > 0, number n of items, and right-hand sides b and d.
Input: Reals opt,
Phase 1: Compute matrices H 1 , . . . , H n relative to the PCMC LP L.

Phase 2: Run algorithm expertLB (with the MWU algorithm from Theorem 2.2) over the
√
2ε2
generalized load-balancing instance {H t }t with parameters M = log((m+1)/δ)
, ε′ = 8ε and δ
(given), and let {x̃t }t be the returned solution.
btj :=
Phase 3: Define x
L.

(1−ε′ )
t
(1+4c1 ε′ ) x̃j

for j = 1, . . . , k. Return {b
xt }t as the solution for the PCMC LP
15

Some remarks are in order. Firstly, for simplicity we described the algorithm as running in phases, but
it is easy to implement this in an online fashion. Indeed, when at time t the algorithm sees a random
triple (π t , At , Ct ), it can construct the appropriate matrix Ht , feed it to algorithm expertLB to get
bt . Secondly, we used the algorithm expertLB
back the vector x̃t , and output the scaled version x
instantiated with the MWU algorithm, but this is for ease of exposition. We use the guarantees from
Theorem 3.3 in a black-box fashion, and hence could use any algorithm for the prediction-with-experts
problem (and obtaining different guarantees).
The guarantee of algorithm LPviaLB depends on the generalized width of the PCMC LP, defined as:
)
(
di
opt
bi
(4.10)
min min t , min t , min t .
i,j,t ci,j
t,j πj
i,j,t ai,j
The next theorem shows that algorithm LPviaLB with high probability returns an ε-feasible (1 − ε)optimal solution as long as the generalized width is Ω( log(m/δ)
) and a (1 − ε)-optimal under estimate
ε2
c
opt is available.
.

Theorem 4.1. Consider a feasible packing/covering multiple-choice LP L. Consider ε > 0 at most
a sufficiently small constant ε0 , and δ ∈ (0, ε], and assume that the generalized width of L is at least
log((1+mp +mc )/δ)
. Then LPviaLB finds an online solution {xt } that with probability at least 1 − δ is
ε2
P
c for constants c2 , c3 ≥ 1.
(c2 ε)-feasible for L and has value t π t xt ≥ (1 − c3 ε)opt,

4.2

Proof of Theorem 4.1

The idea is to first show that the reduction creates a load-balancing instance that is well-bounded,
and whose optimal load is not very small. With these guarantees, we apply Theorem 3.3 from §3 to
get a good load-balancing solution. Interpreting this as a solution to our PCMC LP will complete the
proof.
Assume that all hypotheses in the statement of Theorem 4.1 hold. Let {H t }t be the generalized
load-balancing instance relative to the input PCMC LP L, and let λ∗ denote the optimal value of
the instance {H t }t . We start by bounding λ∗ by relating the solutions for the instance {H t }t to the
solutions for the LP L.
Claim 4.2.

1
2

≤ λ∗ ≤ 1.

Proof. (Upper bound.) Let {xt }t be an optimal solution for the PCMC LP L, and for each t define
x̃t = (xt1 , . . . , xtk , 0) by appending a zero at the end of xt ; it suffices to show that {x̃t }t is a solution
for the load-balancing instance {H t }t with load at most 1.
P t t
P
The feasibility of {xt }t guarantees that for i ∈ [mp ] we have t Hi,⋆
x̃ = b1i t Ati,⋆ xt ≤ 1, and for
P t t
P t
x ) ≤ 1. Moreover, the optimality of {xt }t guarantees
i ∈ [mc ] we have t Hm
x̃t = 2 − d1i ( t Ci,⋆
c +i,⋆
P t t
P
c
that t H0,⋆ x̃ = 2 − 1 ( t π t xt ) = 2 − opt ≤ 1, where the last inequality follows from opt ≥ opt.
c
opt

c
opt

Thus, {x̃t }t achieves load at most 1 for {H t }t .

(Lower bound.)
an optimal solution x̃1 , . . . , x̃n ∈ △k for the load-balancing instance {H t }t ,
P tConsider
∗
t
so λ := k t H x kmax . Define xt = (x̃t1 , . . . , x̃tk ) by dropping the last component from x̃t .
P
P
P t t
t
For i ∈ [mp ] we have λ∗ ≥ t Hi,⋆
x̃ = b1i t Ati,⋆ xt , and hence t At λx∗ ≤ b. Moreover, for i ∈ [mc ]
P t t
P
P t
∗
t
x , and hence t C t λx∗ ≥ 2−λ
we have λ∗ ≥ t Hm
x̃t = 2 − d1i t Ci,⋆
λ∗ d ≥ d, where the last
p +i,⋆
16

t

inequality uses λ∗ ≤ 1 which was proved in the first part of the claim. Thus, { λx∗ }t is a feasible
solution for the LP L.
P t t
xt
1 P
t t
x̃ = 2 − opt
In addition, we have λ∗ ≥ t H0,⋆
t π x , and hence the solution { λ∗ }t obtains value
c
P t xt
2−λ∗ c
2−λ∗ c
t π λ∗ ≥ λ∗ opt. This must be at most the optimal value opt for the LP L, so opt ≥ λ∗ opt,
c
c
or λ∗ ≥ 2 opt ≥ 12 , where the last inequality follows from opt
2 ≤ opt ≤ opt. This concludes the
c
opt+opt

proof.

Claim 4.3. The instance {H t }t is (M, 4)-well-bounded for M =

2ε2
log((m+1)/δ) .

Proof. Using the lower bound λ∗ ≥ 12 from the previous claim, it suffices to show that each row of H t
contains entries that all lie in the interval [−M, n2 ], or all in the interval [− n2 , M ].
πt

t ≥ − j ≥ − M opt ≥ −M , where
For the zeroth row, the generalized width lower bound implies H0,j
c
c
2opt
opt
t ≤ 2 , it follows that H t ∈ [−M, 2 ]. For i ∈ [m ], we
c
≤
opt;
since
H
the last inequalityt uses opt
p
0,j
0,j
2
n
n
cti,j
2
t ≤ ai,j ≤ M . And for i ∈ [m ], we have H t
t
have 0 ≤ Hi,j
≤
and
H
≥
−
≥
−M
.
This
c
mp +i,j
mp +i,j
bi
n
di
concludes the proof.
√
2ε2
Proof of Theorem 4.1. Again let M = log((m+1)/δ)
and recall that ε′ = 8ε. Since Claims 4.3 and
4.2 guarantee, respectively, that the instance {H t }t is (M, 4)-well-bounded and has optimal value
λ∗ ≥ 3M log((m+1)/δ)
, we can applying Theorem 3.3 to obtain that the solution {x̃t }t returned by the
(ε′ )2
algorithm expertLB satisfies with probability at least 1 − δ
X
X
∀i = 0, . . . , m,
Hti,⋆ x̃t − ε′
(4.11)
|Hti,⋆ x̃t | ≤ λ∗ (1 + 4c1 ε′ ) ≤ (1 + 4c1 ε′ ),
t

t

where the last inequality follows again from Claim 4.2. Let E be the event that this bound holds. For
t
P P
t t
t = Ai,⋆ is non-negative, this means that conditioned on E we have
i ∈ [mp ], since Hi,⋆
t
j≤k Aij x̃j ≤
bi
′

1ε )
bi (1+4c
xt }t output by LPviaLB satisfies the packing constraints.
(1−ε′ ) and so the solution {b
1 P
t t
For i = 0 we have |Ht0,⋆ x̃t | ≤ n2 + opt
j≤k πj x̃j , and thus the left-hand side of inequality (4.11) is at
c
least




X
X
X
X
(1 + ε′ ) X X t t
1
2 − 1
πjt x̃tj  − ε′ 2 +
πjt x̃tj  = 2(1 − ε′ ) −
πj x̃j .
c
c
c
opt
opt
opt
t j≤k
t j≤k
t j≤k

So conditioned on E, inequality (4.11) gives
XX
t

j≤k

c
πjt x̃tj ≥ opt

(1 − ε′ )(1 − 2ε′ − c1 ε′ )
c
= (1 − O(ε′ )) opt,
(1 + 4c1 ε′ )(1 + ε′ )

where the last inequality uses the fact that ε (and hence ε′ ) is at most a sufficiently smallPconstant.
t bt =
Therefore, conditioned on E, we have that the solution output by LPviaLB satisfies
tπ x
(1−ε′ ) P P
t t
′
c
t
j≤k πj x̃j ≥ (1 − O(ε )) opt.
(1+4c1 ε′ )

An identical
shows that conditioned on E each covering constraint is O(ε′ )-approximately satPproof
t
t
b ≥ (1 − O(ε′ )) d. This concludes the proof of the theorem.
isfied, i.e., t C x

17

5

Estimating the optimal value based on sampled LPs

In ths preceding section, we saw how to solve a PCMC LP L given an estimate of opt(L). Now we
show how to obtain such estimates via “sampled LPs”. For that, we require the LP to satisfy a
stability condition. Loosely speaking this asks that the covering constraints are not “very tight” — if
we reduce the covering requirements by a little, the optimal value should not increase by a lot. First,
a definition to simplify notation:
Definition 5.1. Given a PCMC LP L and ε ∈ [0, 1), we define L(1 − ε) as the LP obtained by
multiplying the right-hand side of the covering constraints by (1−ε), but keeping the packing constraints
unchanged.
Notice that the feasible solutions for L(1 − ε) are exactly the ε-feasible solutions for L. Now we
formally define the stability property.
Definition 5.2 (Stability). A PCMC LP L is called (ε, σ)-stable if any optimal ε-feasible solution for
it has value at most (1 + σε) · opt(L), i.e., opt(L(1 − ε)) ≤ (1 + σε) · opt(L).
The following lemma gives a natural sufficient condition for an LP to be stable.
Lemma 5.3. If a PCMC LP L is such that L(1 + σ1 ) is feasible, then L is (ε, σ)-stable for every
ε ∈ (0, 1].
Proof. Consider any ε ≥ 0. Let {x̄t }t be a feasible solution for L(1 + σ1 ) and let {xt }t be an optimal
ε
ε
solution for L(1 − ε). Define x̃t = ε+1/σ
x̄t + (1 − ε+1/σ
)xt . It is easy to verify that {x̃t }t is feasible
for L and has value


n
X
ε
t t
π x̃ ≥ 1 −
opt(L(1 − ε)),
ε + 1/σ
t=1

ε
)opt(L(1−
where the inequality uses the non-negativity of the π t ’s. This implies that opt(L) ≥ (1− ε+1/σ
ε)), which is equivalent to opt(L(1 − ε)) ≤ (1 + εσ)opt(L). This concludes the proof.

The idea behind our estimator for opt(L) in the random-order model has been used in prior works
on packing-only LPs, e.g., [DH09, FHK+ 10, AWY14, MR12]: observe the first s random blocks
(π 1 , A1 , C1 ), . . . , (π s , As , Cs ) of the LP, and form the sampled LP with these blocks and right-hand
side scaled by a factor of ns :
Ps
t t
max
t=1 π x
Ps
s
t t
·b
(5.12)
st
t=1 A x ≤
n
Ps
s
t t
·d
t=1 C x ≥
n
xt ∈ Nk ∀t ∈ [s].
By the random-order assumption, the blocks (π t , At , Ct ) are an ns -sample of the underlying LP L,
and hence should be “representative” of the latter. Consequently, computing an optimal (ε-feasible)
solution for this sampled LP should give a good estimate of ns · opt(L).
In this work, we extend this idea beyond packing-only LPs, and allow for covering constraints as well.
This introduces complications, but the stability property defined above allows us to address them.
Let us define sampled LPs in the generality that we need.
18

Definition 5.4 (Restricted LP). Given a PCMC LP L, and a subset I of [n], the restricted LP LI is
obtained by retaining only the columns of L that belong to I, and setting the right-hand side rhs(LI )
to be |I|
n rhs(L), namely
P
t t
max
t∈I π x
P
|I|
t t
·b
(LI )
st
t∈I A x ≤
n
P
|I|
t t
·d
t∈I C x ≥
n
xt ∈ Nk ∀t ∈ I.
Notice that the restricted LP L{1,...,s} is exactly the sampled LP of (5.12). Moreover, since the
sequence of random variables (π 1 , A1 , C1 ), . . . , (π n , An , Cn ) is exchangeable (i.e., every subsequence
of same size has the same joint distribution), LI has the same distribution as the sampled LP L{1,...,s}
for every s-subset I ⊆ [n] (only the indices of the variables are different).

In the following, we will need a more refined control over the ratio of item profits to opt, we define
the width of a PCMC LP L as
)
(
di
bi
.
(5.13)
min min t , min t
t,i,j aij t,i,j cij
πt

i,j
Note that unlike the generalized width defined in (4.10), the width does not depend on opt
. Finally,
n
for a vector v ∈ R and a subset I ⊆ [n], we use v|I = (vi )i∈I to denote the vector which keeps only
the coordinates in I.

The following is the main result of this section: The first two parts say that with good probability a
solution to the original LP translates to a solution to the sampled LP with value not much lower than
the expected value. This is via a straightforward application of Bernstein’s inequality. The latter two
parts show that the optimal value for the sampled LP is not much higher either, both in expectation
and with high probability. These parts use (ε, σ)-stability to control the variance of the (dual of the)
sampled LP. Since the proof is slightly technical we defer it to Appendix C.
Lemma 5.5 (Sampled LP Lemma). For ε, δ ∈ (0, 1) and ρ ≥ 1, consider a PCMC LP L with width
ε2
2
t are at most ρ · opt(L)(
and such that all item values πi,j
at least 32 log(m/δ)
32 log(m/δ) ). Let s ≥ ε n and
ε2
p
let I be a s-subset of [n]. Then for ε′ = ε ns we have the following guarantees for the random LP L:
(a) If x̄ is feasible for L, then (1 −

ε′
2 ) · x̄|I
I

is feasible for LI (1 − ε′ ) with probability at least 1 − 2δ.

(b) With probability at least 1 − 4δ, opt(L (1 − ε′ )) ≥ (1 −

ρε′
2 )

·

s
n

opt(L).

Moreover, if L is (ε, σ)-stable, then the following upper bounds hold:
(c) With probability at least 1 − 2δ, opt(LI (1 − ε′ )) ≤ (1 + 2σε′ + ρε′ ) ·


(d) E opt(LI (1 − ε′ )) ≤ (1 + σε′ ) · ns opt(L).

6

s
n

opt(L)

Solving packing/covering LPs with unknown OPT

We can now combine the algorithm from §4 that needs estimates on opt with the algorithm from §5 that
estimates of opt to get almost optimal ε-feasible online solutions to packing-covering multiple-choice
LPs. We are going to use the same doubling strategy introduced in [AWY14] (and used in [MR12])
in the packing-only case. We give the details since covering constraints introduce technicalities that
preclude applying previous results directly. To simplify notation we use the shorthand L≤k to denote
the sampled LP L{1,...,k} , and similarly L>k := L{k+1,...,n} .
19

6.1

One-time learning OPT

The one-time learning (OTL) algorithm below uses the first half of the instance to estimate the value
of opt and then runs the algorithm LPviaLB on the second half.
Algorithm 3 . One-time learning (OTL) algorithm
Input: Reals ε, δ, σ > 0, number n of items, and right-hand sides b and d.
√
(Estimation phase) Let ε′ = ε 2. For time steps 1, . . . , n2 observe blocks (π 1 , A1 , C1 ),
′
≤n
c := 1−2ε
2 (1 − ε′ )). Output x̄t = 0
. . . , (π n/2 , An/2 , Cn/2 ) and compute the estimate opt
1+3σ · opt(L
for all these time steps.
(Optimization phase) For the remaining time steps n2 + 1, . . . , n, run algorithm LPviaLB with
n
c over the scaled remaining LP L> 2 (1 − ε′ ), outputting the solution
the computed estimate opt
x̄n/2+1 , . . . , x̄n returned by LPviaLB.

The following theorem shows that the solution computed is almost feasible and almost optimal for
n
the second half L> 2 of the instance.
Theorem 6.1. Consider a feasible PCMC LP L. Consider ε > 0 at most a sufficiently small constant,
and δ ∈ (0, ε], and assume that the generalized width of L is at least 32 log(m/δ)
. Also assume that L
ε2
1
].
Then
with
probability
at
least
1
−
13δ,
the
algorithm
OTL returns
is (ε, σ)-stable for σ ∈ [1, 20√
2ε
n

an online solution {x̄t }nt=n/2 that is (c4 ε)-feasible for L> 2 and has value
n
X
t=1

n

π t x̄t ≥ (1 − c5 σε) opt L> 2 1 −

√ 
2ε

for constants c4 , c5 .
c defined,
The proof is conceptually direct: it uses Lemma 5.5 to assert the quality of the estimate opt
t
n
and then employs Theorem 4.1 to obtain guarantees on the computed solution {x̄ }t=n/2+1 . The
details are in Appendix D.
Observe that this theorem does not give an almost feasible solution for the entire LP L, only for
L>n/2 . Also it only achieves value ≈ opt(L>n/2 ) ≈ 21 opt(L). To do better we use the doubling
strategy to dynamically learn opt.

6.2

Dynamically learning OPT

Our final algorithm for PCMC LPs is called dynamic learning algorithm (DLA). The idea of this
algorithm is to use the blocks seen in the first εn time steps to obtain an estimate of opt(L) and
feed it to LPviaLB to compute solutions for time steps εn + 1, . . . , εn. Then it uses the blocks seen
up to this time (i.e. the first 2εn blocks) to obtain a better estimate of opt(L) and again feeds it to
LPviaLB, obtaining solutions for time steps 2εn + 1, . . . , 4εn; the algorithm proceeds in this doubling
fashion until the end. Equivalently, we can define it as repeatedly using algorithm OTL from the
previous section:

20

Algorithm 4 . Dynamic learning algorithm (DLA)
Input: Reals ε, δ, σ > 0, number n of items, and right-hand sides b and d.
p
p
For i = 0, . . . , log ε−1 , let Si := {1, . . . , 2i εn} and let εi = ε n/|Si | = ε/2i

for i = 1, . . . , log ε−1 do
(Phase i) Run the algorithm OTL with parameters εi , δ, σ over the instanceLSi , namely the
first 2i εn times steps of instance L, and let 0, . . . , 0, x̄|Si−1 |+1 , x̄|Si−1 |+2 , . . . , x̄|Si | be the returned
solution
end for

Output 0, . . . , 0, x̄|S0 |+1 , x̄|S0 |+2 , . . . , x̄n , namely the “union” of the solutions computed above

Algorithm DLA finally delivered the promised guarantees for PCMC LPs: for stable LPs with not too
small generalized width, it obtains an O(ε)-feasible (1 − O(ε))-optimal solution with high probability.
(This corresponds to Theorem 1.2 in the introduction.)
Theorem 6.2. Consider a feasible PCMC LP L. Consider ε > 0 at most a sufficiently small constant
. Also assume that
ε0 , and δ ∈ (0, ε], and assume that the generalized width of L is at least 32 log(m/δ)
ε2
1
L is (ε, σ)-stable for σ ∈ [1, 20√
].
Then
with
probability
at
least
1
−
23δ
log(1/ε),
the
algorithm DLA
2ε
t
returns an online solution {x̄ }t that is (c6 ε)-feasible for L and has value
n
X
t=1

π t x̄t ≥ (1 − c7 σε) opt(L)

for constants c6 , c7 .
The main element for proving this theorem is to obtain guarantees for the solutions returned by OTL
in each phase i of the algorithm DLA. This is done by showing that with good probability the random
instance LSi (1−εi ) is (εi , O(σ))-stable (using the bounds from Lemma 5.5) so we can employ Theorem
6.1 to obtain guarantees for OTL; a full proof is presented in Appendix E.

Lemma 6.3. Let x̄(i) = 0, . . . , 0, x̄|Si−1 |+1 , x̄|Si−1 |+2 , . . . , x̄|Si | be the partial solution computed in
phase i of algorithm DLA. Then with probability at least 1 − 19δ, x̄(i) is ((c4 + 1)εi )-feasible for
√
P|Si | t
LSi \Si−1 and has value at least t=1
π x̄(i)t ≥ (1 − 7c5 σεi ) opt(LSi \Si−1 (1 − 2εi )).
We now use this lemma on every phase of DLA to obtain the proof of Theorem 6.2.

Proof of Theorem 6.2. Let E be the event that for all i = 1, . . . , log( 1ε ), the bound from Lemma 6.3
holds and
opt(LSi \Si−1 (1 −

√

 |Si \ Si−1 |

2εi )) ≥ 1 − εi ·
opt(L) = 1 − εi ε 2i−1 opt(L)
n

also holds. Using Lemmas 5.5 and 6.3 and taking a union bound over i = 1, . . . , log( 1ε ), we get that
event E holds with probability at least 1 − 23δ log( 1ε ) (indeed we can apply Lemma 5.5 since εi ≥ ε
implies that the generalized width of LSi \Si−1 is at least 32 log(m/δ)
, and ε2i ≤ ε implies
≥ 32 log(m/δ)
ε2
ε2

|Si \ Si−1 | ≥ ε2i n). In addition, notice that the definition of the εi ’s gives
log(1/ε)

X
i=1

i−1

εi 2

i

√ √ log(1/ε)+1
√ log(1/ε)
1
ε X √ i
ε
2
=√ √
≤ 2.
· √
2 ≤
=
2
2
2
−
1
2
(
2
−
1)
i=1
21

(6.14)

Then using the guarantees from Lemma 6.3, it is easy to see that under the event E the solution {x̄t }t
output by DLA satisfies the covering constraints within a factor of (1 − ε(1 + 2c4 )):


log(1/ε)
log(1/ε)
n
X
X
X
|Si \ Si−1 |
(1 − (c4 + 1)εi )
Ct xt ≥ d ·
εi 2i−1  ≥ d · (1 − ε(3 + 2c4 )).
= d · 1 − ε − ε(c4 + 1)
n
t=1

i=1

i=1

Similar, and even simpler, calculations show that the solution {x̄t }t also satisfies the packing conP|Si |
x̄t ≥
straints under E, and thus is (3+2c4 )-feasible for L. Finally, since under E we have that t=|S
i−1 |+1
(1 − 7c5 σεi )(1 − εi ) ε2i−1 opt(L), adding over all phases i gives
n
X
t=1

log(1/ε)
t t

π x̄ ≥ ε opt(L)

X
i=1



i−1

(1 − 7c5 σεi ) 1 − εi 2

≥ opt(L) (1 − c7 εσ)

≥ ε opt(L)

log(1/ε)

X
i=1

1−


c7
σεi 2i−1
2

for some constant c7 , where in the second inequality we also used the fact σ ≥ 1. This concludes the
proof of the theorem.

7

Solving packing LPs with no assumption on item values

Finally, we turn to removing all assumptions about the magnitudes of the profits πt . To achieve this,
we consider packing-only LPs (PLPs) of the following form:
Pn
max
(PLP)
t=1 πt xt
st Ax ≤ b

x ∈ [0, 1]n ,

for non-negative π, A, and b. Observe the absence of covering constraints, and also of multiple-choice
constraints—each load matrix At is just a column vector, so at each step one more column of the
matrix A is revealed to us. In this setting we now find a solution of value (1 − O(ε)) opt, without any
assumptions about the magnitudes of the values πt .
The presence of items with large value πt compared to opt rules out using algorithms DLA or
LPviaLB directly, since we may violate the required generalized width bounds. We would like to
show a threshold value such that items having values higher than the threshold can be directly added
to our solution (i.e., we can set xt = 1 for these items) such that: (i) the total value of these items
plus the LP on the remaining items is still a (1 − ε)-approximation to the original optimal value (i.e.,
we do not lose much value by adding these items); (ii) the individual values of items in the remaining

ε2
· opt, and (iii) the right-hand side of the remaining LP is still large. Properties
LP are O log(m/δ)

so we can
(ii) and (iii) would guarantee that the generalized width of the remaining LP is Ω log(m/δ)
2
ε
employ the algorithm LPviaLB, for example, on the remaining LP.
Indeed, our algorithm proceeds essentially using this approach. The difference is that we can only
ε2
show a threshold such that the remaining items have values smaller than O log(m/δ)
times the original
LP value, not the new LP value. Thus, having taken high-value items into our solution, the value of
the new “skimmed-off” LP may have fallen drastically, so we may get no bounds on the generalized
width. Yet, the value of the remaining LP being small implies the already-picked items have a lot of
value, which means even a poor approximation on the remaining LP suffices. This approach introduces
additional complications that are handled in the remainder of §7.
Let us establish some notation. Denote the set of PLPs with n columns by PLPn , and the right-hand
side vector b of a PLP L by rhs(L). Also, recall that the width (defined in (5.13)) of a packing LP is
22

, and will want the width of all LPs to be Ω(B). By scaling, we
maxi,j { abiji }. Define B := log((m+1)/δ)
ε2
will assume that entries in each column At lie in [0, 1] and that the right-hand sides bi ’s are at least
the width of the LP.

7.1

Estimating the high-value items

The first piece of the puzzle is to show the existence of a good skimming threshold τ such that blindly
adding to the solution the items with value more than τ satisfies the properties (i)–(iii) above. We
first formally define the “remaining LP” mentioned above.
Definition 7.1 (Skimmed LP). For L ∈ PLPn and a threshold τ ≥ 0, consider the high-value items
H = {t : πt > τ }. The skimmed LP skimτ (L) is then obtained from L by setting
the value of
P to zero
t
all items in H and setting the right-hand side to be rhs(skimτ (L)) := rhs(L) − t∈H A . (I.e., this is
essentially the residual LP if we hard-code xt = 1 for all t with πt > τ .)
The following gives a formal definition of a good skimming threshold (it is useful to think of ∆ =
Θ(opt(L)), which corresponds to the discussion above).
Definition 7.2 (Good Skimming Threshold). A value τ ∈ R is a ∆-good skimming threshold for
L ∈ PLPn if:
P
(S1) opt(skimτ (L)) + t:πt >τ πt ≥ (1 − ε) opt(L),
(S2) rhs(skimτ (L)) ≥ 12 rhs(L), and
(S3) τ ≤ 24·∆
B .
The starting point is the following simple but crucial claim, which gives a “perfect” skimming threshold
τ — one where we do not lose any value by blindly picking items of higher value. It is a generalization
of the “value/weight” rule for solving single knapsack problems, and says that every optimal fractional
solution must pick all the sufficiently high valued items.
Lemma 7.3 (Perfect Threshold). For a feasible PLP L and for every τ ≥
X

opt(skimτ (L)) +

opt(L)
mini bi ,

we have

πt = opt(L).

t:πt >τ

Proof. The dual of L is given by

X
X
D = min
bi p i +
yt |

i∈[m]

p, At

t∈[n]



+ yt ≥ πt ∀t ∈ [n], p, y ≥ 0 ,


where the variable yt is relative to the primal constraint xt ≤ 1.

Let (x∗ , (p∗ , y ∗ )) be an optimal primal-dual pair for L and D. We claim that x∗ selects all items with
πt > kp∗ k1 . To see this, observe that πt > p∗ , At means yt∗ > 0 and hence x∗t = 1 by complementary
slackness. But since the entries of At are upper bounded by 1, we have p∗ , At ≤ kp∗ k1 . Thus,
πt > kp∗ k1 ≥ p∗ , At implies x∗t = 1, giving the claim.
This means that


opt skimkp∗ k1 (L) +

X

πt = opt(L).

t:πt >kp∗ k1

opt(L)
. This is easy from strong duality: opt(L) = opt(D) ≥
Now
to show that kp∗ k1 ≤ min
i bi
P it suffices
∗
∗
i∈[m] bi pi ≥ (mini bi ) · kp k1 , which completes the proof.

23

Lemma ensures

opt(L)
mini bi

satisfies criteria (S1) and (S3) for being a Θ(opt(L))-good skimming threshold

2opt(L)
notice. But if we assume that L has width at least B, the slightly higher threshold τ = 2opt(L)
mini bi ≤
B
satisfies (S2) as well. Indeed, at most B2 items with value more than τ (else picking B2 + 1 of them
would satisfy the constraints of the LP L and give value strictly greater than opt(L)), and thus
rhs(skimτ (L)) ≥ rhs(L) − B2 1 ≥ 12 rhs(L). Therefore, this threshold τ is indeed a “perfect” Θ(opt(L))good skimming threshold for L.

Hence we want to estimate τ in order to pick up the high-value items in an online fashion, i.e., we
seem to need to estimate opt(L) with good probability (in the presence of unboundedly large item
values πt ). And hence we seem to be back at square one. However, recall that this is only if we want
a perfect threshold. By excluding a small number of items with the largest values πt , we now show
how to find a good-enough skimming threshold. To make this precise, for K ∈ N let L<K denote the
LP obtained by zeroing out the values πt of the K highest valued items (without changing the right
hand side).5
First we show that the optimal value of this modified LP L<K can be (over)estimated by using the
n
optimal value of the sampled LP L≤ 4 .

1
Lemma 7.4. For L ∈ PLPn with width at least 16B and ε ≤ 32
, and K = 128εB,


n
Pr opt(L≤ 4 ) ≥ opt(L8<K ) ≥ 1 − 6δ.

Proof. Let M be the value of the K th largest value of π. We use Lemma 5.5(b) on L<K (using the
fact that all item values in L<K are at most M and that since there are no covering constraints
L<K (1 − ε′ ) = L<K ) to get with probability at least 1 − 4δ
n

n

opt(L≤ 4 ) ≥ opt((L<K )≤ 4 ) ≥

opt(L<K ) KM
opt(L<K )
− 8M Bε =
−
.
4
4
16

(7.15)

n

Moreover, we claim that opt(L≤ 4 ) ≥ (KM )/16 with probability at least 1 − 2δ. For that, let T be
b that sets for all t ∈ [n/4],
the indices of the top K = 128εB values of π and consider the solution x
≤n
1
bt = 1 if t ∈ T and x
bt = 0 otherwise. We know that rhs(L 4 ) = 4 rhs(L) ≥ 4B 1; moreover, this
x
b can (at most) pick all K = 128εB ≤ 4B elements of T (since ε ≤ 1/32), so x
b is feasible
solution x
≤n
4
b is E[|T ∩ [n/4]|] = K/4, and the Bernstein’s
for L . The expected number of items picked by x
δ
bt = 1
. Each item with x
inequality Corollary 2.4 implies Pr(|T ∩ [n/4]| < K/16) ≤ 2 exp(−εB) ≤ 2 m
has value at least M , so with probability at least 1 − 2δ
n

opt(L≤ 4 ) ≥

X

t∈T∩[n/4]

bt ≥
πt x

KM
.
16

(7.16)

Taking a union bound we have that with probability at least 1 − 6δ inequalities (7.15) and (7.16) hold
simultaneously. When this holds we can take the average of these inequalities, and so with probability
n
at least 1 − 6δ opt(L≤ 4 ) ≥ opt(L8 <K ) , which concludes the proof.
Next, the optimal value of the modified LP L<K can be used to obtain a good skimming threshold.
Lemma 7.5. Consider a feasible PLP L with width at least B. Suppose ε ≤ 13 and K is at most
<K )
is a τ24B -good skimming threshold for L.
times the width of L. Then any τ ≥ 3opt(L
B
5

We assume items have distinct values for simplicity; one can break ties consistently and get the same result.

24

ε
2

Proof.
We first show that condition (1) of a good skimming threshold holds, namely opt(skimτ (L)) +
P
t:πt >τ πt ≥ (1 − ε) opt(L). Let H = {t : πt > τ } be the high-value items, and let T ⊆ [n] denote the
index set of the K items with largest value πt (the “top-value” items).
Since the width of L<K is the same as that of L (which is at least B), we have that τ ≥
and thus from Lemma 7.3 we have
X
opt(skimτ (L<K )) +
πt = opt(L<k ).

3opt(L<K )
mini rhs(L<K )i

t∈T,t∈H
/

Adding all the top valued items T to both sides gives
X
X
X
opt(skimτ (L<K )) +
πt +
πt = opt(L<k ) +
πt ≥ opt(L).

(7.17)

To connect the left-hand side of this expression with opt(skimτ (L)) we claim that
X
πt .
opt(skimτ (L)) ≥ (1 − ε) opt(skimτ (L<K )) +

(7.18)

t∈H

t∈T,t∈H
/

t∈T

t∈T,t∈H
/

To see this, consider an optimal solution x∗ for skimτ (L<K ) (which only accrues value from items in
H), and construct the vector x
b by setting x
bt = (1− ε)x∗t for t ∈ H ∩ T , x
bt = 1 for t ∈ H ∩ T , and x
bt = 0
otherwise. Notice that x
b is feasible for skimτ (L): First, rhs(skimτ (L)) ≥ rhs(skimτ (L<K )) − K 1, since
only the K items in T can be additionally skimmed in L compared to L<k . Thus, the usage of the
solution x
b is
X
X
At x
bt ≤ (1 − ε)
At x∗t + K 1 ≤ (1 − ε) rhs(skimτ (L<K )) + K 1
t:t≤τ

t:t≤τ

≤ (1 − ε) rhs(skimτ (L)) + 2K 1 ≤ rhs(skimτ (L)),

where the inequality 2K 1 ≤ ε rhs(skimτ (L)) used in the last step follows from the fact that rhs(skimτ (L)) ≥
1
2K
b is
2 rhs(L) (condition (2) proved below) and rhs(L) ≥ ε 1 (assumption). Therefore, the solution x
feasible for skimτ (L). Since it has value equal to the right-hand side of inequality (7.18), it proves the
validity of this inequality.
Putting
inequalities (7.17) and 7.18 together and using the non-negativity of the πt ’s gives opt(skimτ (L))+
P
t:πt >τ πt ≥ (1 − ε)opt(L), and thus condition (1) holds.

Condition (3) in the definition of good skimming threshold trivially holds, so to conclude the proof
we show condition (2), namely rhs(skimτ (L)) ≥ 12 rhs(L). As argued before, there are at most B3 items
in H ∩ T , otherwise we could pick B3 + 1 items in this set to obtain a feasible solution for L<K (since
At ≤ 1 for all t) with value more than opt(L<K ), a contradiction. Therefore, the right-hand side of
skimτ (L) equals


X

B
t
rhs(L) −
A ≥ rhs(L) − |H ∩ T̄ | + |T | · 1 ≥ rhs(L) −
+ K · 1.
3
t∈H

1
ε
Since the width of L is at least B and at least 2K
ε , this inequality gives skimτ (L) ≥ rhs(L)(1 − 3 − 2 ) ≥
1
1
2 rhs(L), where the last inequality uses ε ≤ 3 . This concludes the proof of the lemma.

Therefore, putting Lemmas 7.4 and 7.5 together, we get that with probability at least 1 − 6δ the
≤n
4 ) is an opt(L)-good skimming threshold for L; in fact, as will be more useful,
value τ := 24
B opt(L
n
n
it is an opt(L)-good skimming threshold for L> 4 and L> 2 (this simply uses the additional fact that
n
n
opt(L<K ) is at least opt((L> 4 )<K ) and opt((L> 2 )<K )).
Lemma 7.6 (Finding Good Skimming Threshold). Consider L ∈ PLPn with width at least 512B,
≤n
1
>n
4 ). Then τ is an opt(L)-good skimming threshold for L 4
, and δ > 0. Define τ := 24
ε ≤ 32
B opt(L
n
and L> 2 with probability at least 1 − 6δ.
25

7.2

Estimating opt and right-hand side of a skimmed LP

In order to solve the skimmed LP skimτ (L) using the algorithm LPviaLB, we need to obtain estimates
for the optimal value of this LP, as well as its right-hand side (which is now random). Crucially, since
skimτ (L) has only “small-value” items (and we assume L has large width), these quantities can be
n
estimated by looking at that sampled LP L≤ 3 just like we did in §5 for packing-covering LPs; a full
proof is deferred to Appendix F.
Lemma 7.7. Let ε > 0 be at most a sufficiently small constant. Given L ∈ PLPn with width at least
40B, let τ be an opt(L)-good skimming threshold for L. Then with probability at least 1 − 4δ,
n 
n 
1
rhs skimτ (L≤ 3 ) ∈ (1 ± 3ε) rhs skimτ (L> 3 )
2

and with probability at least 1 − 16δ,

n 
n 
1
opt skimτ (L≤ 3 ) ∈ (1 ± 3ε) opt skimτ (L> 2 ) ± 33εBτ.
2

Next, we show we can replace this fixed good skimming threshold τ by the estimated one τ given by
Lemma 7.6. For that, we condition that the set of items that appear on times 1, . . . , n4 is such that τ
n
n
is a opt(L)-good skimming threshold for L> 4 , and then apply Lemma 7.7 to the LP L> 4 ; taking an
average over all such conditionings then gives the following.
Corollary 7.8. Let ε > 0 be at most a sufficiently small constant, and let L ∈ PLPn have width at
≤n
4 ) as in Lemma 7.6. Then with probability at least 1 − 14δ all of
least 512B. Define τ := 24
B opt(L
the following hold simultaneously:
n

τ is a opt(L)-good skimming threshold for L> 2
n n 
n 
1
rhs skimτ (L( 4 , 2 ] ) ∈ (1 ± 3ε) rhs skimτ (L> 2 )
2
n 
n n 
1
opt skimτ (L( 4 , 2 ] ) ∈ (1 ± 3ε) opt skimτ (L> 2 ) ± 33εBτ .
2
Finally, since we only have an estimate of the right-hand side of skimτ (L), we need to ensure that
the algorithm LPviaLB can handle this. Thankfully this is the case: The following corollary of
Theorem 4.1 follows directly from the fact that if we reduce the right-hand side of a PLP by a factor
of (1 − 6ε), the optimal value reduces by at most a factor of (1 − 6ε) (since we can scale an original
optimal solution by (1 − 6ε) and obtain at least this much value).
Corollary 7.9 (of Theorem 4.1). Consider a feasible PLP L. Consider ε > 0 at most a sufficiently
.
small constant ε0 , and δ ∈ (0, ε], and assume that the generalized width of L is at least 2 log((1+m)/δ)
ε2
opt
b
c ∈ [ 2 , opt] and an approximation b ∈
Suppose the algorithm LPviaLB is given an estimate opt
[(1 − 6ε)b, b] to the packing right-hand side. Then LPviaLB
an online solution {xt }t that with
P tfinds
c
probability at least 1 − δ is feasible for L and has value t π xt ≥ (1 − c3 ε − 6ε) opt.

7.3

Modified one-time learning algorithm

Now we present the modified one-time learning (mOTL) algorithm, which at a high-level does the
n
natural thing: 1) uses the first n2 time steps (i.e. L≤ 2 ) to estimate the required parameters (good
n
skimming threshold τ , optimal value and right-hand side of skimτ (L> 2 )); 2) in time steps > n2 , picks
n
all high-value items πt > τ and feeds the remaining LP skimτ (L 2 ) to algorithm LPviaLB. Here is
26

a formal description of the algorithm mOTL, which has one small additional feature to simplify its
n
analysis: we truncate the solution obtained for skimτ (L> 2 ) to ensure it is always feasible for estimated
b
right-hand side b.
Algorithm 5 . Modified one-time learning (mOTL) algorithm
Input: Reals ε, δ, σ > 0, number n of items, and right-hand side b.

(Estimation) For time steps 1, . . . , n2 observe blocks (π 1 , A1 , C1 ), . . . , (π n/2 , An/2 , Cn/2 ) and compute the estimates
n
24
opt(L≤ 4 )
B
h
i
n n
b := 2
opt(skimτ (L( 4 , 2 ] )) − 33εBτ
O
1 + 3ε
b := 2 rhs(skimτ (L( n4 , n2 ] ))
b
1 + 3ε

τ :=

n

(estimate of opt(skimτ (L> 2 )))
n

(estimate of rhs(skimτ (L> 2 )))

n q
o
n
b . Run algorithm
(Approximate solution for skimτ (L> 2 )) Define ε′ = ε max 1, 2Bτ /O
b and parameters ε′ , δ, over the skimmed remaining
b and b,
LPviaLB with the computed estimates O
>n
LP skimτ (L 2 ), letting x̃ n2 +1 , . . . , x̃n be the returned solution. Let tlast be the largest index such
P
b
that tlastn At (1 − 6ε)x̃t ≤ b.
t= 2 +1

(Output above solution + high-value items, truncated) Let H = {t > n2 : πt > τ } be the
high-value items within the time periods n2 + 1, . . . , n. Output the solution x̄ n2 +1 , . . . , x̄n defined by

if t ∈ H
 1


(1 − 6ε) x̃t if t ∈
/ H, t ∈ n2 + 1, tlast
x̄t =

0
if t ∈
/ H, t > tlast .

The next theorem states the guarantees that we have for algorithm mOTL.
Theorem 7.10. Consider ε > 0 smaller than a sufficiently small constant, and δ ∈ (0, ε]. Consider
a feasible LP L ∈ PLPn with width at least 512B. Then with probability at least 1 − 15δ, the algorithm
n
mOTL returns a solution x̄ n2 +1 , . . . , x̄n that is feasible for the LP L> 2 and has value at least
n

opt(L> 2 ) − c6 ε opt(L)
for some constant c6 .
Here is some intuition for the proof. Recall that the main point of the skimming operation is to try to
n
control the generalized width of the skimmed LP skimτ (L> 2 ); let us see what we have accomplished in
this direction. Suppose (via Corollary 7.8) that the estimate τ computed is an opt(L)-good skimming
n
n
threshold for L> 2 . Property (2) of a good skimming threshold implies that the width of skimτ (L> 2 )

(if we assume that the width of L is Ω(B)). However, for the item
is the desired Ω(B) = Ω log(m/δ)
ε2
n
n
values, notice that the ratio of opt(skimτ (L> 2 )) divided by the largest item value in skimτ (L> 2 ) is at
n
n
n
>2
>
 opt(skimτ (L> 2 ))
τ (L 2 ))
least opt(skimττ (L )) = Ω(B) opt(skim
= Ω log(m/δ)
. If the skimmed LP has large
opt(L)
opt(L)
ε2

optimal value (namely Ω(opt(L))), then the skimmed LP has generalized width Ω log(m/δ)
and we
2
ε
can guarantee that LPviaLB returns an (1 − O(ε))-approximation for it; since τ is a good skimming
27

threshold, this (1 − O(ε))-approximation together with the high-value items guarantee that algorithm
n
mOTL obtains value ≈ opt(L> 2 ).

However, if the skimmed LP has a small optimal value, the generalized width is not within the desired
range and we lose the guarantee for algorithm LPviaLB. But the generalized width of
Ω log(m/δ)
ε2
r
n
log(m/δ) 
opt(L)
>2
′′
for ε = Θ(ε)
, and thus we can get a
skimτ (L ) is always in the range Ω (ε′′ )2
>n
O(ε′′ ))-approximation

opt(skimτ (L
the ε′ used in

ε′′

2

))

(1 −
(notice the similarity of
and
the algorithm). Moreover,
n
when ε′′ ≫ ε this means that the high-value items of L> 2 have a large contribution to the optimal
value opt(L); since these items are picked by our algorithm, our solution should again have large
overall value.
n

Proof of Theorem 7.10. Let σ be a realization of L≤ 2 where the guarantees from Corollary 7.8 hold
(the probability of obtaining such realization is at least 1−14δ). In this scenario, the solution x̄ output
n
b ≤ rhs(skimτ (L> n2 )) and thus the choice of stopping time
by mOTL is feasible for L> 2 : we have b
n
tlast makes ((1 − 6ε)x̃ n2 +1 , . . . , (1 − 6ε)x̃tlast , 0, . . . , 0) feasible for rhs(skimτ (L> 2 )); the definition of
skimmed LP then guarantees that the output solution x̄ (which consists of these x̃t ’s plus high-value
n
items) fits the budgets of L> 2 , thus we get feasibility.
As for the value val of the solution under scenario σ, we have two different cases depending on the
n
suffices).
value of opt(skimτ (L> 2 )); let C be a sufficiently large constant (C = 132×48×2
1−9ε
n

n

Case 1: opt(skimτ (L> 2 )) < εCopt(L). Since τ is a opt(L)-good skimming threshold for L> 2 , the
high-value items already give value
X
n
n
n
πt ≥ (1 − ε)opt(L> 2 ) − opt(skimτ (L> 2 )) ≥ opt(L> 2 ) − ε(C + 1)opt(L),
t∈H

n

and thus val ≥ opt(L> 2 ) − ε(C + 1)opt(L).
n

Case 2: opt(skimτ (L> 2 )) ≥ εCopt(L). We claim that the requirements of Corollary 7.9 are fulfilled
(with approximation parameter ε′ ), so we can apply it to obtain guarantees for the solution x̃ for
n
skimτ (L> 2 ); most conditions can be easily checked, we argue about theqless trivial ones. First, since


b ≤ opt skimτ (L> n2 ) ; then ε′ ≥ ε 2Bτ /opt skimτ (L> n2 ) and
Corollary 7.8 holds for scenario σ, O
n

reorganizing this expression gives that the LP skimτ (L> 2 ) has generalized width at least
b is at least
Second, the estimate O

n

2 log((m+1)/δ)
.
(ε′ )2

opt(skimτ (L> 2 ))
:
2

b ≥ 1 − 3ε opt(skimτ (L> n2 )) − O(εBτ ) ≥ 1 − 3ε opt(skimτ (L> n2 )) − O(εopt(L)) ≥ 1 opt(skimτ (L> n2 )),
O
1 + 3ε
1 + 3ε
2
n

where the last inequality uses the assumption that opt(skimτ (L> 2 )) ≥ εCopt(L) for a sufficiently
large C and that ε is at most a sufficiently small constant. Finally, using this fact plus the bound
τ ≤ 24opt(L)
, we have ε′ ≤ ε0 :
B
( s
 q

b ≤ ε max 1,
ε′ = ε max 1, 2Bτ /O

4 × 24opt(L)
n
opt(skimτ (L> 2 ))

)


√
≤ max ε, O( ε) ≤ ε0 ,

where the second inequality follows from our assumption on Case 2, and the last inequality follows
from the fact ε is a sufficiently small constant.

28

n

Thus, we can apply Corollary 7.9 to L> 2 and get that, conditioned on σ, with probability at least
n
1 − δ the solution x̃ n2 +1 , . . . , x̃n is feasible for L> 2 and has value
o
n p
X
b ≥O
b − O(ε) opt(L)
b ≥O
b − ε(c3 + 6) max O,
b
2Bτ O
πt x̃t ≥ (1 − c3 ε′ − 6ε′ ) O
:t∈H
/
t> n
2

n

≥ opt(skimτ (L> 2 )) − O(ε) opt(L),

b ≤ opt(L) (a consequence of an upper bound on O
b proved
where the second inequality because O
above) and the fact τ is opt(L)-good skimming threshold, and the last inequality uses the above
b Also, the feasibility of this solution also implies (together with the conditioning
upper bound on O.
on σ) that
X
n
1 b
b,
At x̃t ≤ rhs(skimτ (L> 2 )) ≤
1
−
6ε
n
t> 2

and hence the stopping time tlast is set to be equal to n. Thus, the value val obtained by the algorithm
uses the full solution x̃ n2 +1 , . . . , x̃n , and again using the fact τ is a good skimming threshold we get
X
X
n
val =
πt x̃t +
πt ≥ opt(L> 2 ) − O(ε) opt(L).
t> n
:t∈H
/
2

t∈H

Since this all happened with probability at least 1 − δ conditioned on a scenario σ where Corollary
7.8 holds, taking an expectation over all such scenarios gives that the above guarantee for val holds
with overall probability at least 1 − 15δ. This concludes the proof of the theorem.

7.4

Final algorithm: Modified Dynamic Learning

The final algorithm to solve packing LPs, modified dynamic learning (mDLA), is exactly as the
dynamic learning algorithm from §6.2 with the only change that it uses the modified One-time learning
algorithm mOTL instead of OTL.
The following theorem shows that this algorithm mDLA has the desired guarantees.
Theorem 7.11. Consider ε > 0 smaller than a sufficiently small constant, and δ ∈ (0, ε]. Consider
. Then there is an event E that holds with
a feasible LP L ∈ PLPn with width at least 1024 log((m+1)/δ)
ε2
probability at least 1 − c7 δ log 1ε such that under E the solution {x̄t }t returned by algorithm mDLA
is feasible for the LP L and has expected value conditioned on E at least (1 − c8 δ log ε−1 ) opt(L), for
some constants c7 , c8 . In particular, the truncated solution x̄1 , x̄2 , . . . , x̄t′last , 0, . . . , 0, where t′last is the
largest index that makes this solution feasible for L, has expected value at least (1 − c9 δ log e−1 ) opt(L)
for some constant c9 .
The proof of this theorem is similar to the proof of the guarantee for the algorithm DLA and the
changes required —which arise from the fact that we now do not have good bounds on the ratios
πt /opt(L)— are indicated in Appendix G.

References
[ABFP13] Yossi Azar, Umang Bhaskar, Lisa Fleischer, and Debmalya Panigrahi. Online mixed packing and
covering. In SODA, pages 85–100, 2013.
[ABH11]

Jacob Abernethy, Peter L. Bartlett, and Elad Hazan.
Blackwell approachability and
no-regret learning are equivalent.
In COLT 2011 - The 24th Annual Conference on
Learning Theory, June 9-11, 2011, Budapest, Hungary, pages 27–46, 2011.
URL:
http://www.jmlr.org/proceedings/papers/v19/abernethy11b/abernethy11b.pdf.

29

[AD14]

Shipra Agrawal and Nikhil R. Devanur. Bandits with concave rewards and convex knapsacks. In
Proceedings of the Fifteenth ACM Conference on Economics and Computation, EC ’14, pages 989–
1006, New York, NY, USA, 2014. ACM. URL: http://doi.acm.org/10.1145/2600057.2602844,
doi:10.1145/2600057.2602844.

[AD15]

Shipra Agrawal and Nikhil R. Devanur. Fast algorithms for online stochastic convex programming. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete
Algorithms, pages 1405–1424, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.93,
doi:10.1137/1.9781611973730.93.

[AHK12]

Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method:
a meta-algorithm and applications.
Theory of Computing, 8(6):121–164, 2012.
URL:
http://www.theoryofcomputing.org/articles/v008a006, doi:10.4086/toc.2012.v008a006.

[AWY14]

Shipra
Agrawal,
Zizhuo
Wang,
and
Yinyu
Ye.
A
dynamic
nearoptimal
algorithm
for
online
linear
programming.
Operations
Research,
62(4):876–890,
2014.
URL:
http://dx.doi.org/10.1287/opre.2014.1289,
arXiv:http://dx.doi.org/10.1287/opre.2014.1289, doi:10.1287/opre.2014.1289.

[BIK07]

Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online
mechanisms. In SODA ’07, pages 434–443, 2007.

[BIKK07] Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. A knapsack secretary
problem with applications. In APPROX-RANDOM, pages 16–28, 2007.
[BIKK08] Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. Online auctions and
generalized secretary problems. SIGecom Exchanges, 7(2), 2008.
[BN09]

Niv Buchbinder and Joseph Naor. The design of competitive online algorithms via a primal-dual
approach. Foundations and Trends in Theoretical Computer Science, 3(2-3):93–263, 2009.

[CBL06]

Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cambridge University
Press, 2006.

[CHW12] Kenneth L. Clarkson, Elad Hazan, and David P. Woodruff. Sublinear optimization for machine
learning. J. ACM, 59(5):23:1–23:49, 2012.
[DF80]

P. Diaconis and D. Freedman. Finite exchangeable sequences. The Annals of Probability, 8(4):745–
764, 08 1980. URL: http://dx.doi.org/10.1214/aop/1176994663.

[DH09]

Nikhil R. Devenur and Thomas P. Hayes. The adwords problem: online keyword matching with
budgeted bidders under random permutations. In John Chuang, Lance Fortnow, and Pearl Pu,
editors, ACM Conference on Electronic Commerce, pages 71–78. ACM, 2009.

[DJSW11] Nikhil R. Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A. Wilkens. Near optimal
online algorithms and fast approximation algorithms for resource allocation problems. In Yoav
Shoham, Yan Chen, and Tim Roughgarden, editors, ACM Conference on Electronic Commerce,
pages 29–38. ACM, 2011.
[Dyn63]

E. B. Dynkin. The optimum choice of the instant for stopping a Markov process. Soviet Math. Dokl,
4, 1963.

[ESF14]

Reza Eghbali, Jon Swenson, and Maryam Fazel. Exponentiated subgradient algorithm for online optimization under the random permutation model. CoRR, abs/1410.7171, 2014. URL:
http://arxiv.org/abs/1410.7171.

[FHK+ 10] Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S. Mirrokni, and Clifford Stein. Online
stochastic packing applied to display ad allocation. In Mark de Berg and Ulrich Meyer, editors,
ESA (1), volume 6346 of Lecture Notes in Computer Science, pages 182–194. Springer, 2010.
[Fre75]

David A. Freedman. On tail probabilities for martingales. Annals of Probability, 3:100–118, 1975.
doi:10.1214/aop/1176996452.

30

[GK07]

Naveen Garg and Jochen Könemann. Faster and simpler algorithms for multicommodity flow and
other fractional packing problems. SIAM J. Comput., 37(2):630–652 (electronic), 2007. URL:
http://dx.doi.org/10.1137/S0097539704446232.

[GM08]

Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adWords. In Shang-Hua Teng, editor, SODA, pages 982–991. SIAM, 2008.

[Haz06]

Elad Hazan. Approximate convex optimization by online game playing. CoRR, abs/cs/0610119,
2006. URL: http://arxiv.org/abs/cs/0610119.

[Kha04]

Rohit Khandekar.
Lagrangian Relaxation Based Algorithms for Convex Programming
Problems.
PhD thesis, Indian Institute of Technology Delhi, March 2004.
URL:
http://people.cse.iitd.ac.in/~rohitk/research/thesis.ps.gz.

[Kle05]

Robert Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In
Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, SODA ’05, pages
630–631, Philadelphia, PA, USA, 2005. Society for Industrial and Applied Mathematics. URL:
http://portal.acm.org/citation.cfm?id=1070432.1070519.

[KRTV13] Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. Primal beats dual on
online packing lps in the random-order model. CoRR, abs/1311.2578, 2013. To appear in STOC
2014. URL: http://arxiv.org/abs/1311.2578.
[KV05]

Adam Kalai and Santosh Vempala.
Efficient algorithms for online decision
problems.
Journal of Computer and System Sciences, 71(3):291 – 307, 2005.
URL:
http://www.sciencedirect.com/science/article/pii/S0022000004001394,
doi:http://dx.doi.org/10.1016/j.jcss.2004.10.016.

[MR12]

Marco Molinaro and R. Ravi. Geometry of online packing linear programs. In Automata, languages,
and programming. Part I, volume 7391 of Lecture Notes in Comput. Sci., pages 701–713. Springer,
Heidelberg, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31594-7_59.

[MSVV07] Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. AdWords and generalized online
matching. J. ACM, 54(5):Art. 22, 19, 2007. URL: http://dx.doi.org/10.1145/1284320.1284321.
[Pru98]

Alexander R. Pruss. A maximal inequality for partial sums of finite exchangeable sequences of
random variables. Proceedings of the American Mathematical Society, 126(6):1811–1819, 1998.

[PST95]

Serge A. Plotkin, David B. Shmoys, and Éva Tardos. Fast approximation algorithms for
fractional packing and covering problems. Math. Oper. Res., 20(2):257–301, 1995. URL:
http://dx.doi.org/10.1287/moor.20.2.257.

[Sim89]

R. W. Simpson. Using network flow techniques to find shadow prices for market and seat inventory
control. Technical report, 1989. MIT Flight Transportation Laboratory Memorandum M89-1.

[SS11]

Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends
in Machine Learning, 4(2):107–194, 2011. URL: http://dx.doi.org/10.1561/2200000018,
doi:10.1561/2200000018.

[TR98]

Kalyan Talluri and Garrett Van Ryzin.
An analysis of bid-price controls for network revenue management.
Manage. Sci., 44(11):1577–1593, November 1998.
URL:
http://dx.doi.org/10.1287/mnsc.44.11.1577.

[vdVW96] Aad W. van der Vaart and Jon A. Wellner. Weak convergence and empirical processes. Springer
Series in Statistics. Springer-Verlag, New York, 1996. With applications to statistics. URL:
http://link.springer.com/book/10.1007/978-1-4757-2545-2.
[Wil92]

Elizabeth Louise Williamson. Airline network seat inventory control: methodologies and revenue
impacts. PhD thesis, M.I.T., 1992.

[You01]

Neal E. Young. Sequential and parallel algorithms for mixed packing and covering. In 42nd IEEE
Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), pages 538–546. IEEE
Computer Soc., Los Alamitos, CA, 2001.

31

A

Maximal Bernstein for Sampling Without Replacement

We state the Levy-type maximal inequality for exchangeable random variables obtained in [Pru98].
Theorem A.1 (Theorem 1 of [Pru98], with γ = 2). Let Y1 , Y2 , . . . , Yn be an exchangeable sequence of
random variables taking values in a Banach space. Then for every λ ≥ 0 and every k ≤ n/2, we have
!
!
X
X
λ
Yi >
Yi > λ ≤ 15 Pr
Pr max
.
j≤k
24
i≤j

i≤k

P
Proof of Lemma 2.5. The sequence ( i≤j Xi − jµ)ni=1 is exchangeable, so applying the theorem above
and then Theorem 2.3 we have
!
!


X
X
α
(α/24)2
Xi − jµ > α ≤ 15 Pr
Xi − kµ >
Pr max
≤ 30 exp −
.
j≤k
24
2kσ 2 + (α/24)
i≤j

B

i≤k

Useful Properties of (ε, σ)-Stability

For any ε′ and subset I ⊆ [n], the dual of LI (1 − ε′ ) is

P
k
− ε′ ) nk hβ,

n hα, bi −
 min D
E (1 D
E di + t∈I γt
t , β + γ ≥ πt
D I (1 − ε′ ) :=
At⋆,j , α − C⋆,j
∀j, ∀t ∈ I
t
j


α, β, γ ≥ 0

(B.19)

where again we use At⋆,j to denote the jth column of At , and similarly for C t .

The next essentially follows from the fact that η 7→ opt(L(1 − η)) is concave, and that its derivative
is obtained by looking at an optimal dual solution.
Lemma B.1. Let L be an (ε, σ)-stable packing/covering LP. Then:
1. For every ε′ ≥ ε, L is (ε′ , σ)-stable
2. If (α̃, β̃, γ̃) is an optimal solution for the dual of L(1 − ε), then β̄, d ≤ σ · opt(L).
Proof. Take an optimal solution (α̃, β̃, γ̃) for D(1 − ε). Notice that forP
every η, (ᾱ, β̄, γ̄) is feasible for
D(1 − ε + η) and hence opt(D(1 − ε + η)) ≤ hᾱ, bi − (1 − ε + η) β̄, d + t γ̄ = opt(D(1 − ε)) − η β̄, d .
Using Strong Duality, this gives opt(L(1 − ε)) ≥ opt(L(1 − ε + η)) + η β̄, d .

Setting η = ε, (ε, σ)-stability gives that β̄, d ≤ σ · opt(L), proving Part 2. Also, setting η = ε − ε′
we get opt(L(1 − ε′ )) ≤ opt(L(1 − ε)) + (ε′ − ε)σ · opt(L); again using (ε, σ)-stability of L we get
opt(L(1 − ε′ )) ≤ (1 + ε′ σ)opt(L) for ε′ ≥ ε, concluding the proof of Part 1.

C

Proof of Lemma 5.5

Since the LP has width at least

32 log(m/δ)
,
ε2

by scaling the constraints we assume without loss of

generality that its right-hand sides are all exactly equal to ϑ :=
the left-hand side have entries in [0, 1].

32

32 log(m/δ)
ε2

and the matrices At , C t on

P t t
Part (a). Consider a feasible solution x̄ for L. Since for all i,
t Ai x̄ ≤ ϑ, from Bernstein’s
inequality (Corollary 2.4) we have
!

 2 2

 2


X
s
τ ϑ τϑ
4τ n
log(m/δ)
t t
Ai x̄ ≥ ϑ + τ ϑ ≤ 2 exp − min
Pr
,
, 16τ
;
min
≤ 2 exp −
n
8sϑ/n 2
ε2
s
t∈I

p
setting τ = (ε/2) s/n makes the right-hand side at most 2δ/m (this uses the fact ε ≤ 1 and s ≥ ε2 n).
P
′
Then taking a union bound over all i ∈ [mp ], we have t∈I At x̄t ≤ (1 + ε2 ) ns ϑ1 with probability at
least 1 − 2δ(mp /m).
P
Similarly, fix i ∈ {mp + 1, . . . , m} and let µ = E[ t∈I Cti x̄t ]; then using the fact µ ≥ (s/n)ϑ,
!

 2
 2



X
n
τ µ(n/s)2 τ µ(n/s)
4τ n
log(m/δ)
t t
Ci x̄ ≤ µ − τ µ
≤ 2 exp − min
Pr
,
min
, 16τ
.
≤ 2 exp −
s
8
2
ε2
s
t∈I

p
P
Setting τ = (ε/2) s/n and taking a union bound over all such i’s, we get t∈I Ct x̄t ≥ (1 −
with probability at least 1 − 2δ(mc /m).
′

′

ε′ s
2 )nϑ

1

′

Then, using the fact that (1 − ε2 )(1 + ε2 ) ≤ 1, with probability at least 1 − 2δ we have that (1 − ε2 )x̄|I
′
′
is (1 − ε2 )2 -feasible for LI , and since (1 − ε2 )2 ≥ (1 − ε′ ), Part (a) follows.
Part (b). Let x̄ be an optimal solution for L. Then again by Bernstein’s inequality (Corollary 2.4)
!



X
s
τ 2 opt(L)2 ϑ
τ opt(L)ϑ
t t
π x̄ ≤ opt(L) − τ opt(L) ≤ 2 exp − min
Pr
,
;
n
8ρ(s/n)opt(L)2 2ρ(s/n)opt(L)
t∈I

p
setting τ = (ερ/2) (s/n) makes the right-hand side at most 2δ (this uses the fact ρ ≥ 1).

Then using Part (a), with probability at least 1 − 4δ we have x̄|I feasible for LI (1 − ε′ ) and with value
′
at least (1 − ρε2 ) ns opt(L); this lower bounds the value of opt(LI (1 − ε′ )) and Part (b) follows.
Now for the arguments about the upper bounds. Here we use the (ε, σ)-stability of L. We consider
the (random) dual D I of LI (recall from (B.19) the expression for the dual).
Part (d). Let (ᾱ, β̄, γ̄) be an optimal solution for D(1 − ε). Notice that in every scenario this
solution is feasible for D I (1 − ε′ ), so taking expectations and using Strong Duality E[D I (1 − ε′ )] ≤
s
s
′
n opt(L(1 − ε)) + (ε − ε) n β̄, ϑ1 . Using (ε, σ)-stability of L we have opt(L(1 − ε)) ≤ (1 + σε)opt(L)
and using Lemma B.1 β̄, ϑ1 ≤ σ · opt(L). Since ε′ ≥ ε, this gives E[D I (1 − ε′ )] ≤ ns (1 + σε′ )opt(L),
and Strong Duality then gives Part (e) of the lemma.
Part (c). Again let (ᾱ, β̄, γ̄) be an optimal solution for D(1 − ε). Notice that
P the above
Pargument
s
′
I
′
gives that in every scenario
opt(LP(1−ε )) ≤ n opt(L(1−ε))+(ε −ε)σ·opt(L)+( t∈I γ̄t −E[ t∈I γ̄t ]) ≤
P
s
′ )opt(L) + (
(1
+
σε
γ̄
− E[ t∈I γ̄t ]). Thus it suffices to show that with probability at least 1 − δ,
t
t∈I
n
P
P
′ s (ρ + σ)opt(L).
γ̄
]
+
ε
γ̄
≤
E[
t∈I t
t∈I t
n

For that, we need to control how large
 γ̄ cantbe. By the optimality of γ̄, notice that in each scenario
, or else we could reduce γ̄t and obtain a feasible
and for all t we have γ̄t ≤ maxj πjt , β̄, C⋆,j
P
solution for D(1 − ε) with strictly smaller cost. Again from Lemma B.1 we have i β̄i ≤ σ · opt(L)/ϑ,
and since the entries of Ct are at most 1, we get β̄, Ct⋆,j ≤ σ · opt(L)/ϑ. Using our assumption that
πjt ≤ ρopt(L)/ϑ, we get γ̄t ≤ (σ + ρ)opt(L)/ϑ.
P
Since opt(L(1 − ε)) = opt(L(1 − ε)) =
In addition, we claim thatP
E[ t∈I γ̄t ] ≤ ns (1 + σ)opt(L).
P
hᾱ, ϑ1i − (1 − ε) β̄, ϑ1 + t γ̄t , reorganizing we get t γ̄t ≤ opt(L(1 − ε)) + (1 − ε) β̄, ϑ1 . Using
33

(ε, σ)-stability of L and again the bound from Lemma B.1, this gives
claim follows.

P

t γ̄t

≤ (1 + σ)opt(L), and the


P
Then using Bernstein’s inequality (Corollary 2.4), we get (letting µ = E t∈I γ̄t )
!

 2 2

X
ε τ opt(L)2 ϑ
ετ opt(L)ϑ
Pr
γ̄t ≥ µ + ετ opt(L) ≤ 2 exp − min
,
8µ(ρ + σ)opt(L) 2(ρ + σ)opt(L)
t∈I



log(1/δ)
4τ 2
16τ
≤ 2 exp −
min
,
;
(ρ + σ)
(s/n)(1 + σ) ε
p
setting τ = (ρ + σ) (s/n) makes the right-hand side at most 2δ (this uses the fact that ρ ≥ 1 and
s ≥ ε2 n). Since ε′ ns (ρ + σ) = ετ , this concludes the proof of the lemma.

D

Proof of Theorem 6.1
n

n

c ∈ [ 12 opt(L> 2 (1 − ε′ )), opt(L> 2 (1 − ε′ ))] so we
First we verify that with good probability we have opt
can employ Theorem 4.1 to obtain guarantees for the solution {x̄t }nt=n/2+1 returned by LPviaLB.

Taking a union bound over Parts (b) and (c) of Lemma 5.5 and using the fact that σ ≥ 1, we have
that
#
"

n
opt(L≤ 2 (1 − ε′ ))
ε′
≤
≤ (1 + 3ε′ σ) ≥ 1 − 6δ,
Pr 1 −
1
2
opt(L)
2
n

and the same holds for opt(L> 2 (1 − ε′ )); let E be the event that these bounds hold for both, so we
n
n
have Pr(E) ≥ 1 − 12δ. We can chain the bounds for opt(L≤ 2 (1 − ε′ )) and opt(L> 2 (1 − ε′ )) to get
that conditioned on E
′

(1 − ε2 )2
n
n
c ≤ opt(L> 2 (1 − ε′ )).
· opt(L> 2 (1 − ε′ )) ≤ opt
′
2
(1 + 3ε σ)

Now using the fact that ǫ ∈ (0, 1) and σ ≥ 1, it is easy to verify that we can lower bound the first factor
′

as

(1− ε2 )2
(1+3ε′ σ)2

≥ 1−10ε′ σ. In addition, since σ ≤

1
20ε′ ,

n

c ≥ 12 opt(L> 2 (1−ε′ )).
this in particular implies opt

Then under the event E the requirements of the Theorem 4.1 holds and thus taking a union bound
over the event E and this theorem gives that with probability at least 1 − 13δ the solution {x̄t }nt=n/2+1
n

n

is c2 ε-feasible for L> 2 (1 − ε′ ) (and thus is (c2 ε + ε′ )-feasible for L> 2 ) and has value
n
X

t=n/2+1

n

c ≥ (1 − c3 ε)(1 − 10ε′ σ) opt(L> 2 (1 − ε′ ))
π t x̄t ≥ (1 − c3 ε) opt
n

≥ (1 − c5 εσ) opt(L> 2 (1 − ε′ )),

for some constant c5 , where the last inequality uses the fact σ ≥ 1, which gives the desired guarantees.
(Actually, in more detail notice that the event E only depends on what set of blocks (π t , At , C t ) of the
n
underlying LP L comprise the blocks in the random sampled LP L> 2 (1 − ε′ ) (this also determines the
n
blocks that comprise the sampled LP L≤ 2 (1 − ε′ )). Thus, we can first condition that the set of blocks
n
in L> 2 (1 − ε′ ) is a specific one that satisfies E, and since we do not fix their order they still appear
n
in random order in the conditioned L> 2 (1 − ε′ ) and we can apply Theorem 4.1 to this conditioned
n
L> 2 (1 − ε′ ); ranging over all such conditioning then gives the result.)

34

E

Proof of Lemma 6.3

First we claim that with probability at least 1−6δ, the random LP LSi (1−εi ) is (εi , 7σ)-stable.
Notice
p
′
that we can employ Lemma 5.5(c) to p
L with parameter ε set to 2εi (in particular, 2εi |Si |/n ≥ ε
plus Lemma B.1 implies that L is (2εi |Si |/n, σ)-stable). Thus, Lemma 5.5(c) guarantees that with
probability at least 1 − 2δ, opt(LSi (1 − 2εi )) ≤ (1 + 6σεi ) |Sni | opt(L). Moreover, applying Lemma 5.5(b)
to L with ε′ = εi we get that with probability at least 1 − 4δ, opt(LSi (1 − εi )) ≥ (1 − ε2i ) |Sni | opt(L).
Putting these inequalities together, we get that with probability at least 1 − 6δ
opt(LSi (1 − 2εi )) ≤

(1 + 6σεi )
opt(LSi (1 − εi )) ≤ (1 + 7σεi )opt(LSi (1 − εi )),
(1 − ε2i )

where the last inequality uses σ ≥ 1 and that εi ≤
√
example ε ≤ 71 suffices). This proves the claim.

√

ε is at most a sufficiently small constant (for

Second, notice that whenever the claim above holds (i.e. LSi (1 − εi ) is (εi , 7σ)-stable) we can apply
Theorem 6.1 with parameters (εi , δ, 7σ) to obtain guarantees for the solution (0, . . . , 0, x̄|Si−1 |+1 , . . . , x̄|Si | ).
So employing the claim above, Theorem 6.1 and union bound, we get that with probability at least
1 − 19δ this solution is (c4 εi )-feasible for LSi \Si−1 (1 − εi ) (and thus ((c4 + 1)εi )-feasible for LSi \Si−1 )
√
P|Si |
πx̄t ≥ (1 − c5 7σεi )opt(LSi \Si−1 (1 − 2εi )). This concludes the proof of the
and has value t=|S
i−1 |+1
lemma. (As noted at the end of Theorem 6.1, formally we should condition on the set of blocks of
LSi being such that the claim above holds and then apply Theorem 6.1 on the conditioned LP (which
still has its blocks coming in random order), and then take an average over all such conditionings.)

F

Proof of Lemma 7.7

The following will be a more convenient way of seeing the random order process: the random restricted
LP LI (i.e. columns are in random order and we are focusing on the ones indexed by I) has the same
distribution as the LP LI for I a uniformly chosen |I|-subset of [n] (i.e. sampling |I|-columns from L
without replacement).
The following lemma is the main part of the argument.
Lemma F.1. Let ε ≤ 1/20. Given L ∈ PLPn with width at least 40B, let τ be an opt(L)-good
skimming threshold for L. Let K be a random pn-subset of [n] for p ∈ [ 41 , 34 ]. Then with probability at
least 1 − 2δ,
rhs(skimτ (LK )) ∈ (1 ± ε) p rhs(skimτ (L))
and with probability at least 1 − 8δ,
opt(skimτ (LK )) ∈ (1 ± ε)p opt(skimτ (L)) ± ε64pBτ.
Proof. Let H = {t : πt > τ } be the set of high-value items. If At is the tth column of A, we get that
P
bL := rhs(skimτ (L)) = rhs(L) − t∈H At ;
P
P
K
K
t = p rhs(L) −
t
bK
L := rhs(skimτ (L )) = rhs(L ) −
t∈K:πt >τ A
t∈H∩K A .

Since K is a random pn-subset of the columns, the expectation of the second line is precisely p times
the first line. To obtain concentration, fix a coordinate i. The second property
of a good skimming
P
i
≤ (bL )i .
threshold implies the high-value items occupy at most half of the budget: t∈H Ati ≤ rhs(L)
2
35


P
P
t
t = p
This
gives
E
A
i
t∈H Ai ≤ p (bL )i and Bernstein’s inequality Corollary 2.4 gives that
t∈H∩K
P
P
t
t
t∈H∩K Ai = p
t∈H Ai ± ε p (bL )i with probability at least

 2


ε p (bL )i
2δ
(ε p (bL )i )2
≥ 1 − 2 exp −
≥1− ,
1 − 2 exp −
(4 + ε)p (bL )i
5
m

where the last inequality uses the width lower bound (bL )i ≥ 21 rhs(L)i ≥ 20B (recall we have used
the normalization Ati ∈ [0, 1]). A union bound over all coordinates i then gives that bK
L ∈ p bL (1 ± ε)
with probability at least 1 − 2δ, giving the first part of the lemma.

For the estimate of the optimal value, let L := [n] \ H be the low-value items. Let skimτ (L) p1 · bK
L
be the LP skimτ (L) with the right-hand side replaced by p1 · bK
L and notice that
skimτ (LK ) = max

P

t∈L∩K πt xt

|

P

t
t∈K A xt

≤ bK
L = skimτ (L)

1
p

· bK
L

K

.

(F.20)


The idea is to apply Lemma 5.5 to bound skimτ (L) 1p · bK
L , but unfortunately the right-hand side
of this LP is random; but since from the previous part p1 · bK
L ∈ bL (1 ± ε) with good probability, we
replace the right-hand side with the upper bound (1 + ε)bL (resp. lower bound (1 − ε)bL ) to upper
(resp. lower) bound the optimal value. So define L+ = skimτ (L) bL (1 + ε) and employ Lemma 5.5(c)
32τ B
to L+ with ρ = opt(L
to get that with probability at least 1 − 2δ
+)
opt(LK
+)

≤




ε64τ B
p opt(L+ ) ≤ (1 + ε)p opt(skimτ (L)) + ε64pBτ,
1+
opt(L+ )

(F.21)

1
where again opt(L+ ) ≤ (1 + ε) opt(skimτ (L)) since an optimal solution to L+ can be scaled by 1+ε
to give a feasible solution to skimτ (L). Moreover, from the first part of this lemma, with probability
1
K K
K
at least 1 − 2δ we have 1p · bK
L ≤ bL (1 + ε), in which case opt(skimτ (L)( p · bL ) ) ≤ opt(L+ ). Thus,
together with inequalities (F.20) and (F.21), a union bound gives that with probability at least 1 − 4δ

opt(skimτ (LK )) ≤ (1 + ε)p opt(skimτ (L)) + ε64pBτ.
Using the same reasoning, the lower bound
opt(skimτ (LK )) ≥ (1 − ε)p opt(skimτ (L)) − ε64pBτ
holds with probability at least 1 − 4δ. Taking a union bound over these upper and lower bounds then
concludes the proof of the lemma.
n

Proof of Lemma 7.7. Let I be a random n3 -subset of [n] and let J = [n] \ I, and recall skimτ (L≤ 3 ) has
n
the same distribution as skimτ (LI ) and skimτ (L> 3 ) has the same distribution as skimτ (LJ ). Thus,
employing Lemma F.1 with K = I and then K = J and employing a union bound, we get that with
probability at least 1 − 4δ


n 
n 
n 
1−ε 1+ε 1
1
,
rhs skimτ (L> 3 ) ⊆ (1 ± 3ε) rhs skimτ (L> 3 ) ,
rhs skimτ (L≤ 3 ) ∈
1+ε 1−ε 2
2
where the last inequality uses ε ≤ 31 .
n 
The bounds for opt skimτ (L≤ 3 ) follow similarly. This concludes the proof.

36

G

Proof of Theorem 7.11

We prove only the first part of the theorem since the second directly follows from it. Let E be the
event that the the guarantee of Theorem 7.10 holds for all i = 1, . . . , log 1ε . Since each such guarantee
holds with probability at least 1 − 15δ, a union bound gives that E holds with probability at least
1 − 15δ log 1ε . As in the proof of Theorem 6.2, it is easy to see that under E the returned solution
{x̄t }t is feasible for L.

Now we analyze the value val of the solution. To simplify the notation, let opt(I) = opt(LI ) for any
subset I ⊆ [n]. Again, conditioned on E we can put together the guarantees from Theorem
p 7.10 for
each phase of mDLA to get (recall in phase i we use the approximation parameter εi = ε n/|Si |)
E[val | E] ≥

log
ε−1
X
i=1



E opt(Si \ Si−1 ) − c6 εi opt(Si ) | E .

(G.22)

First we analyze the unconditioned value of the right-hand side of this expression.
P ε−1
P ε−1
Lemma G.1. log
E[opt(Si \ Si−1 )] − c6 log
εi E[opt(Si )] ≥ (1 − 2ε − 2δ log ε−1 − 4c6 ε) opt(L).
i=1
i=1

Proof. The last term in the left-hand side is at most 4c6 ε opt(L): Lemma 5.5(d) gives E[opt(Si )] ≤
|Si |
′
n opt(L) (since our LP without covering constraints is trivially (ε , 0)-stable), so we get
c6

log
ε−1
X
i=1

εi E[opt(Si )] ≤ c6

log
ε−1
X
i=1

−1

log
ε
X
|Si |
opt(L) = c6
εi ε 2i opt(L) ≤ 4c6 ε opt(L),
εi
n

where the last inequality follows from the bound

i=1

Plog ε−1
i=1

εi 2i−1 ≤ 2 from equation (6.14).

To show that the first term in the left-hand side is approximately opt(L) is a little more complicated,
πt
we do not have bounds showing that opt(Si \ Si−1 ) ≈
since without good bounds on the ratios opt(L)
|Si |\|Si−1 |
opt(L) even in expectation; we need to look at all the terms
n
Let x∗ be a optimal solution for L and let x∗ (i) be the solution scaled

opt(Si \ Si−1 ) simultaneously.

down by (1 − ε2i ) and restricted
to the 2i−1 εn columns in Si \ Si−1 . From Lemma 5.5(a) we have that x∗ (i) is feasible for LSi \Si−1 with
probability at least 1 − 2δ. Let G be the good event that for all i we have x∗ (i) feasible for LSi \Si−1 ,
which holds with probability at least
1 − 2(log ε−1 )δ by a union bound. Then for every scenario in G
P
we have opt(Si \ Si−1 ) ≥ (1 − ε2i ) t∈Si \Si−1 πt x∗t , so adding over all i ≥ 1 gives
X
X
X εi X
πt x∗t .
πt x∗t −
opt(Si \ Si−1 ) ≥ opt(L) −
2
i≥1

i≥1

t∈Si \Si−1

t∈S0

Then letting 1G be the indicator of the event G and using the non-negativity of the objective function,
we get that


X

X
X
X εi X
opt(Si \ Si−1 ) ≥ E 1G ·
E[πt x∗t ].
E[πt x∗t ] −
E
opt(Si \ Si−1 ) ≥ E[1G · opt(L)] −
2
i≥1

i≥1

i≥1

t∈Si \Si−1

t∈S0

Clearly E[1G ·opt(L)] = Pr(G)·opt(L) ≥ (1− 2δ log ε−1 ) opt(L). Moreover, by the random order model
we have that for all t, E[πt x∗t ] = opt(L)
n . Thus, the above bound becomes

X
opt(L) X εi ε 2i−1 n
− εopt(L) ≥ (1 − 2ε − 2δ log ε−1 ) opt(L),
opt(Si \ Si−1 ) ≥ (1 − 2δ log ε−1 ) opt(L) −
E
n
2
i≥1

i≥1

where again we have used equation (6.14) in the last step. This concludes the proof of the lemma.
37

To handle the conditioned right-hand side of (G.22) we observe the following: with probability 1 we
P ε−1
have opt(S0 ) + log
opt(Si \ Si−1 ) ≤ opt(L), since concatenating the optimal solutions for LS0 ,
i=1
LS1 \S0 , . . . , gives a feasible solution
convenience, let vali :=Popt(Si \ Si−1 ) − c6 εi opt(Si ).
P for L. ForP
¯ Pr(E),
¯ inequality
Then using the decomposition E[ i≥1 vali ] = E[ i≥1 vali | E] Pr(E) + E[ i≥1 vali | E]
(G.22) gives
X
X
X
¯
¯
E[val | E] ≥
E[vali | E] ≥
E[vali ] − Pr(E)
E[vali | E]
i≥1

≥
≥

X
i≥1

X
i≥1

i≥1

i≥1

"

¯ E[opt(S0 ) | E¯] +
E[vali ] − Pr(E)
¯ opt(L).
E[vali ] − Pr(E)

X
i≥1

#

¯
E[opt(Si \ Si−1 ) | E]

¯ ≤ 15δ log ε−1 , gives
Lower bounding the first term using Lemma G.1 and recalling that Pr(E)
−1
E[val | E] ≥ (1 − 2ε − 17δ log ε − 4c6 ε) opt(L). This concludes the proof of Theorem 7.11.

38

