
Suppose a set of requests arrives online: each request gives some value $v_i$
if accepted, but requires using some amount of each of $d$ resources. Our cost
is a convex function of the vector of total utilization of these $d$ resources.
Which requests should be accept to maximize our profit, i.e., the sum of values
of the accepted demands, minus the convex cost?
We consider this problem in the randomorder a.k.a. secretary model, and show
an $O(d)$competitive algorithm for the case where the convex cost function is
also supermodular. If the set of accepted demands must also be independent in a
given matroid, we give an $O(d^3 \alpha)$competitive algorithm for the
supermodular case, and an improved $O(d^2\alpha)$ if the convex cost function
is also separable. Here $\alpha$ is the competitive ratio of the best algorithm
for the submodular secretary problem. These extend and improve previous results
known for this problem. Our techniques are simple but use powerful ideas from
convex duality, which give clean interpretations of existing work, and allow us
to give the extensions and improvements.

We study the problem of deleting the smallest set $S$ of vertices (resp.\
edges) from a given graph $G$ such that the induced subgraph (resp.\ subgraph)
$G \setminus S$ belongs to some class $\mathcal{H}$.
We consider the case where graphs in $\mathcal{H}$ have treewidth bounded by
$t$, and give a general framework to obtain approximation algorithms for both
vertex and edgedeletion settings from approximation algorithms for certain
natural graph partitioning problems called $k$Subset Vertex Separator and
$k$Subset Edge Separator, respectively.
For the vertex deletion setting, our framework combined with the current best
result for $k$Subset Vertex Separator, yields a significant improvement in the
approximation ratios for basic problems such as $k$Treewidth Vertex Deletion
and Planar$F$ Vertex Deletion. Our algorithms are simpler than previous works
and give the first uniform approximation algorithms under the natural
parameterization.
For the edge deletion setting, we give improved approximation algorithms for
$k$Subset Edge Separator combining ideas from LP relaxations and important
separators. We present their applications in boundeddegree graphs, and also
give an APXhardness result for the edge deletion problems.

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.

Dropletbased microfluidics turned out to be an efficient and adjustable
platform for digital analysis, encapsulation of cells, drug formulation, and
polymerase chain reaction. Typically, for most biomedical applications, the
handling of complex, nonNewtonian fluids is involved, e.g. synovial and
salivary fluids, collagen, and gel scaffolds. In this study we investigate the
problem of droplet formation occurring in a microfluidic Tshaped junction,
when the continuous phase is made of shear thinning liquids. At first, we
review in detail the breakup process providing extensive, sidebyside
comparisons between Newtonian and nonNewtonian liquids over unexplored ranges
of flow conditions and viscous responses. The nonNewtonian liquid carrying the
droplets is made of Xanthan solutions, a stiff rodlike polysaccharide
displaying a marked shear thinning rheology. By defining an effective Capillary
number, a simple yet effective methodology is used to account for the
sheardependent viscous response occurring at the breakup. The droplet size can
be predicted over a wide range of flow conditions simply by knowing the
rheology of the bulk continuous phase. Experimental results are complemented
with numerical simulations of purely shear thinning fluids using Lattice
Boltzmann models. The good agreement between the experimental and numerical
data confirm the validity of the proposed rescaling with the effective
Capillary number.

We present an extensive numerical study of the time irreversibility of the
dynamics of heavy inertial particles in threedimensional, statistically
homogeneous and isotropic turbulent flows. We show that the probability density
function (PDF) of the increment, $W(\tau)$, of a particle's energy over a
timescale $\tau$ is nonGaussian, and skewed towards negative values. This
implies that, on average, particles gain energy over a period of time that is
longer than the duration over which they lose energy. We call this
$\textit{slow gain}$ and $\textit{fast loss}$. We find that the third moment of
$W(\tau)$ scales as $\tau^3$, for small values of $\tau$. We show that the PDF
of powerinput $p$ is negatively skewed too; we use this skewness ${\rm Ir}$ as
a measure of the timeirreversibility and we demonstrate that it increases
sharply with the Stokes number ${\rm St}$, for small ${\rm St}$; this increase
slows down at ${\rm St} \simeq 1$. Furthermore, we obtain the PDFs of $t^+$ and
$t^$, the times over which $p$ has, respectively, positive or negative signs,
i.e., the particle gains or loses energy. We obtain from these PDFs a direct
and natural quantification of the the slowgain and fastloss of the particles,
because these PDFs possess exponential tails, whence we infer the
characteristic loss and gain times $t_{\rm loss}$ and $t_{\rm gain}$,
respectively; and we obtain $t_{\rm loss} < t_{\rm gain}$, for all the cases we
have considered. Finally, we show that the slowgain in energy of the particles
is equally likely in vortical or straindominated regions of the flow; in
contrast, the fastloss of energy occurs with greater probability in the latter
than in the former.

The BealeKatoMajda theorem contains a single criterion that controls the
behaviour of solutions of the $3D$ incompressible Euler equations. Versions of
this theorem are discussed in terms of the regularity issues surrounding the
$3D$ incompressible Euler and NavierStokes equations together with a
phasefield model for the statistical mechanics of binary mixtures called the
$3D$ CahnHilliardNavierStokes (CHNS) equations. A theorem of BKMtype is
established for the CHNS equations for the full parameter range. Moreover, for
this latter set, it is shown that there exists a Reynolds number and a bound on
the energydissipation rate that, remarkably, reproduces the $Re^{3/4}$ upper
bound on the inverse Kolmogorov length normally associated with the
NavierStokes equations alone. An alternative lengthscale is introduced and
discussed, together with a set of pseudospectral computations on a $128^{3}$
grid.

We study the problem of embedding shortestpath metrics of weighted graphs
into $\ell_p$ spaces. We introduce a new embedding technique based on lowdepth
decompositions of a graph via shortest paths. The notion of Shortest Path
Decomposition depth is inductively defined: A (weighed) path graph has shortest
path decomposition (SPD) depth $1$. General graph has an SPD of depth $k$ if it
contains a shortest path whose deletion leads to a graph, each of whose
components has SPD depth at most $k1$. In this paper we give an
$O(k^{\min\{\frac{1}{p},\frac{1}{2}\}})$distortion embedding for graphs of SPD
depth at most $k$. This result is asymptotically tight for any fixed $p>1$,
while for $p=1$ it is tight up to second order terms.
As a corollary of this result, we show that graphs having pathwidth $k$ embed
into $\ell_p$ with distortion $O(k^{\min\{\frac{1}{p},\frac{1}{2}\}})$. For
$p=1$, this improves over the best previous bound of Lee and Sidiropoulos that
was exponential in $k$; moreover, for other values of $p$ it gives the first
embeddings whose distortion is independent of the graph size $n$. Furthermore,
we use the fact that planar graphs have SPD depth $O(\log n)$ to give a new
proof that any planar graph embeds into $\ell_1$ with distortion $O(\sqrt{\log
n})$. Our approach also gives new results for graphs with bounded treewidth,
and for graphs excluding a fixed minor.

In the Steiner Forest problem, we are given a graph and a collection of
sourcesink pairs, and the goal is to find a subgraph of minimum total length
such that all pairs are connected. The problem is APXHard and can be
2approximated by, e.g., the elegant primaldual algorithm of Agrawal, Klein,
and Ravi from 1995.
We give a localsearchbased constantfactor approximation for the problem.
Local search brings in new techniques to an area that has for long not seen any
improvements and might be a step towards a combinatorial algorithm for the more
general survivable network design problem. Moreover, local search was an
essential tool to tackle the dynamic MST/Steiner Tree problem, whereas dynamic
Steiner Forest is still wide open.
It is easy to see that any constant factor local search algorithm requires
steps that add/drop many edges together. We propose natural local moves which,
at each step, either (a) add a shortest path in the current graph and then drop
a bunch of inessential edges, or (b) add a set of edges to the current
solution. This second type of moves is motivated by the potential function we
use to measure progress, combining the cost of the solution with a penalty for
each connected component. Our carefullychosen local moves and potential
function work in tandem to eliminate bad local minima that arise when using
more traditional local moves.

We study the combinatorial pure exploration problem BestSet in stochastic
multiarmed bandits. In a BestSet instance, we are given $n$ arms with unknown
reward distributions, as well as a family $\mathcal{F}$ of feasible subsets
over the arms. Our goal is to identify the feasible subset in $\mathcal{F}$
with the maximum total mean using as few samples as possible. The problem
generalizes the classical best arm identification problem and the top$k$ arm
identification problem, both of which have attracted significant attention in
recent years. We provide a novel instancewise lower bound for the sample
complexity of the problem, as well as a nontrivial sampling algorithm, matching
the lower bound up to a factor of $\ln\mathcal{F}$. For an important class of
combinatorial families, we also provide polynomial time implementation of the
sampling algorithm, using the equivalence of separation and optimization for
convex program, and approximate Pareto curves in multiobjective optimization.
We also show that the $\ln\mathcal{F}$ factor is inevitable in general
through a nontrivial lower bound construction. Our results significantly
improve several previous results for several important combinatorial
constraints, and provide a tighter understanding of the general BestSet
problem.
We further introduce an even more general problem, formulated in geometric
terms. We are given $n$ Gaussian arms with unknown means and unit variance.
Consider the $n$dimensional Euclidean space $\mathbb{R}^n$, and a collection
$\mathcal{O}$ of disjoint subsets. Our goal is to determine the subset in
$\mathcal{O}$ that contains the $n$dimensional vector of the means. The
problem generalizes most pure exploration bandit problems studied in the
literature. We provide the first nearly optimal sample complexity upper and
lower bounds for the problem.

Disorganized electrical activity in the heart leads to sudden cardiac death.
To what extent can this electrical turbulence be viewed as classical fluid
turbulence,which is an important central problem in modern physics? We
investigate,for the first time,via extensive DNSs,the statistical properties of
spiraland scrollwave turbulence in two and threedimensional excitable media
by using approaches employed in studies of classical turbulence. We use the
Panfilov and the AlievPanfilov mathematical models for cardiac tissue. We show
that once electricalwave turbulence has been initiated,there is a forward
cascade,in which spirals or scrolls form,interact,and break to yield a
turbulent state that is statistically steady and,far away from boundaries,is
statistically homogeneous and isotropic. For the transmembrane potential $V$
and the slow recovery variable $g$,which define our models,we define $E_V(k)$
and $E_g(k)$,the electricalwave analogs of the fluid energy spectrum $E(k)$ in
fluid turbulence. We show that $E_V(k)$ and $E_g(k)$ are spread out over
several decades in $k$. Thus spiral and scrollwave turbulence involves a wide
range of spatial scales. $E_V(k)$ and $E_g(k)$ show approximate power laws,in
some range of $k$, however,their exponents cannot be determined as accurately
as their fluidturbulence counterparts. The dimensionless ratio $L/\lambda$ is
a convenient control parameter like the Reynolds number for fluid
turbulence,where $L$ is the linear size of the domain and $\lambda$ the
wavelength of a plane wave in the medium. By comparing several other
statistical properties for spiral and scrollwave turbulence with their
fluidturbulence counterparts,we show that,although spiral and scrollwave
turbulence have some statistical properties like those of fluid
turbulence,overall these types of turbulence are special and differ in
important ways from fluid turbulence.

LowReynoldsnumber polymer solutions exhibit a chaotic behaviour known as
'elastic turbulence' when the Weissenberg number exceeds a critical value. The
twodimensional OldroydB model is the simplest constitutive model that
reproduces this phenomenon. To make a practical estimate of the resolution
scale of the dynamics requires an assumption that an attractor of the OldroydB
model exists : numerical simulations show that the quantities on which this
assumption is based are bounded. We estimate the Lyapunov dimension of this
assumed attractor as a function of the Weissenberg number by combining a
mathematical analysis of the model with direct numerical simulations.

We consider the problem of constructing optimal decision trees: given a
collection of tests which can disambiguate between a set of $m$ possible
diseases, each test having a cost, and the apriori likelihood of the patient
having any particular disease, what is a good adaptive strategy to perform
these tests to minimize the expected cost to identify the disease? We settle
the approximability of this problem by giving a tight $O(\log m)$approximation
algorithm. We also consider a more substantial generalization, the Adaptive TSP
problem. Given an underlying metric space, a random subset $S$ of cities is
drawn from a known distribution, but $S$ is initially unknown to uswe get
information about whether any city is in $S$ only when we visit the city in
question. What is a good adaptive way of visiting all the cities in the random
subset $S$ while minimizing the expected distance traveled? For this problem,
we give the first polylogarithmic approximation, and show that this algorithm
is best possible unless we can improve the approximation guarantees for the
wellknown group Steiner tree problem.

We perform a direct numerical simulation (DNS) of the forced, incompressible
twodimensional NavierStokes equation coupled with the FENEP equations for
the polymerconformation tensor. The forcing is such that, without polymers and
at low Reynolds numbers $\mbox{Re}$, the film attains a steady state that is a
square lattice of vortices and antivortices. We find that, as we increase the
Weissenberg number $\mbox{Wi}$, a sequence of nonequilibrium phase transitions
transforms this lattice, first to spatially distorted, but temporally steady,
crystals and then to a sequence of crystals that oscillate in time,
periodically, at low $\mbox{Wi}$, and quasiperiodically, for slightly larger
$\mbox{Wi}$. Finally, the system becomes disordered and displays spatiotemporal
chaos and elastic turbulence. We then obtain the nonequilibrium phase diagram
for this system, in the $\mbox{Wi}  \Omega$ plane, where $\Omega \propto
{\mbox{Re}}$, and show that (a) the boundary between the crystalline and
turbulent phases has a complicated, fractaltype character and (b) the
OkuboWeiss parameter $\Lambda$ provides us with a natural measure for
characterizing the phases and transitions in this diagram.

We consider the 3D CahnHilliard equations coupled to, and driven by, the
forced, incompressible 3D NavierStokes equations. The combination, known as
the CahnHilliardNavierStokes (CHNS) equations, is used in statistical
mechanics to model the motion of a binary fluid. The potential development of
singularities (blowup) in the contours of the order parameter $\phi$ is an
open problem. To address this we have proved a theorem that closely mimics the
BealeKatoMajda theorem for the $3D$ incompressible Euler equations [Beale et
al. Commun. Math. Phys., Commun. Math. Phys., ${\rm 94}$, $ 6166 ({\rm
1984})$]. By taking an $L^{\infty}$ norm of the energy of the full binary
system, designated as $E_{\infty}$, we have shown that
$\int_{0}^{t}E_{\infty}(\tau)\,d\tau$ governs the regularity of solutions of
the full 3D system. Our direct numerical simulations (DNSs), of the 3D CHNS
equations, for (a) a gravitydriven Rayleigh Taylor instability and (b) a
constantenergyinjection forcing, with $128^3$ to $512^3$ collocation points
and over the duration of our DNSs, confirm that $E_{\infty}$ remains bounded as
far as our computations allow.

In this paper, we study the set cover problem in the fully dynamic model. In
this model, the set of active elements, i.e., those that must be covered at any
given time, can change due to element arrivals and departures. The goal is to
maintain an algorithmic solution that is competitive with respect to the
current optimal solution. This model is popular in both the dynamic algorithms
and online algorithms communities. The difference is in the restriction placed
on the algorithm: in dynamic algorithms, the running time of the algorithm
making updates (called update time) is bounded, while in online algorithms, the
number of updates made to the solution (called recourse) is limited.
In this paper we show the following results: In the update time setting, we
obtain O(log n)competitiveness with O(f log n) amortized update time, and
O(f^3)competitiveness with O(f^2) update time. The O(log n)competitive
algorithm is the first one to achieve a competitive ratio independent of f in
this setting. In the recourse setting, we show a competitive ratio of O(min{log
n,f}) with constant amortized recourse. Note that this matches the best offline
bounds with just constant recourse, something that is impossible in the
classical online model.
Our results are based on two algorithmic frameworks in the fullydynamic
model that are inspired by the classic greedy and primaldual algorithms for
offline set cover. We show that both frameworks can be used for obtaining both
recourse and update time bounds, thereby demonstrating algorithmic techniques
common to these strands of research.

We present an extensive direct numerical simulation of statistically steady,
homogeneous, isotropic turbulence in twodimensional, binaryfluid mixtures
with airdraginduced friction by using the CahnHilliardNavierStokes
equations. We choose parameters, e.g., the surface tension, such that we have a
droplet of the minority phase moving inside a turbulent background of the
majority phase. We characterize the deformation of the droplet and show that it
displays multifractal dynamics. The probability distribution functions of the
components of the acceleration of the center of mass of the droplet exhibit
wide, nonGaussian tails. Our study reveals that the droplet enhances the
energy spectrum $E(k)$ when the wavenumber $k$ is large; this enhancement leads
to dissipation reduction.

Based on mesoscale lattice Boltzmann (LB) numerical simulations, we
investigate the effects of viscoelasticity on the breakup of liquid threads in
microfluidic crossjunctions, where droplets are formed by focusing a liquid
thread of a dispersed (d) phase into another coflowing continuous (c)
immiscible phase. Working at small Capillary numbers, we investigate the
effects of nonNewtonian phases in the transition from droplet formation at the
crossjunction (DCJ) to droplet formation downstream of the crossjunction (DC)
(Liu $\&$ Zhang, ${\it Phys. ~Fluids.}$ ${\bf 23}$, 082101 (2011)). We will
analyze cases with ${\it Droplet ~Viscoelasticity}$ (DV), where viscoelastic
properties are confined in the dispersed phase, as well as cases with ${\it
Matrix ~Viscoelasticity}$ (MV), where viscoelastic properties are confined in
the continuous phase. Moderate flowrate ratios $Q \approx {\cal O}(1)$ of the
two phases are considered in the present study. Overall, we find that the
effects are more pronounced in the case with MV, where viscoelasticity is found
to influence the breakup point of the threads, which moves closer to the
crossjunction and stabilizes. This is attributed to an increase of the polymer
feedback stress forming in the corner flows, where the side channels of the
device meet the main channel. Quantitative predictions on the breakup point of
the threads are provided as a function of the Deborah number, i.e. the
dimensionless number measuring the importance of viscoelasticity with respect
to Capillary forces.

The effects of viscoelasticity on the dynamics and breakup of fluid threads
in microfluidic Tjunctions are investigated using numerical simulations of
dilute polymer solutions at changing the Capillary number ($\mbox {Ca}$), i.e.
at changing the balance between the viscous forces and the surface tension at
the interface, up to $\mbox{Ca} \approx 3 \times 10^{2}$. A NavierStokes (NS)
description of the solvent based on the lattice Boltzmann models (LBM) is here
coupled to constitutive equations for finite extensible nonlinear elastic
dumbbells with the closure proposed by Peterlin (FENEP model). We present the
results of threedimensional simulations in a range of $\mbox{Ca}$ which is
broad enough to characterize all the three characteristic mechanisms of breakup
in the confined Tjunction, i.e. ${\it squeezing}$, ${\it dripping}$ and ${\it
jetting}$ regimes. The various model parameters of the FENEP constitutive
equations, including the polymer relaxation time $\tau_P$ and the finite
extensibility parameter $L^2$, are changed to provide quantitative details on
how the dynamics and breakup properties are affected by viscoelasticity. We
will analyze cases with ${\it Droplet ~Viscoelasticity}$ (DV), where
viscoelastic properties are confined in the dispersed (d) phase, as well as
cases with ${\it Matrix ~Viscoelasticity}$ (MV), where viscoelastic properties
are confined in the continuous (c) phase. Moderate flowrate ratios $Q \approx
{\cal O}(1)$ of the two phases are considered in the present study. Overall, we
find that the effects are more pronounced in the case with MV, as the flow
driving the breakup process upstream of the emerging thread can be sensibly
perturbed by the polymer stresses.

We investigate the breakup of Newtonian/viscoelastic droplets in a
viscoelastic/Newtonian matrix under the hydrodynamic conditions of a confined
shear flow. Our numerical approach is based on a combination of
LatticeBoltzmann models (LBM) and Finite Difference (FD) schemes. LBM are used
to model two immiscible fluids with variable viscosity ratio (i.e. the ratio of
the droplet to matrix viscosity); FD schemes are used to model viscoelasticity,
and the kinetics of the polymers is introduced using constitutive equations for
viscoelastic fluids with finitely extensible nonlinear elastic dumbbells with
Peterlin's closure (FENEP). We study both strongly and weakly confined cases
to highlight the role of matrix and droplet viscoelasticity in changing the
droplet dynamics after the startup of a shear flow. Simulations provide easy
access to quantities such as droplet deformation and orientation and will be
used to quantitatively predict the critical Capillary number at which the
droplet breaks, the latter being strongly correlated to the formation of
multiple neckings at breakup. This study complements our previous
investigation on the role of droplet viscoelasticity (A. Gupta \& M.
Sbragaglia, {\it Phys. Rev. E} {\bf 90}, 023305 (2014)), and is here further
extended to the case of matrix viscoelasticity.

We present the most extensive direct numerical simulations, attempted so far,
of statistically steady, homogeneous, isotropic turbulence in twodimensional
fluid films with airdraginduced friction and with polymer additives. Our
study reveals that the polymers (a) reduce the total fluid energy, enstrophy,
and palinstrophy, (b) modify the fluid energy spectrum both in inverse and
forwardcascade regimes, (c) reduce smallscale intermittency, (d) suppress
regions of large vorticity and strain rate, and (e) stretch in straindominated
regions. We compare our results with earlier experimental studies; and we
propose new experiments.

The online (uniform) buyatbulk network design problem asks us to design a
network, where the edgecosts exhibit economyofscale. Previous approaches to
this problem used tree embeddings, giving us randomized algorithms. Moreover,
the optimal results with a logarithmic competitive ratio requires the metric on
which the network is being built to be known upfront; the competitive ratios
then depend on the size of this metric (which could be much larger than the
number of terminals that arrive).
We consider the buyatbulk problem in the least restrictive model where the
metric is not known in advance, but revealed in parts along with the demand
points seeking connectivity arriving online. For the single sink buyatbulk
problem, we give a deterministic online algorithm with competitive ratio that
is logarithmic in k, the number of terminals that have arrived, matching the
lower bound known even for the online Steiner tree problem. In the oblivious
case when the buyatbulk function used to compute the edgecosts of the
network is not known in advance (but is the same across all edges), we give a
deterministic algorithm with competitive ratio polylogarithmic in k, the number
of terminals.
At the heart of our algorithms are optimal constructions for online Light
Approximate Shortestpath Trees (LASTs) and spanners, and their variants. We
give constructions that have optimal tradeoffs in terms of cost and stretch.
We also define and give constructions for a new notion of LASTs where the set
of roots (in addition to the points) expands over time. We expect these
techniques will find applications in other online networkdesign problems.

We obtain the probability distribution functions (PDFs) of the time that a
Lagrangian tracer or a heavy inertial particle spends in vortical or
straindominated regions of a turbulent flow, by carrying out direct numerical
simulation (DNS) of such particles advected by statistically steady,
homogeneous and isotropic turbulence in the forced, threedimensional,
incompressible NavierStokes equation. We use the two invariants, $Q$ and $R$,
of the velocitygradient tensor to distinguish between vortical and
straindominated regions of the flow and partition the $QR$ plane into four
different regions depending on the topology of the flow; out of these four
regions two correspond to vorticitydominated regions of the flow and two
correspond to straindominated ones. We obtain $Q$ and $R$ along the
trajectories of tracers and heavy inertial particles and find out the time
$\mathrm{t_{pers}}$ for which they remain in one of the four regions of the
$QR$ plane. We find that the PDFs of $\mathrm{t_{pers}}$ display exponentially
decaying tails for all four regions for tracers and heavy inertial particles.
From these PDFs we extract characteristic times scales, which help us to
quantify the time that such particles spend in vortical or straindominated
regions of the flow.

Suppose we are given a submodular function $f$ over a set of elements, and we
want to maximize its value subject to certain constraints. Good approximation
algorithms are known for such problems under both monotone and nonmonotone
submodular functions. We consider these problems in a stochastic setting, where
elements are not all active and we can only get value from active elements.
Each element $e$ is active independently with some known probability $p_e$, but
we don't know the element's status \emph{a priori}. We find it out only when we
\emph{probe} the element $e$probing reveals whether it's active or not,
whereafter we can use this information to decide which other elements to probe.
Eventually, if we have a probed set $S$ and a subset $\text{active}(S)$ of
active elements in $S$, we can pick any $T \subseteq \text{active}(S)$ and get
value $f(T)$. Moreover, the sequence of elements we probe must satisfy a given
\emph{prefixclosed constraint}e.g., these may be given by a matroid, or an
orienteering constraint, or deadline, or precedence constraint, or an arbitrary
downwardclosed constraintif we can probe some sequence of elements we can
probe any prefix of it. What is a good strategy to probe elements to maximize
the expected value?
In this paper we study the gap between adaptive and nonadaptive strategies
for $f$ being a submodular or a fractionally subadditive (XOS) function. If
this gap is small, we can focus on finding good nonadaptive strategies
instead, which are easier to find as well as to represent. We show that the
adaptivity gap is a constant for monotone and nonmonotone submodular
functions, and logarithmic for XOS functions of small \emph{width}. These
bounds are nearly tight. Our techniques show new ways of arguing about the
optimal adaptive decision tree for stochastic problems.

We study the pure exploration problem subject to a matroid constraint
(BestBasis) in a stochastic multiarmed bandit game. In a BestBasis instance,
we are given $n$ stochastic arms with unknown reward distributions, as well as
a matroid $\mathcal{M}$ over the arms. Let the weight of an arm be the mean of
its reward distribution. Our goal is to identify a basis of $\mathcal{M}$ with
the maximum total weight, using as few samples as possible.
The problem is a significant generalization of the best arm identification
problem and the top$k$ arm identification problem, which have attracted
significant attentions in recent years. We study both the exact and PAC
versions of BestBasis, and provide algorithms with nearlyoptimal sample
complexities for these versions. Our results generalize and/or improve on
several previous results for the top$k$ arm identification problem and the
combinatorial pure exploration problem when the combinatorial constraint is a
matroid.

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
righthand sides of the LPs have to be (compared to the entries on the
lefthand side of the constraints) to allow $(1+\epsilon)$approximations
online. It is known that the righthand sides have to be $\Omega(\epsilon^{2}
\log m)$ times the lefthand sides, where $m$ is the number of constraints.
In this paper we give a primaldual algorithm that achieve this bound for
mixed packing/covering LPs. Our algorithms construct dual solutions using a
regretminimizing online learning algorithm in a blackbox 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.