<p>Luca, since a year has passed, you probably have researched your own
answer.  I'm answering some of your questions here just for the
record.  I review some Lagrangian-relaxation algorithms for the
problems you mention, and sketch the connection to learning (in
particular, following expert advice).  I don't comment here on SDP
algorithms.</p>

<p>Note that the particular algorithms that you mention do not run in
nearly linear time.  (There is a nearly linear-time algorithm for
<em>explicitly</em> given packing or covering problems.  See
<a href="http://arxiv.org/abs/0801.1987" rel="noreferrer">Beating Simplex for Fractional Packing and Covering Linear Programs</a>.)
The algorithms you have in mind typically have variants that run in a
nearly linear number of <em>iterations</em>, but each iteration typically
requires at least linear time as well.  I discuss some of these
algorithms below.</p>

<h3>Some useful functions</h3>

<p>Before we start, here are some functions that we will use in the proof sketches.
(If you are interested in the algorithms, but not the proof details, you can skip ahead.)
For any vector <span class="math-container">$y$</span>, define <span class="math-container">$\mbox{Lmax}(y)$</span> to be <span class="math-container">$\ln \sum_i \exp(y_i)$</span>.
This function is an upper bound on <span class="math-container">$\max_i y_i$</span>:
<span class="math-container">$$\max_i y_i ~\le~ \mbox{Lmax}(y) ~\le~ \max_i y_i + \ln m.$$</span>
Analogously, define <span class="math-container">$\mbox{Lmin}(y)$</span> to be <span class="math-container">$-\mbox{Lmax}(-y)$</span>,
a lower bound on <span class="math-container">$\min_i y_i$</span>.</p>

<p>For convenience in what follows, 
we use <span class="math-container">$g(y)$</span> to denote the gradient <span class="math-container">$\nabla \mbox{Lmin}(y)$</span> of Lmin.
We use <span class="math-container">$G(y)$</span> to denote the gradient <span class="math-container">$\nabla \mbox{Lmax}(y)$</span> of Lmax.</p>

<p>Explicitly, <span class="math-container">$g_i(y)$</span> is <span class="math-container">$\exp(-y_i)/\sum_{i'} \exp(-y_{i'})$</span>
while <span class="math-container">$G_i(y)$</span> is <span class="math-container">$\exp(y_i)/\sum_{i'} \exp(y_{i'})$</span>.</p>

<p>Lmin and Lmax are <em>smooth</em> in the following sense: 
for any vectors <span class="math-container">$d\in[0,\varepsilon]^n$</span> and <span class="math-container">$y\in R^n$</span>,
<span class="math-container">$$\mbox{Lmin}(y+d) ~\ge~ \mbox{Lmin}(y) 
~+~ (1-O(\varepsilon))\, d \cdot g(y)$$</span>
and
<span class="math-container">$$\mbox{Lmax}(y+d) ~\le~ \mbox{Lmax}(y) 
~+~ (1+O(\varepsilon))\, d \cdot G(y).$$</span></p>

<p>Note that both of the gradients have 1-norm equal to 1:
<span class="math-container">$|G(y)| = |g(y)| = 1$</span>.  (Throughout we use <span class="math-container">$|z|$</span> to denote the 1-norm.)</p>

<p>Note also that, for a matrix <span class="math-container">$A$</span>, 
the gradient of the function <span class="math-container">$x\mapsto \mbox{Lmin}(Ax)$</span> with respect to <span class="math-container">$x$</span>
is (by the chain rule) <span class="math-container">$(g(Ax))^T A$</span>.
More explicitly, the partial derivative of the function with respect to <span class="math-container">$x_j$</span>
is <span class="math-container">$\sum_i A_{ij} \exp(-A_i x) / \sum_i \exp(-A_i x)$</span>.
Likewise,  the partial derivative of Lmax<span class="math-container">$(Ax)$</span> 
with respect to <span class="math-container">$x_j$</span> is <span class="math-container">$\sum_i A_{ij} \exp(A_i x)/\sum_i \exp(A_i x)$</span>. </p>

<h3>Fractional Set Cover</h3>

<p>Fix a Set-Cover instance.
Let <span class="math-container">$A$</span> denote the element/set incidence matrix.
Thus, <span class="math-container">$A_{es} = 1$</span> if <span class="math-container">$e\in s$</span>, else 0,
and <span class="math-container">$A_e x$</span> is the extent that  fractional cover <span class="math-container">$x$</span> covers element <span class="math-container">$e$</span>.</p>

<p>The LP is <span class="math-container">$\min\{ |x| : A x \ge 1; x \ge 0\}$</span>.
Given <span class="math-container">$\varepsilon\in (0,1)$</span>, the algorithm is</p>

<hr>

<ol>
<li>Initialize all <span class="math-container">$x_s = 0$</span>.  Let <span class="math-container">$N=\log(n)/\varepsilon$</span>.  </li>
<li><p>Repeat until <span class="math-container">$\min_e A_e x \ge N$</span>:   </p>

<p>2.1. Choose <span class="math-container">$s$</span> maximizing the partial derivative of Lmin<span class="math-container">$(Ax)$</span> w.r.t. <span class="math-container">$x_s$</span>.<br>
      (Explicitly, choose <span class="math-container">$s$</span> maximizing <span class="math-container">$\sum_{e\in s} \exp(-\sum_{s'\ni e} x_{s'})$</span>.)   </p>

<p>2.2. Increase <span class="math-container">$x_s$</span> by <span class="math-container">$\varepsilon$</span>.    </p></li>
<li><p>Return <span class="math-container">$x/\min_{e} A_e x$</span>.</p></li>
</ol>

<hr>

<p>The algorithm returns a <span class="math-container">$(1+O(\varepsilon))$</span> approximate solution
in <span class="math-container">$O(|x^*|\log(n)/\varepsilon^2)$</span> iterations, where <span class="math-container">$n$</span> is the number of elements
and <span class="math-container">$x^*$</span> is the optimal fractional set cover (trivially <span class="math-container">$|x^*|\le n$</span>).
(A similar algorithm appears in <a href="http://www.cs.ucr.edu/~neal/non_arxiv/SODA_1995_170.pdf" rel="noreferrer">the paper Chandra mentioned</a>.
Vertex Cover is of course a special case.)</p>

<p>(<strong>Remark:</strong> Note that the iteration bound does not depend on the number
of sets, just the number of elements.  Thus, the algorithm can be used
with an implicitly defined set system, as long as, given weights on the
elements, one can efficiently find a set of maximum (or near-maximum) total weight.
This kind of oracle is the same as the separation oracle required to apply
the ellipsoid algorithm to the <em>dual</em> problem. For packing problems such
as set packing, you need an oracle that, given weights on the elements,
returns a set <em>minimizing</em> the total weight.  For problems such as
multi-commodity flow, you might, for example, need to find a path
minimizing the sum of some given edge weights.)</p>

<p>Here's a sketch of the proof of the performance guarantee.
In each iteration, the partial derivative w.r.t. the chosen <span class="math-container">$s$</span>
is at least <span class="math-container">$1/|x^*|$</span>, where <span class="math-container">$x^*$</span> is the optimal fractional set cover.</p>

<p>(To see why, recall that the gradient of Lmin<span class="math-container">$(Ax)$</span> with respect to <span class="math-container">$x$</span> is <span class="math-container">$(g(Ax))^T A$</span>.
If we were to choose a set <span class="math-container">$s'$</span> at random from the distribution <span class="math-container">$x^*/|x^*|$</span>,
the expected value of the partial derivative with respect to <span class="math-container">$x_{s'}$</span>
would thus be <span class="math-container">$(g(Ax))^T \,A x^*/|x^*|$</span>.
Since <span class="math-container">$Ax^* \ge 1$</span>, this is at least <span class="math-container">$|g(Ax)|/|x^*|$</span>.
Since <span class="math-container">$|g(Ax)|=1$</span>, this is at least <span class="math-container">$1/|x^*|$</span>.
Thus, there must exist some <span class="math-container">$s$</span> giving partial derivative at least <span class="math-container">$1/|x^*|$</span>.
Since the algorithm chooses <span class="math-container">$x_s$</span> in each iteration to <em>maximize</em>
the partial derivative, it achieves a partial derivative of at least <span class="math-container">$1/|x^*|$</span>.)</p>

<p>Then, the step size <span class="math-container">$\varepsilon$</span> is chosen just small enough so that 
no coordinate of <span class="math-container">$A x$</span> increases by more than <span class="math-container">$\varepsilon$</span>.
Thus, because of the smoothness of Lmin,  increasing <span class="math-container">$x_s$</span>
to <span class="math-container">$x_s+\varepsilon$</span> increases <span class="math-container">$\mbox{Lmin}(Ax)$</span> by at least
<span class="math-container">$(1-O(\varepsilon))\varepsilon/|x^*|$</span>.</p>

<p>In this way, the algorithm maintains the invariant
<span class="math-container">$$\mbox{Lmin}(Ax) \ge (1-O(\varepsilon)) |x|/|x^*| - \ln n.$$</span>
(Note that Lmin<span class="math-container">$(\overline 0)$</span> equals <span class="math-container">$\ln n$</span>.)</p>

<p>At termination, in the invariant, the <span class="math-container">$\ln n$</span> term is <span class="math-container">$O(\varepsilon)$</span> times the left-hand side,
so by calculation one gets <span class="math-container">$\min_e A_e x \ge  (1-O(\varepsilon)) |x|/|x^*|$</span>.
After the normalization in the last line of the algorithm,
this implies <span class="math-container">$|x| \le (1+O(\varepsilon))|x^*|$</span>.</p>

<p>FWIW, the inequalities involved in proving the invariant are essentially
the same as those involved in proving the Chernoff bound.
(In fact, this algorithm can be derived by applying the
method of conditional probabilities to a randomized-rounding
scheme that repeatedly samples sets from the distribution <span class="math-container">$x^*/|x^*|$</span>
(with replacement), increasing <span class="math-container">$x_s$</span> for each sampled set <span class="math-container">$s$</span>.
This derandomization of that gives the algorithm:
the underlying invariant is just that the pessimistic estimator stays below 1.
The exponential penalties in the pessimistic estimator come from the
using the Chernoff bound in the analysis of the rounding scheme.
This basic idea is explained further in <a href="http://www.cs.ucr.edu/~neal/non_arxiv/SODA_1995_170.pdf" rel="noreferrer">the paper Chandra mentioned</a>.)</p>

<h3>Fractional Weighted Set Cover (and general fractional Covering)</h3>

<p>To handle problems such as Weighted Set Cover <em>efficiently</em>,
we modify the algorithm to use non-uniform increments
(an idea due to <a href="http://scholar.google.com/scholar?cluster=735294650310145635&amp;hl=en&amp;as_sdt=0,5" rel="noreferrer">Garg and Konemann</a>).   </p>

<p>The LP is <span class="math-container">$\min\{ c\cdot x : (\forall e) \sum_{s\ni e} x_s \ge 1\}$</span>, 
where <span class="math-container">$e$</span> ranges over the elements, <span class="math-container">$s$</span> ranges over the sets,
and all variables are non-negative.
To present the algorithm, first rewrite the problem as a general covering problem.
Let <span class="math-container">$A_{es} = 1/c_s$</span> for <span class="math-container">$e\in s$</span> and <span class="math-container">$A_{es} = 0$</span> otherwise.
Then (with a change of variables, scaling each <span class="math-container">$x_s$</span> by <span class="math-container">$c_s$</span>),
the LP is <span class="math-container">$\min\{ |x| : A x \ge 1; x \ge 0\}$</span>,
which we can view as a general covering LP.
Here is the algorithm:</p>

<hr>

<ol>
<li><p>Initialize all <span class="math-container">$x_s = 0$</span>.  Let <span class="math-container">$N=\log(n)/\varepsilon$</span>.</p></li>
<li><p>Repeat until all covering constraints have been deleted:</p>

<p>2.1. Choose <span class="math-container">$s$</span> maximizing the partial derivative of Lmin<span class="math-container">$(Ax)$</span> w.r.t. <span class="math-container">$x_s$</span>.<br>
     (Explicitly, choose <span class="math-container">$s$</span> maximizing <span class="math-container">$\sum_{e\in s} \exp({-\sum_{s'\ni e} x_{s'}})/c_s$</span>.)</p>

<p>2.2. Increase <span class="math-container">$x_s$</span> by <span class="math-container">$\delta$</span>, where <span class="math-container">$\delta$</span> is chosen maximally such that, for every remaining covering constraint <span class="math-container">$e$</span>, the increase in <span class="math-container">$A_e \cdot x$</span> is at most <span class="math-container">$\varepsilon$</span>.</p>

<p>2.3 Delete all covering constraints <span class="math-container">$e$</span> such that <span class="math-container">$A_e\cdot x \ge N$</span>.</p></li>
<li><p>Return <span class="math-container">$x/\min_e A_e\cdot x$</span>.</p></li>
</ol>

<hr>

<p>The algorithm returns a <span class="math-container">$(1+O(\varepsilon))$</span>-approximate solution
in <span class="math-container">$O(n\log(n)/\varepsilon^2)$</span> iterations, where <span class="math-container">$n$</span> is the number of covering constraints.
(Each iteration increases some remaining <span class="math-container">$A_e x$</span> by <span class="math-container">$\varepsilon$</span>; this can happen
only <span class="math-container">$N/\varepsilon$</span> times to a constraint before it is deleted.)
The proof of correctness is via essentially the same invariant as for Set Cover.</p>

<p>Weighted Vertex Cover is a special case. </p>

<h3>Maximum Fractional Bipartite Matching</h3>

<p>Given a graph <span class="math-container">$G=(U,W,E)$</span>,
the natural LP for the problem is <span class="math-container">$\max\{|x| : \forall v.\, \sum_{e\ni v} x_e \le 1\}$</span>.</p>

<p>In matrix representation, this is a packing LP <span class="math-container">$\max\{|x| : Ax \le 1; x \ge 0\}$</span>
with 0-1 coefficients (<span class="math-container">$A_{ve} = 1$</span> if <span class="math-container">$v\in e$</span>).
Such problems do not require non-uniform increments, so a simple algorithm analogous to the unweighted Set Cover algorithm (but for packing) will do:</p>

<hr>

<ol>
<li>Initialize all <span class="math-container">$x_e = 0$</span>.  Let <span class="math-container">$N=\log(n)/\varepsilon$</span>.</li>
<li><p>While <span class="math-container">$A x &lt; N$</span>:</p>

<p>2.1. Choose <span class="math-container">$e$</span> minimizing the partial derivative of Lmax<span class="math-container">$(Ax)$</span> w.r.t. <span class="math-container">$x_e$</span>.<br>
      (Explicitly, choose <span class="math-container">$e$</span> to minimize <span class="math-container">$\sum_{v\in e} \exp(\sum_{e'\ni v} x_{e'})$</span>.)</p>

<p>2.2. Increase <span class="math-container">$x_e$</span> by <span class="math-container">$\varepsilon$</span>.  </p></li>
<li><p>Return <span class="math-container">$x/\max_{v} A_v x$</span>.</p></li>
</ol>

<hr>

<p>The algorithm returns a <span class="math-container">$(1-O(\varepsilon))$</span>-approximate solution in <span class="math-container">$O(n\log(n)/\varepsilon^2)$</span> iterations.
(This is because each iteration increases <span class="math-container">$|x|$</span> by <span class="math-container">$\varepsilon$</span>,
and finally, before normalization, <span class="math-container">$|x| = O(N n)$</span>.)</p>

<p>Just for fun, here is a curious alternative algorithm for Perfect Bipartite Matching.
Recall that <span class="math-container">$G=(U,W,E)$</span>.  Let <span class="math-container">$n=|U|=|W|$</span>.</p>

<hr>

<ol>
<li>Initialize all <span class="math-container">$x_e = 0$</span>.  Let <span class="math-container">$N=4\ln(n)/\varepsilon$</span>.  </li>
<li><p>Repeat <span class="math-container">$n\,N$</span> times:</p>

<p>2.1. Choose <span class="math-container">$u$</span> uniformly at random from <span class="math-container">$U$</span>.<br>
 2.2. Choose <span class="math-container">$w$</span> such that <span class="math-container">$(u,w)\in E$</span> minimizing <span class="math-container">$\sum_{e\ni w} x_e$</span>.<br>
 2.3. Increase <span class="math-container">$x_{uw}$</span> by <span class="math-container">$\varepsilon$</span>.   </p></li>
<li><p>Return <span class="math-container">$x/N$</span>.</p></li>
</ol>

<hr>

<p>If <span class="math-container">$G$</span> has a perfect matching, the algorithm returns
an <span class="math-container">$x$</span> such that <span class="math-container">$|x|=n$</span>, and, with high probability,
for all vertices <span class="math-container">$u\in U$</span>, <span class="math-container">$1-O(\varepsilon) \le \sum_{e\ni u} x_e \le 1+O(\varepsilon)$</span>,
and for all vertices <span class="math-container">$w\in W$</span>, <span class="math-container">$\sum_{e\ni w} x_e \le 1+O(\varepsilon)$</span>.
If you are interested in the details of the proof, please ask...</p>

<h3>Mixed Packing and Covering</h3>

<p>You may have asked about bipartite matching hoping for an example
of a <em>mixed</em> packing and covering problem, that is, one of the form
<span class="math-container">$$\exists x?~ Px \le p; Cx \ge c; x \ge 0.$$</span>
Here's one algorithm for such problems.
First, normalize so that <span class="math-container">$p=\overline 1$</span> and <span class="math-container">$c=\overline 1$</span>.</p>

<p>Let <span class="math-container">$m$</span> be the number of constraints (rows in <span class="math-container">$P$</span> plus rows in <span class="math-container">$C$</span>).</p>

<hr>

<ol>
<li>Initialize all <span class="math-container">$x_j = 0$</span>.  Let <span class="math-container">$N=2\ln(m)/\varepsilon$</span>.</li>
<li><p>While <span class="math-container">$P x &lt; N$</span>:</p>

<p>2.1. Choose <span class="math-container">$j$</span> so that the partial derivative of Lmax<span class="math-container">$(Px)$</span> with respect to <span class="math-container">$x_j$</span> is at most the partial derivative of Lmin<span class="math-container">$(Cx)$</span> with respect to <span class="math-container">$x_j$</span>.  (Explicitly, choose <span class="math-container">$j$</span> such that <span class="math-container">$$\frac{\sum_i P_{ij} \exp(P_i x)}{\sum_{i}\exp(P_i x)} \le \frac{\sum_i C_{ij} \exp(-C_i x)}{\sum_{i}\exp(-C_i x)}.)$$</span></p>

<p>2.2. Increase <span class="math-container">$x_j$</span> by <span class="math-container">$\delta$</span>, where <span class="math-container">$\delta$</span> is chosen maximally such that no constraint <span class="math-container">$P_i x$</span> or remaining constraint <span class="math-container">$C_i x$</span> increases by more than <span class="math-container">$\varepsilon$</span>. </p>

<p>2.3. Delete all covering constraints <span class="math-container">$i$</span> such that <span class="math-container">$C_i x \ge N$</span>.</p></li>
<li><p>Return <span class="math-container">$x/\max_i P_i x$</span>.</p></li>
</ol>

<hr>

<p>Assuming the given problem is feasible, the algorithm
returns an <span class="math-container">$x$</span> such that <span class="math-container">$Px\le 1$</span> 
and <span class="math-container">$Cx\ge 1-O(\varepsilon)$</span>.
The number of iterations is <span class="math-container">$O(m\ln(m)/\varepsilon^2)$</span>,
because each iteration increases some constraint by <span class="math-container">$\varepsilon$</span>,
and this can happen for each constraint at most <span class="math-container">$N$</span> times.</p>

<p>The proof of correctness is via the invariant
<span class="math-container">$$\mbox{Lmax}(Px) \le 2\ln(m) + (1+O(\varepsilon)) \mbox{Lmin}(Cx).$$</span>
The invariant implies
<span class="math-container">$$\max Px \le 2\ln(m) + (1+O(\varepsilon)) \min Cx.$$</span>
At termination the left-hand side is <span class="math-container">$\Omega(\log(m)/\varepsilon)$</span>,
proving the performance guarantee.</p>

<p>In Step 2.1, the desired <span class="math-container">$j$</span> must exist as long as the original problem is feasible.
(This is because, for any <em>feasible</em> <span class="math-container">$x^*$</span>, and any <span class="math-container">$x$</span>,
if we were to choose a random <span class="math-container">$j'$</span> from the distribution <span class="math-container">$x^*/|x^*|$</span>,
the expected value of the partial derivative of Lmax<span class="math-container">$(Px)$</span> with respect to <span class="math-container">$x_{j'}$</span>
would be at most <span class="math-container">$1/|x^*|$</span> (see the previous proof sketch for Set Cover).
Likewise, the expected value of the partial derivative of Lmin<span class="math-container">$(Cx)$</span> with respect to <span class="math-container">$x_{j'}$</span>
would be at least <span class="math-container">$1/|x^*|$</span>.
Thus, there is an <span class="math-container">$j$</span> such that the partial derivative of Lmax<span class="math-container">$(Px)$</span> with respect to <span class="math-container">$x_{j'}$</span>
is at most the partial derivative of Lmin<span class="math-container">$(Cx)$</span>.)</p>

<p>Then the invariant is maintained in each iteration because,
by the choice of <span class="math-container">$x_j$</span> and <span class="math-container">$\delta$</span>, 
and the smoothness of Lmin and Lmax,
increasing <span class="math-container">$x_j$</span> to <span class="math-container">$x_j+\delta$</span>
increases Lmax<span class="math-container">$(Px)$</span> 
by at most <span class="math-container">$1+O(\varepsilon)$</span>
times the increase in Lmin<span class="math-container">$(Cx)$</span>.</p>

<h3>Learning (following experts / boosting)</h3>

<p>One reference for understanding this connection is
<a href="http://scholar.google.com/scholar?cluster=4120237815378119841&amp;hl=en&amp;as_sdt=0,5&amp;as_vis=1" rel="noreferrer">Adaptive game playing using multiplicative weights</a>, by Freund and Schapire.
Here is a quick summary to give the technical idea.</p>

<p>Consider the following repeated game.  In each round <span class="math-container">$t$</span>:  </p>

<ol>
<li>You choose a probability distribution <span class="math-container">$p^t$</span> on <span class="math-container">$[n]$</span> (the <span class="math-container">$n$</span> so-called <em>experts</em>).  </li>
<li>Knowing <span class="math-container">$p^t$</span>, the adversary then chooses a payoff vector <span class="math-container">$a^t\in [0,1]^{n}$</span>.  </li>
<li>You receive payoff <span class="math-container">$p^t\cdot a^t$</span> for the round.  </li>
</ol>

<p>The game stops after some number of rounds.
Your goal is to minimize your regret
in comparison to any single expert (i.e., pure strategy) <span class="math-container">$i$</span>.
That is, your goal is to minimize <span class="math-container">$(\max_i \sum_t a^t_i) - \sum_t p^t\cdot a^t$</span>.</p>

<p>Fix any <span class="math-container">$\varepsilon&gt;0$</span>.
Let vector <span class="math-container">$y^t$</span> denote <span class="math-container">$\varepsilon \sum_{s \le t} a^s$</span>, that is,
<span class="math-container">$\varepsilon$</span> times the vector sum of the payoff vectors up to time <span class="math-container">$t$</span>.
Recall that <span class="math-container">$G(y)$</span> is the gradient of Lmax<span class="math-container">$(y)$</span>.</p>

<p>Here's the basic strategy we will analyze:
<em>On round <span class="math-container">$t$</span>, choose <span class="math-container">$p^t$</span> to be <span class="math-container">$G(y^{t-1})$</span>.</em></p>

<p>By inspection, this gives you payoff <span class="math-container">$a^t \cdot G(y^{t-1})$</span> in round <span class="math-container">$t$</span>.</p>

<p>Because of the smoothness property of <span class="math-container">$F$</span>,
<span class="math-container">$$\mbox{Lmax}(y^t) \le \mbox{Lmax}(y^{t-1}) + (1+O(\varepsilon))  \varepsilon a^t \cdot G(y^{t-1}).$$</span>
That is, in each round, <span class="math-container">$\mbox{Lmax}(y^t)$</span> can't increase by more than <span class="math-container">$\varepsilon(1+O(\varepsilon))$</span> times your payoff.
Since <span class="math-container">$\mbox{Lmax}(\overline 0) = \ln n$</span>, 
this maintains the invariant that <span class="math-container">$\mbox{Lmax}(y^t)$</span>
is at most your total payoff times <span class="math-container">$\varepsilon(1+O(\varepsilon)$</span>,
plus <span class="math-container">$\ln(n)$</span>.
On the other hand, your regret in comparison to the best expert <span class="math-container">$i$</span>
is <span class="math-container">$\max_i \sum_t a^t_i$</span>, i.e., <span class="math-container">$\varepsilon^{-1} \max_i y^t_i$</span>,
which is in turn at most <span class="math-container">$\varepsilon^{-1} \mbox{Lmax}(y^t)$</span>.</p>

<p>Thus, <em>your regret is at most <span class="math-container">$\varepsilon^{-1} \ln(n)$</span>, plus <span class="math-container">$O(\varepsilon)$</span> times your total payoff.</em></p>

<p><strong>Remark:</strong> I think, as Freund and Schapire point out, a "boosting" algorithm (in learning theory) is also implicit in this analysis.  See their paper for more details.</p>

<strong>Minimizing total payoff</strong>

<p>You can derive a similar strategy for the setting where the goal is to <em>minimize</em>,
rather than maximize, the total payoff.
Your regret, which you still want to minimize, is <span class="math-container">$\sum_t p^t\cdot a^t - \min_i a^t_i$</span>.
In that case, the corresponding strategy is to choose <span class="math-container">$p^t$</span> to be the gradient of <span class="math-container">$\mbox{Lmin}(y^t)$</span>.
With this strategy your regret is again at most
<span class="math-container">$\varepsilon^{-1} \ln n$</span> plus <span class="math-container">$O(\varepsilon)$</span> times your total payoff.</p>

<strong>Connection to Lagrangian-relaxation algorithms</strong>

<p>To see the connection to Lagrangian-relaxation algorithms, fix a Set-Cover instance.
Consider the latter type of game (with the goal of minimizing payoff),
where the experts correspond to the elements <span class="math-container">$e$</span> of your set system.
In each round, choose the probability distribution <span class="math-container">$p^t$</span> 
to be the gradient of Lmin<span class="math-container">$(y^t)$</span> as above, 
and have the adversary choose the payoff vector <span class="math-container">$a^t$</span> as a function of <span class="math-container">$p^t$</span> as follows:
<em>choose the set <span class="math-container">$s^t$</span> maximizing <span class="math-container">$\sum_{e\in s} p^t_e$</span>,
then let <span class="math-container">$a^t_e = 1$</span> if <span class="math-container">$e\in s^t$</span>, and <span class="math-container">$a^t_e = 0$</span> otherwise.</em></p>

<p>Given the correct stopping condition (discussed below),
this process gives you exactly the Set-Cover algorithm discussed at the start.</p>

<p>The performance guarantee of the algorithm follows from the regret bound as follows.
Let <span class="math-container">$X_s$</span> be the number of times the adversary chose set <span class="math-container">$s$</span> during the play.
Let <span class="math-container">$x^*$</span> be the optimal fractional set cover.
Let <span class="math-container">$T=|X_s|$</span> be the number of rounds played.
The regret bound implies
<span class="math-container">$$\textstyle \sum_t a^t\cdot p^t \le  \varepsilon^{-1}\ln(m) + \min_e \sum_t a_e^t.$$</span></p>

<p>Using the definition of <span class="math-container">$a^t$</span>, the <span class="math-container">$t$</span>th payoff
(the <span class="math-container">$t$</span>th term in the sum on the left)
equals <span class="math-container">$\sum_{e\in s^t} p^t_e$</span>.
The adversary chose <span class="math-container">$s^t$</span> to minimize this payoff.
If the adversary had instead chosen <span class="math-container">$s^t$</span> randomly 
from the distribution <span class="math-container">$x^*/|x^*|$</span>, the expectation of
the payoff would have been
<span class="math-container">$$ \sum_s \frac{x^*_s}{|x^*|} \sum_{e\in s} p^t_e
~=~
\frac{1}{|x^*|} \sum_e p^t_e \sum_{s\ni e} x^*_s 
~\ge~
\frac{1}{|x^*|} \sum_e p^t_e
 ~=~
\frac{1}{|x^*|}.$$</span>
(Above we use that <span class="math-container">$\sum_{s\ni e} x^*_s \ge 1$</span> for all <span class="math-container">$e$</span>, and <span class="math-container">$|p^t| = 1$</span>.)
Since each payoff is at least <span class="math-container">$1/|x^*|$</span>, the regret bound implies
<span class="math-container">$$ \frac{T}{|x^*|} \le  \varepsilon^{-1}\ln(m) + \min_e \sum_t a_e^t.$$</span>
By the definition of <span class="math-container">$X$</span>,
we have <span class="math-container">$|X| = T$</span> (each round chooses one set),
and <span class="math-container">$\sum_t a_e^t = \sum_e [e\in s^t] = \sum_{s\ni e} X_s$</span>,
giving
<span class="math-container">$$\frac{|X|}{|x^*|} \le  \varepsilon^{-1}\ln(m) +\min_e \sum_{s\ni e} X_s.$$</span> 
We make the process stop when <span class="math-container">$\min_e \sum_{s\ni e} X_s = \Omega(\varepsilon^{-2}\ln m)$</span>, 
so then (rearranging terms)
<span class="math-container">$$\frac{|X|}{\min_e \sum_{s\ni e} X_s}~ \le~ (1+O(\varepsilon)|x^*|.$$</span>
That is, normalizing <span class="math-container">$X$</span> gives a fractional set cover
of size at most <span class="math-container">$(1+O(\varepsilon))$</span> times optimum.</p>

<p><strong>Remark:</strong> In a sense, this learning theory interpretation
generalizes the algorithmic interpretation.  However, some
of the algorithmic techniques necessary for efficiency 
(such as non-uniform increments and dropping satisfied
covering constraints) don't seem to carry over into the 
learning theory setting naturally.  Likewise, algorithms for
<em>mixed</em> packing and covering LPs (e.g. <a href="http://arxiv.org/abs/cs/0205039" rel="noreferrer">these</a>)
don't seem to have natural analogues in the learning-theory setting.</p>

CC BY-SA 3.0
2012-11-20T03:30:28.057Z
That is quite the answer !!
Suresh Venkat
CC BY-SA 3.0
2012-11-20T06:39:09.757Z
Thanks.  Probably overdid it.  Am interested in feedback: how to present these ideas accessibly, what else to include...
Neal Young
CC BY-SA 4.0
2023-09-15T00:47:43.600Z
You call the algorithm for fractional set cover a "Lagrangian Relaxation algorithm". Can you explain the connection to [the definition of Lagrangian Relaxation in Wikipedia](https://en.wikipedia.org/wiki/Lagrangian_relaxation)? In particular, what are the Lagrangian coefficients $\lambda$ in the set cover example? And what are the constraints that are moved into the objective function?
Erel Segal-Halevi
CC BY-SA 4.0
2023-09-15T01:01:07.673Z
I use that term informally to mean that the algorithm replaces multiple constraints by a single weighted combination of those constraints (typically giving more weight to constraints that are "closer to violation").  I think the formal term for this particular kind of Lagrangian relaxation, where a collection of constraints is replaced by a single constraint, instead of being replaced by a function that is incorporated into the objective,  is "surrogate duality".  The basic technical challenge in each case (e.g. in MWU algorithms) is how to compute the weight assigned to each constraint.
Neal Young
CC BY-SA 4.0
2023-09-15T08:52:19.560Z
You write "The algorithm can be used with an implicitly defined set system, as long as, given weights on the elements, one can efficiently find a set of maximum (or near-maximum) total weight"; what are examples of approximation algorithms to this problem, for some implicitly-defined set-systems?
Erel Segal-Halevi
CC BY-SA 4.0
2023-09-15T15:22:20.277Z
@ErelSegal-Halevi, I haven't thought much about specific applications, but here's one I just made up.  Given a directed graph, two vertices S and T, and a collection Q of vertices, consider the problem of finding a minimum number of S->T paths that collectively contain all vertices.  You can relax the latter covering constraints as follows: given a weighting of the vertices, find an S-T path that maximizes the weights of the vertices on the path.  If you can, say, c-approximate the latter problem, then you can c'-approximate the fractional relaxation of the original one,  for any c' > c.
Neal Young
CC BY-SA 4.0
2012-11-19T22:18:22.123Z
2019-04-05T21:06:53.970Z
2019-04-05T21:06:53.970Z
Neal Young
<p>I would like to understand how the Arora-Kale SDP solver approximates the Goemans-Williamson relaxation in nearly linear time, how the Plotkin-Shmoys-Tardos solver approximates fractional &quot;packing&quot; and &quot;covering&quot; problems in nearly linear time, and how the algorithms are instantiations of the &quot;learning from experts&quot; abstract framework.</p>
<p>Kale's thesis has an excellent presentation, but I find it very difficult to directly jump into the abstract framework, and I would prefer to start from an example of a simple problem for which it's absolutely obvious what to do, and then move to more general problems, progressively adding &quot;features&quot; to the algorithm and to its analysis.</p>
<p>For example:</p>
<blockquote>
<p>How does Plotkin-Shmoys solve the linear programming relaxation of unweighted vertex cover? Weighted vertex cover? Set cover? Bipartite matching?</p>
<p>What is the simplest example in which the Arora-Kale algorithm is doing something interesting? How does it compute the largest eigenvalue of the Laplacian of a graph?</p>
</blockquote>
<p>(Computing the largest eigenvalue of the Laplacian is equivalent to the problem of solving a weaker version of the Goemans-Williamson SDP relaxation of Max Cut, in which, instead of requiring each vector to be of length one, you want the sum of the squares of the norms to be |V|.)</p>

CC BY-SA 2.5
2011-02-02T02:40:45.903Z
That's a nice question.
Suresh Venkat
CC BY-SA 2.5
2011-02-02T22:20:28.617Z
To understand PST-style algorithms for packing problems it is good to look at algorithms for approximately solving the multicommodity flow problem which is where PST evolved from. Neal Young's paper describes set cover in detail. Ihttp://www.cs.ucr.edu/~neal/non_arxiv/SODA_1995_170.pdf. I thought Arora-Kale-Hazan's survey also makes the connection between the experts framework and packing/covering solvers explicit.
Chandra Chekuri
CC BY-SA 3.0
2011-09-04T17:00:20.180Z
@ChandraChekuri: It's rather delayed, but I'm wondering if you should make this an answer ?
Suresh Venkat
CC BY-SA 3.0
2012-11-03T17:47:33.140Z
FWIW, for some notes expanding on the SODA paper @ChandraChekuri mentioned, see http://greedyalgs.info/blog/about/ .
Neal Young
CC BY-SA 3.0
2018-03-05T14:11:54.840Z
Updated link: http://algnotes.info/on/obliv/
Neal Young
CC BY-SA 4.0
2023-09-15T00:36:47.143Z
@NealYoung in the algnotes, there is a room for comments, but it does not work - it gives an error "nonce verification failed".
Erel Segal-Halevi
CC BY-SA 4.0
2023-09-15T01:02:44.547Z
Thanks for pointing that out.  It worked 10 years ago :-).  Bit-rot I guess.  I should disable comments there, as even when they were working I don't think they were used.  Stackexchange seems to be a better place for discussion.
Neal Young
CC BY-SA 4.0
2023-09-15T09:00:31.607Z
@NealYoung not sure if that's the right place, but here are some typos I noted while reading https://algnotes.info/on/background/lagrangian-relaxation-example/ :

In page 1, in the algorithm, in line 3, "/ c_e" is typed twice. Is this a typo?
In page 2, in the proof sketch, x(e) is used but it is not previously defined. Should it be f(e)?
In page 5, "finding an approximately maximum-size fractional set cover"  - should it be "minimum-size"?
Erel Segal-Halevi
CC BY-SA 4.0
2023-09-24T02:08:49.533Z
@ErelSegal-Halevi, in Page 1 if I recall correcetly the two occurrences $/c_e$ are correct (I could be wrong, though).  Yes in p 2 $x(e)$ should be $f(e)$ and in page 5 "maximum" should be "minimum".  Thanks.
Neal Young
<ds.algorithms><approximation-algorithms><linear-programming><primal-dual><semidefinite-programming>
Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers
Luca Trevisan
# Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers

(Asked by: username_0 on 2011-02-02)

I would like to understand how the Arora-Kale SDP solver approximates the Goemans-Williamson relaxation in nearly linear time, how the Plotkin-Shmoys-Tardos solver approximates fractional "packing" and "covering" problems in nearly linear time, and how the algorithms are instantiations of the "learning from experts" abstract framework.

Kale's thesis has an excellent presentation, but I find it very difficult to directly jump into the abstract framework, and I would prefer to start from an example of a simple problem for which it's absolutely obvious what to do, and then move to more general problems, progressively adding "features" to the algorithm and to its analysis.

For example:

> How does Plotkin-Shmoys solve the linear programming relaxation of unweighted vertex cover? Weighted vertex cover? Set cover? Bipartite matching?
>
> What is the simplest example in which the Arora-Kale algorithm is doing something interesting? How does it compute the largest eigenvalue of the Laplacian of a graph?

(Computing the largest eigenvalue of the Laplacian is equivalent to the problem of solving a weaker version of the Goemans-Williamson SDP relaxation of Max Cut, in which, instead of requiring each vector to be of length one, you want the sum of the squares of the norms to be |V|.)

**Tags:** ds.algorithms, approximation-algorithms, linear-programming, primal-dual, semidefinite-programming
> **Comments:**
> **username_1**: That's a nice question.  
> **username_2**: To understand PST-style algorithms for packing problems it is good to look at algorithms for approximately solving the multicommodity flow problem which is where PST evolved from. Neal Young's paper describes set cover in detail. Ihttp://www.cs.ucr.edu/~neal/non_arxiv/SODA_1995_170.pdf. I thought Arora-Kale-Hazan's survey also makes the connection between the experts framework and packing/covering solvers explicit.  
> **username_1**: @ChandraChekuri: It's rather delayed, but I'm wondering if you should make this an answer ?  
> **username_3**: FWIW, for some notes expanding on the SODA paper @ChandraChekuri mentioned, see http://greedyalgs.info/blog/about/ .  
> **username_3**: Updated link: http://algnotes.info/on/obliv/  
> **username_4**: @NealYoung in the algnotes, there is a room for comments, but it does not work - it gives an error "nonce verification failed".  
> **username_3**: Thanks for pointing that out.  It worked 10 years ago :-).  Bit-rot I guess.  I should disable comments there, as even when they were working I don't think they were used.  Stackexchange seems to be a better place for discussion.  
> **username_4**: @NealYoung not sure if that's the right place, but here are some typos I noted while reading https://algnotes.info/on/background/lagrangian-relaxation-example/ :  In page 1, in the algorithm, in line 3, "/ c_e" is typed twice. Is this a typo? In page 2, in the proof sketch, x(e) is used but it is not previously defined. Should it be f(e)? In page 5, "finding an approximately maximum-size fractional set cover"  - should it be "minimum-size"?  
> **username_3**: @ErelSegal-Halevi, in Page 1 if I recall correcetly the two occurrences $/c_e$ are correct (I could be wrong, though).  Yes in p 2 $x(e)$ should be $f(e)$ and in page 5 "maximum" should be "minimum".  Thanks.  

---

## 1 answers

### Answer by username_3 on 2012-11-19. Score: 27

Luca, since a year has passed, you probably have researched your own
answer. I'm answering some of your questions here just for the
record. I review some Lagrangian-relaxation algorithms for the
problems you mention, and sketch the connection to learning (in
particular, following expert advice). I don't comment here on SDP
algorithms.

Note that the particular algorithms that you mention do not run in
nearly linear time. (There is a nearly linear-time algorithm for
*explicitly* given packing or covering problems. See
[Beating Simplex for Fractional Packing and Covering Linear Programs](http://arxiv.org/abs/0801.1987).)
The algorithms you have in mind typically have variants that run in a
nearly linear number of *iterations*, but each iteration typically
requires at least linear time as well. I discuss some of these
algorithms below.

### Some useful functions

Before we start, here are some functions that we will use in the proof sketches.
(If you are interested in the algorithms, but not the proof details, you can skip ahead.)
For any vector $y$, define $\mbox{Lmax}(y)$ to be $\ln \sum\_i \exp(y\_i)$.
This function is an upper bound on $\max\_i y\_i$:
$$\max\_i y\_i ~\le~ \mbox{Lmax}(y) ~\le~ \max\_i y\_i + \ln m.$$
Analogously, define $\mbox{Lmin}(y)$ to be $-\mbox{Lmax}(-y)$,
a lower bound on $\min\_i y\_i$.

For convenience in what follows,
we use $g(y)$ to denote the gradient $\nabla \mbox{Lmin}(y)$ of Lmin.
We use $G(y)$ to denote the gradient $\nabla \mbox{Lmax}(y)$ of Lmax.

Explicitly, $g\_i(y)$ is $\exp(-y\_i)/\sum\_{i'} \exp(-y\_{i'})$
while $G\_i(y)$ is $\exp(y\_i)/\sum\_{i'} \exp(y\_{i'})$.

Lmin and Lmax are *smooth* in the following sense:
for any vectors $d\in[0,\varepsilon]^n$ and $y\in R^n$,
$$\mbox{Lmin}(y+d) ~\ge~ \mbox{Lmin}(y)
~+~ (1-O(\varepsilon))\, d \cdot g(y)$$
and
$$\mbox{Lmax}(y+d) ~\le~ \mbox{Lmax}(y)
~+~ (1+O(\varepsilon))\, d \cdot G(y).$$

Note that both of the gradients have 1-norm equal to 1:
$|G(y)| = |g(y)| = 1$. (Throughout we use $|z|$ to denote the 1-norm.)

Note also that, for a matrix $A$,
the gradient of the function $x\mapsto \mbox{Lmin}(Ax)$ with respect to $x$
is (by the chain rule) $(g(Ax))^T A$.
More explicitly, the partial derivative of the function with respect to $x\_j$
is $\sum\_i A\_{ij} \exp(-A\_i x) / \sum\_i \exp(-A\_i x)$.
Likewise, the partial derivative of Lmax$(Ax)$
with respect to $x\_j$ is $\sum\_i A\_{ij} \exp(A\_i x)/\sum\_i \exp(A\_i x)$.

### Fractional Set Cover

Fix a Set-Cover instance.
Let $A$ denote the element/set incidence matrix.
Thus, $A\_{es} = 1$ if $e\in s$, else 0,
and $A\_e x$ is the extent that fractional cover $x$ covers element $e$.

The LP is $\min\{ |x| : A x \ge 1; x \ge 0\}$.
Given $\varepsilon\in (0,1)$, the algorithm is

---

1. Initialize all $x\_s = 0$. Let $N=\log(n)/\varepsilon$.
2. Repeat until $\min\_e A\_e x \ge N$:

   2.1. Choose $s$ maximizing the partial derivative of Lmin$(Ax)$ w.r.t. $x\_s$.  
   (Explicitly, choose $s$ maximizing $\sum\_{e\in s} \exp(-\sum\_{s'\ni e} x\_{s'})$.)

   2.2. Increase $x\_s$ by $\varepsilon$.
3. Return $x/\min\_{e} A\_e x$.

---

The algorithm returns a $(1+O(\varepsilon))$ approximate solution
in $O(|x^\*|\log(n)/\varepsilon^2)$ iterations, where $n$ is the number of elements
and $x^\*$ is the optimal fractional set cover (trivially $|x^\*|\le n$).
(A similar algorithm appears in [the paper Chandra mentioned](http://www.cs.ucr.edu/~neal/non_arxiv/SODA_1995_170.pdf).
Vertex Cover is of course a special case.)

(**Remark:** Note that the iteration bound does not depend on the number
of sets, just the number of elements. Thus, the algorithm can be used
with an implicitly defined set system, as long as, given weights on the
elements, one can efficiently find a set of maximum (or near-maximum) total weight.
This kind of oracle is the same as the separation oracle required to apply
the ellipsoid algorithm to the *dual* problem. For packing problems such
as set packing, you need an oracle that, given weights on the elements,
returns a set *minimizing* the total weight. For problems such as
multi-commodity flow, you might, for example, need to find a path
minimizing the sum of some given edge weights.)

Here's a sketch of the proof of the performance guarantee.
In each iteration, the partial derivative w.r.t. the chosen $s$
is at least $1/|x^\*|$, where $x^\*$ is the optimal fractional set cover.

(To see why, recall that the gradient of Lmin$(Ax)$ with respect to $x$ is $(g(Ax))^T A$.
If we were to choose a set $s'$ at random from the distribution $x^\*/|x^\*|$,
the expected value of the partial derivative with respect to $x\_{s'}$
would thus be $(g(Ax))^T \,A x^\*/|x^\*|$.
Since $Ax^\* \ge 1$, this is at least $|g(Ax)|/|x^\*|$.
Since $|g(Ax)|=1$, this is at least $1/|x^\*|$.
Thus, there must exist some $s$ giving partial derivative at least $1/|x^\*|$.
Since the algorithm chooses $x\_s$ in each iteration to *maximize*
the partial derivative, it achieves a partial derivative of at least $1/|x^\*|$.)

Then, the step size $\varepsilon$ is chosen just small enough so that
no coordinate of $A x$ increases by more than $\varepsilon$.
Thus, because of the smoothness of Lmin, increasing $x\_s$
to $x\_s+\varepsilon$ increases $\mbox{Lmin}(Ax)$ by at least
$(1-O(\varepsilon))\varepsilon/|x^\*|$.

In this way, the algorithm maintains the invariant
$$\mbox{Lmin}(Ax) \ge (1-O(\varepsilon)) |x|/|x^\*| - \ln n.$$
(Note that Lmin$(\overline 0)$ equals $\ln n$.)

At termination, in the invariant, the $\ln n$ term is $O(\varepsilon)$ times the left-hand side,
so by calculation one gets $\min\_e A\_e x \ge (1-O(\varepsilon)) |x|/|x^\*|$.
After the normalization in the last line of the algorithm,
this implies $|x| \le (1+O(\varepsilon))|x^\*|$.

FWIW, the inequalities involved in proving the invariant are essentially
the same as those involved in proving the Chernoff bound.
(In fact, this algorithm can be derived by applying the
method of conditional probabilities to a randomized-rounding
scheme that repeatedly samples sets from the distribution $x^\*/|x^\*|$
(with replacement), increasing $x\_s$ for each sampled set $s$.
This derandomization of that gives the algorithm:
the underlying invariant is just that the pessimistic estimator stays below 1.
The exponential penalties in the pessimistic estimator come from the
using the Chernoff bound in the analysis of the rounding scheme.
This basic idea is explained further in [the paper Chandra mentioned](http://www.cs.ucr.edu/~neal/non_arxiv/SODA_1995_170.pdf).)

### Fractional Weighted Set Cover (and general fractional Covering)

To handle problems such as Weighted Set Cover *efficiently*,
we modify the algorithm to use non-uniform increments
(an idea due to [Garg and Konemann](http://scholar.google.com/scholar?cluster=735294650310145635&hl=en&as_sdt=0,5)).

The LP is $\min\{ c\cdot x : (\forall e) \sum\_{s\ni e} x\_s \ge 1\}$,
where $e$ ranges over the elements, $s$ ranges over the sets,
and all variables are non-negative.
To present the algorithm, first rewrite the problem as a general covering problem.
Let $A\_{es} = 1/c\_s$ for $e\in s$ and $A\_{es} = 0$ otherwise.
Then (with a change of variables, scaling each $x\_s$ by $c\_s$),
the LP is $\min\{ |x| : A x \ge 1; x \ge 0\}$,
which we can view as a general covering LP.
Here is the algorithm:

---

1. Initialize all $x\_s = 0$. Let $N=\log(n)/\varepsilon$.
2. Repeat until all covering constraints have been deleted:

   2.1. Choose $s$ maximizing the partial derivative of Lmin$(Ax)$ w.r.t. $x\_s$.  
   (Explicitly, choose $s$ maximizing $\sum\_{e\in s} \exp({-\sum\_{s'\ni e} x\_{s'}})/c\_s$.)

   2.2. Increase $x\_s$ by $\delta$, where $\delta$ is chosen maximally such that, for every remaining covering constraint $e$, the increase in $A\_e \cdot x$ is at most $\varepsilon$.

   2.3 Delete all covering constraints $e$ such that $A\_e\cdot x \ge N$.
3. Return $x/\min\_e A\_e\cdot x$.

---

The algorithm returns a $(1+O(\varepsilon))$-approximate solution
in $O(n\log(n)/\varepsilon^2)$ iterations, where $n$ is the number of covering constraints.
(Each iteration increases some remaining $A\_e x$ by $\varepsilon$; this can happen
only $N/\varepsilon$ times to a constraint before it is deleted.)
The proof of correctness is via essentially the same invariant as for Set Cover.

Weighted Vertex Cover is a special case.

### Maximum Fractional Bipartite Matching

Given a graph $G=(U,W,E)$,
the natural LP for the problem is $\max\{|x| : \forall v.\, \sum\_{e\ni v} x\_e \le 1\}$.

In matrix representation, this is a packing LP $\max\{|x| : Ax \le 1; x \ge 0\}$
with 0-1 coefficients ($A\_{ve} = 1$ if $v\in e$).
Such problems do not require non-uniform increments, so a simple algorithm analogous to the unweighted Set Cover algorithm (but for packing) will do:

---

1. Initialize all $x\_e = 0$. Let $N=\log(n)/\varepsilon$.
2. While $A x < N$:

   2.1. Choose $e$ minimizing the partial derivative of Lmax$(Ax)$ w.r.t. $x\_e$.  
   (Explicitly, choose $e$ to minimize $\sum\_{v\in e} \exp(\sum\_{e'\ni v} x\_{e'})$.)

   2.2. Increase $x\_e$ by $\varepsilon$.
3. Return $x/\max\_{v} A\_v x$.

---

The algorithm returns a $(1-O(\varepsilon))$-approximate solution in $O(n\log(n)/\varepsilon^2)$ iterations.
(This is because each iteration increases $|x|$ by $\varepsilon$,
and finally, before normalization, $|x| = O(N n)$.)

Just for fun, here is a curious alternative algorithm for Perfect Bipartite Matching.
Recall that $G=(U,W,E)$. Let $n=|U|=|W|$.

---

1. Initialize all $x\_e = 0$. Let $N=4\ln(n)/\varepsilon$.
2. Repeat $n\,N$ times:

   2.1. Choose $u$ uniformly at random from $U$.  
   2.2. Choose $w$ such that $(u,w)\in E$ minimizing $\sum\_{e\ni w} x\_e$.  
   2.3. Increase $x\_{uw}$ by $\varepsilon$.
3. Return $x/N$.

---

If $G$ has a perfect matching, the algorithm returns
an $x$ such that $|x|=n$, and, with high probability,
for all vertices $u\in U$, $1-O(\varepsilon) \le \sum\_{e\ni u} x\_e \le 1+O(\varepsilon)$,
and for all vertices $w\in W$, $\sum\_{e\ni w} x\_e \le 1+O(\varepsilon)$.
If you are interested in the details of the proof, please ask...

### Mixed Packing and Covering

You may have asked about bipartite matching hoping for an example
of a *mixed* packing and covering problem, that is, one of the form
$$\exists x?~ Px \le p; Cx \ge c; x \ge 0.$$
Here's one algorithm for such problems.
First, normalize so that $p=\overline 1$ and $c=\overline 1$.

Let $m$ be the number of constraints (rows in $P$ plus rows in $C$).

---

1. Initialize all $x\_j = 0$. Let $N=2\ln(m)/\varepsilon$.
2. While $P x < N$:

   2.1. Choose $j$ so that the partial derivative of Lmax$(Px)$ with respect to $x\_j$ is at most the partial derivative of Lmin$(Cx)$ with respect to $x\_j$. (Explicitly, choose $j$ such that $$\frac{\sum\_i P\_{ij} \exp(P\_i x)}{\sum\_{i}\exp(P\_i x)} \le \frac{\sum\_i C\_{ij} \exp(-C\_i x)}{\sum\_{i}\exp(-C\_i x)}.)$$

   2.2. Increase $x\_j$ by $\delta$, where $\delta$ is chosen maximally such that no constraint $P\_i x$ or remaining constraint $C\_i x$ increases by more than $\varepsilon$.

   2.3. Delete all covering constraints $i$ such that $C\_i x \ge N$.
3. Return $x/\max\_i P\_i x$.

---

Assuming the given problem is feasible, the algorithm
returns an $x$ such that $Px\le 1$
and $Cx\ge 1-O(\varepsilon)$.
The number of iterations is $O(m\ln(m)/\varepsilon^2)$,
because each iteration increases some constraint by $\varepsilon$,
and this can happen for each constraint at most $N$ times.

The proof of correctness is via the invariant
$$\mbox{Lmax}(Px) \le 2\ln(m) + (1+O(\varepsilon)) \mbox{Lmin}(Cx).$$
The invariant implies
$$\max Px \le 2\ln(m) + (1+O(\varepsilon)) \min Cx.$$
At termination the left-hand side is $\Omega(\log(m)/\varepsilon)$,
proving the performance guarantee.

In Step 2.1, the desired $j$ must exist as long as the original problem is feasible.
(This is because, for any *feasible* $x^\*$, and any $x$,
if we were to choose a random $j'$ from the distribution $x^\*/|x^\*|$,
the expected value of the partial derivative of Lmax$(Px)$ with respect to $x\_{j'}$
would be at most $1/|x^\*|$ (see the previous proof sketch for Set Cover).
Likewise, the expected value of the partial derivative of Lmin$(Cx)$ with respect to $x\_{j'}$
would be at least $1/|x^\*|$.
Thus, there is an $j$ such that the partial derivative of Lmax$(Px)$ with respect to $x\_{j'}$
is at most the partial derivative of Lmin$(Cx)$.)

Then the invariant is maintained in each iteration because,
by the choice of $x\_j$ and $\delta$,
and the smoothness of Lmin and Lmax,
increasing $x\_j$ to $x\_j+\delta$
increases Lmax$(Px)$
by at most $1+O(\varepsilon)$
times the increase in Lmin$(Cx)$.

### Learning (following experts / boosting)

One reference for understanding this connection is
[Adaptive game playing using multiplicative weights](http://scholar.google.com/scholar?cluster=4120237815378119841&hl=en&as_sdt=0,5&as_vis=1), by Freund and Schapire.
Here is a quick summary to give the technical idea.

Consider the following repeated game. In each round $t$:

1. You choose a probability distribution $p^t$ on $[n]$ (the $n$ so-called *experts*).
2. Knowing $p^t$, the adversary then chooses a payoff vector $a^t\in [0,1]^{n}$.
3. You receive payoff $p^t\cdot a^t$ for the round.

The game stops after some number of rounds.
Your goal is to minimize your regret
in comparison to any single expert (i.e., pure strategy) $i$.
That is, your goal is to minimize $(\max\_i \sum\_t a^t\_i) - \sum\_t p^t\cdot a^t$.

Fix any $\varepsilon>0$.
Let vector $y^t$ denote $\varepsilon \sum\_{s \le t} a^s$, that is,
$\varepsilon$ times the vector sum of the payoff vectors up to time $t$.
Recall that $G(y)$ is the gradient of Lmax$(y)$.

Here's the basic strategy we will analyze:
*On round $t$, choose $p^t$ to be $G(y^{t-1})$.*

By inspection, this gives you payoff $a^t \cdot G(y^{t-1})$ in round $t$.

Because of the smoothness property of $F$,
$$\mbox{Lmax}(y^t) \le \mbox{Lmax}(y^{t-1}) + (1+O(\varepsilon)) \varepsilon a^t \cdot G(y^{t-1}).$$
That is, in each round, $\mbox{Lmax}(y^t)$ can't increase by more than $\varepsilon(1+O(\varepsilon))$ times your payoff.
Since $\mbox{Lmax}(\overline 0) = \ln n$,
this maintains the invariant that $\mbox{Lmax}(y^t)$
is at most your total payoff times $\varepsilon(1+O(\varepsilon)$,
plus $\ln(n)$.
On the other hand, your regret in comparison to the best expert $i$
is $\max\_i \sum\_t a^t\_i$, i.e., $\varepsilon^{-1} \max\_i y^t\_i$,
which is in turn at most $\varepsilon^{-1} \mbox{Lmax}(y^t)$.

Thus, *your regret is at most $\varepsilon^{-1} \ln(n)$, plus $O(\varepsilon)$ times your total payoff.*

**Remark:** I think, as Freund and Schapire point out, a "boosting" algorithm (in learning theory) is also implicit in this analysis. See their paper for more details.

**Minimizing total payoff**

You can derive a similar strategy for the setting where the goal is to *minimize*,
rather than maximize, the total payoff.
Your regret, which you still want to minimize, is $\sum\_t p^t\cdot a^t - \min\_i a^t\_i$.
In that case, the corresponding strategy is to choose $p^t$ to be the gradient of $\mbox{Lmin}(y^t)$.
With this strategy your regret is again at most
$\varepsilon^{-1} \ln n$ plus $O(\varepsilon)$ times your total payoff.

**Connection to Lagrangian-relaxation algorithms**

To see the connection to Lagrangian-relaxation algorithms, fix a Set-Cover instance.
Consider the latter type of game (with the goal of minimizing payoff),
where the experts correspond to the elements $e$ of your set system.
In each round, choose the probability distribution $p^t$
to be the gradient of Lmin$(y^t)$ as above,
and have the adversary choose the payoff vector $a^t$ as a function of $p^t$ as follows:
*choose the set $s^t$ maximizing $\sum\_{e\in s} p^t\_e$,
then let $a^t\_e = 1$ if $e\in s^t$, and $a^t\_e = 0$ otherwise.*

Given the correct stopping condition (discussed below),
this process gives you exactly the Set-Cover algorithm discussed at the start.

The performance guarantee of the algorithm follows from the regret bound as follows.
Let $X\_s$ be the number of times the adversary chose set $s$ during the play.
Let $x^\*$ be the optimal fractional set cover.
Let $T=|X\_s|$ be the number of rounds played.
The regret bound implies
$$\textstyle \sum\_t a^t\cdot p^t \le \varepsilon^{-1}\ln(m) + \min\_e \sum\_t a\_e^t.$$

Using the definition of $a^t$, the $t$th payoff
(the $t$th term in the sum on the left)
equals $\sum\_{e\in s^t} p^t\_e$.
The adversary chose $s^t$ to minimize this payoff.
If the adversary had instead chosen $s^t$ randomly
from the distribution $x^\*/|x^\*|$, the expectation of
the payoff would have been
$$ \sum\_s \frac{x^\*\_s}{|x^\*|} \sum\_{e\in s} p^t\_e
~=~
\frac{1}{|x^\*|} \sum\_e p^t\_e \sum\_{s\ni e} x^\*\_s
~\ge~
\frac{1}{|x^\*|} \sum\_e p^t\_e
~=~
\frac{1}{|x^\*|}.$$
(Above we use that $\sum\_{s\ni e} x^\*\_s \ge 1$ for all $e$, and $|p^t| = 1$.)
Since each payoff is at least $1/|x^\*|$, the regret bound implies
$$ \frac{T}{|x^\*|} \le \varepsilon^{-1}\ln(m) + \min\_e \sum\_t a\_e^t.$$
By the definition of $X$,
we have $|X| = T$ (each round chooses one set),
and $\sum\_t a\_e^t = \sum\_e [e\in s^t] = \sum\_{s\ni e} X\_s$,
giving
$$\frac{|X|}{|x^\*|} \le \varepsilon^{-1}\ln(m) +\min\_e \sum\_{s\ni e} X\_s.$$
We make the process stop when $\min\_e \sum\_{s\ni e} X\_s = \Omega(\varepsilon^{-2}\ln m)$,
so then (rearranging terms)
$$\frac{|X|}{\min\_e \sum\_{s\ni e} X\_s}~ \le~ (1+O(\varepsilon)|x^\*|.$$
That is, normalizing $X$ gives a fractional set cover
of size at most $(1+O(\varepsilon))$ times optimum.

**Remark:** In a sense, this learning theory interpretation
generalizes the algorithmic interpretation. However, some
of the algorithmic techniques necessary for efficiency
(such as non-uniform increments and dropping satisfied
covering constraints) don't seem to carry over into the
learning theory setting naturally. Likewise, algorithms for
*mixed* packing and covering LPs (e.g. [these](http://arxiv.org/abs/cs/0205039))
don't seem to have natural analogues in the learning-theory setting.

> **Comments:**
> **username_1**: That is quite the answer !!  
> **username_3**: Thanks.  Probably overdid it.  Am interested in feedback: how to present these ideas accessibly, what else to include...  
> **username_4**: You call the algorithm for fractional set cover a "Lagrangian Relaxation algorithm". Can you explain the connection to [the definition of Lagrangian Relaxation in Wikipedia](https://en.wikipedia.org/wiki/Lagrangian_relaxation)? In particular, what are the Lagrangian coefficients $\lambda$ in the set cover example? And what are the constraints that are moved into the objective function?  
> **username_3**: I use that term informally to mean that the algorithm replaces multiple constraints by a single weighted combination of those constraints (typically giving more weight to constraints that are "closer to violation").  I think the formal term for this particular kind of Lagrangian relaxation, where a collection of constraints is replaced by a single constraint, instead of being replaced by a function that is incorporated into the objective,  is "surrogate duality".  The basic technical challenge in each case (e.g. in MWU algorithms) is how to compute the weight assigned to each constraint.  
> **username_4**: You write "The algorithm can be used with an implicitly defined set system, as long as, given weights on the elements, one can efficiently find a set of maximum (or near-maximum) total weight"; what are examples of approximation algorithms to this problem, for some implicitly-defined set-systems?  
> **username_3**: @ErelSegal-Halevi, I haven't thought much about specific applications, but here's one I just made up.  Given a directed graph, two vertices S and T, and a collection Q of vertices, consider the problem of finding a minimum number of S->T paths that collectively contain all vertices.  You can relax the latter covering constraints as follows: given a weighting of the vertices, find an S-T path that maximizes the weights of the vertices on the path.  If you can, say, c-approximate the latter problem, then you can c'-approximate the fractional relaxation of the original one,  for any c' > c.  

---

