
In a recent breakthrough, Paz and Schwartzman (SODA'17) presented a
singlepass ($2+\epsilon$)approximation algorithm for the maximum weight
matching problem in the semistreaming model. Their algorithm uses $O(n\log^2
n)$ bits of space, for any constant $\epsilon>0$.
We present two simplified and more intuitive analyses, for essentially the
same algorithm, which also improve the space complexity to the optimal bound of
$O(n\log n)$ bits  this is optimal as the output matching requires
$\Omega(n\log n)$ bits. Our analyses rely on a simple use of the primaldual
method and a simple accounting method.

Distributed graph algorithms that separately optimize for either the number
of rounds used or the total number of messages sent have been studied
extensively. However, algorithms simultaneously efficient with respect to both
measures have been elusive. For example, only very recently was it shown that
for Minimum Spanning Tree (MST), an optimal message and round complexity is
achievable (up to polylog terms) by a single algorithm in the CONGEST model of
communication.
In this paper we provide algorithms that are simultaneously round and
messageoptimal for a number of wellstudied distributed optimization problems.
Our main result is such a distributed algorithm for the fundamental primitive
of computing simple functions over each part of a graph partition. From this
algorithm we derive round and messageoptimal algorithms for multiple
problems, including MST, Approximate MinCut and Approximate Single Source
Shortest Paths, among others. On general graphs all of our algorithms achieve
worstcase optimal $\tilde{O}(D+\sqrt n)$ round complexity and $\tilde{O}(m)$
message complexity. Furthermore, our algorithms require an optimal
$\tilde{O}(D)$ rounds and $\tilde{O}(n)$ messages on planar, genusbounded,
treewidthbounded and pathwidthbounded graphs.

We present a simple randomized reduction from fullydynamic integral matching
algorithms to fullydynamic "approximatelymaximal" fractional matching
algorithms. Applying this reduction to the recent fractional matching algorithm
of Bhattacharya, Henzinger, and Nanongkai (SODA 2017), we obtain a novel result
for the integral problem. Specifically, our main result is a randomized
fullydynamic $(2+\epsilon)$approximate integral matching algorithm with small
polylog worstcase update time. For the $(2+\epsilon)$approximation regime
only a \emph{fractional} fullydynamic $(2+\epsilon)$matching algorithm with
worstcase polylog update time was previously known, due to Bhattacharya et
al.~(SODA 2017). Our algorithm is the first algorithm that maintains
approximate matchings with worstcase update time better than polynomial, for
any constant approximation ratio. As a consequence, we also obtain the first
constantapproximate worstcase polylogarithmic update time maximum weight
matching algorithm.

We study the classic Bin Packing problem in a fullydynamic setting, where
new items can arrive and old items may depart. We want algorithms with low
asymptotic competitive ratio \emph{while repacking items sparingly} between
updates. Formally, each item $i$ has a \emph{movement cost} $c_i\geq 0$, and we
want to use $\alpha \cdot OPT$ bins and incur a movement cost $\gamma\cdot
c_i$, either in the worst case, or in an amortized sense, for $\alpha, \gamma$
as small as possible. We call $\gamma$ the \emph{recourse} of the algorithm.
This is motivated by cloud storage applications, where fullydynamic Bin
Packing models the problem of data backup to minimize the number of disks used,
as well as communication incurred in moving file backups between disks. Since
the set of files changes over time, we could recompute a solution periodically
from scratch, but this would give a high number of disk rewrites, incurring a
high energy cost and possible wear and tear of the disks. In this work, we
present optimal tradeoffs between number of bins used and number of items
repacked, as well as natural extensions of the latter measure.

Motivated by Internet targeted advertising, we address several ad allocation
problems. Prior work has established these problems admit no randomized online
algorithm better than $(1\frac{1}{e})$competitive
(\cite{karp1990optimal,mehta2007adwords}), yet simple heuristics have been
observed to perform much better in practice. We explain this phenomenon by
studying a generalization of the boundeddegree inputs considered by Buchbinder
et al.~\cite{buchbinder2007online}, graphs which we call $(k,d)bounded$. In
such graphs the maximal degree on the online side is at most $d$ and the
minimal degree on the offline side is at least $k$. We prove that for such
graphs, these problems' natural greedy algorithms attain competitive ratio
$1\frac{d1}{k+d1}$, tending to \emph{one} as $d/k$ tends to zero. We prove
this bound is tight for these algorithms.
Next, we develop deterministic primaldual algorithms for the above problems
achieving competitive ratio $1(1\frac{1}{d})^k>1\frac{1}{e^{k/d}}$, or
\emph{exponentially} better loss as a function of $k/d$, and strictly better
than $1\frac{1}{e}$ whenever $k\geq d$. We complement our lower bounds with
matching upper bounds for the vertexweighted problem. Finally, we use our
deterministic algorithms to prove by dualfitting that simple randomized
algorithms achieve the same bounds in expectation. Our algorithms and analysis
differ from previous ad allocation algorithms, which largely scale bids based
on the spent fraction of their bidder's budget, whereas we scale bids according
to the number of times the bidder could have spent as much as her current bid.
Our algorithms differ from previous online primaldual algorithms, as they do
not maintain dual feasibility, but only primaltodual ratio, and only attain
dual feasibility upon termination. We believe our techniques could find
applications to other wellbehaved online packing problems.