• 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 random-order 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 edge-deletion 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 bounded-degree graphs, and also give an APX-hardness result for the edge deletion problems.
  • We study the classic Bin Packing problem in a fully-dynamic 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 fully-dynamic 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.
  • Droplet-based 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, non-Newtonian 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 T-shaped junction, when the continuous phase is made of shear thinning liquids. At first, we review in detail the breakup process providing extensive, side-by-side comparisons between Newtonian and non-Newtonian liquids over unexplored ranges of flow conditions and viscous responses. The non-Newtonian liquid carrying the droplets is made of Xanthan solutions, a stiff rod-like polysaccharide displaying a marked shear thinning rheology. By defining an effective Capillary number, a simple yet effective methodology is used to account for the shear-dependent 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 three-dimensional, 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 time-scale $\tau$ is non-Gaussian, 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 power-input $p$ is negatively skewed too; we use this skewness ${\rm Ir}$ as a measure of the time-irreversibility 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 slow-gain and fast-loss 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 slow-gain in energy of the particles is equally likely in vortical or strain-dominated regions of the flow; in contrast, the fast-loss of energy occurs with greater probability in the latter than in the former.
  • The Beale-Kato-Majda 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 Navier-Stokes equations together with a phase-field model for the statistical mechanics of binary mixtures called the $3D$ Cahn-Hilliard-Navier-Stokes (CHNS) equations. A theorem of BKM-type 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 energy-dissipation rate that, remarkably, reproduces the $Re^{3/4}$ upper bound on the inverse Kolmogorov length normally associated with the Navier-Stokes equations alone. An alternative length-scale is introduced and discussed, together with a set of pseudo-spectral computations on a $128^{3}$ grid.
  • We study the problem of embedding shortest-path metrics of weighted graphs into $\ell_p$ spaces. We introduce a new embedding technique based on low-depth 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 $k-1$. 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 source-sink pairs, and the goal is to find a subgraph of minimum total length such that all pairs are connected. The problem is APX-Hard and can be 2-approximated by, e.g., the elegant primal-dual algorithm of Agrawal, Klein, and Ravi from 1995. We give a local-search-based constant-factor 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 carefully-chosen 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 Best-Set in stochastic multi-armed bandits. In a Best-Set 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 instance-wise 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 multi-objective 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 Best-Set 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 spiral-and scroll-wave turbulence in two- and three-dimensional excitable media by using approaches employed in studies of classical turbulence. We use the Panfilov and the Aliev-Panfilov mathematical models for cardiac tissue. We show that once electrical-wave 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 electrical-wave 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 scroll-wave 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 fluid-turbulence 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 scroll-wave turbulence with their fluid-turbulence counterparts,we show that,although spiral- and scroll-wave 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.
  • Low-Reynolds-number polymer solutions exhibit a chaotic behaviour known as 'elastic turbulence' when the Weissenberg number exceeds a critical value. The two-dimensional Oldroyd-B 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 Oldroyd-B 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 a-priori 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 us--we 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 poly-logarithmic approximation, and show that this algorithm is best possible unless we can improve the approximation guarantees for the well-known group Steiner tree problem.
  • We perform a direct numerical simulation (DNS) of the forced, incompressible two-dimensional Navier-Stokes equation coupled with the FENE-P equations for the polymer-conformation 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 anti-vortices. 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, fractal-type character and (b) the Okubo-Weiss parameter $\Lambda$ provides us with a natural measure for characterizing the phases and transitions in this diagram.
  • We consider the 3D Cahn-Hilliard equations coupled to, and driven by, the forced, incompressible 3D Navier-Stokes equations. The combination, known as the Cahn-Hilliard-Navier-Stokes (CHNS) equations, is used in statistical mechanics to model the motion of a binary fluid. The potential development of singularities (blow-up) in the contours of the order parameter $\phi$ is an open problem. To address this we have proved a theorem that closely mimics the Beale-Kato-Majda theorem for the $3D$ incompressible Euler equations [Beale et al. Commun. Math. Phys., Commun. Math. Phys., ${\rm 94}$, $ 61-66 ({\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 gravity-driven Rayleigh Taylor instability and (b) a constant-energy-injection 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 fully-dynamic model that are inspired by the classic greedy and primal-dual 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 two-dimensional, binary-fluid mixtures with air-drag-induced friction by using the Cahn-Hilliard-Navier-Stokes 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, non-Gaussian 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 break-up of liquid threads in microfluidic cross-junctions, where droplets are formed by focusing a liquid thread of a dispersed (d) phase into another co-flowing continuous (c) immiscible phase. Working at small Capillary numbers, we investigate the effects of non-Newtonian phases in the transition from droplet formation at the cross-junction (DCJ) to droplet formation downstream of the cross-junction (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 flow-rate 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 break-up point of the threads, which moves closer to the cross-junction 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 break-up 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 break-up of fluid threads in microfluidic T-junctions 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 Navier-Stokes (NS) description of the solvent based on the lattice Boltzmann models (LBM) is here coupled to constitutive equations for finite extensible non-linear elastic dumbbells with the closure proposed by Peterlin (FENE-P model). We present the results of three-dimensional simulations in a range of $\mbox{Ca}$ which is broad enough to characterize all the three characteristic mechanisms of breakup in the confined T-junction, i.e. ${\it squeezing}$, ${\it dripping}$ and ${\it jetting}$ regimes. The various model parameters of the FENE-P 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 break-up 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 flow-rate 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 break-up process upstream of the emerging thread can be sensibly perturbed by the polymer stresses.
  • We investigate the break-up 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 Lattice-Boltzmann 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 non-linear elastic dumbbells with Peterlin's closure (FENE-P). 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 break-up. 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 two-dimensional fluid films with air-drag-induced 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 forward-cascade regimes, (c) reduce small-scale intermittency, (d) suppress regions of large vorticity and strain rate, and (e) stretch in strain-dominated regions. We compare our results with earlier experimental studies; and we propose new experiments.
  • The online (uniform) buy-at-bulk network design problem asks us to design a network, where the edge-costs exhibit economy-of-scale. 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 up-front; 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 buy-at-bulk 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 buy-at-bulk 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 buy-at-bulk function used to compute the edge-costs 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 Shortest-path Trees (LASTs) and spanners, and their variants. We give constructions that have optimal trade-offs 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 network-design problems.
  • We obtain the probability distribution functions (PDFs) of the time that a Lagrangian tracer or a heavy inertial particle spends in vortical or strain-dominated 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, three-dimensional, incompressible Navier-Stokes equation. We use the two invariants, $Q$ and $R$, of the velocity-gradient tensor to distinguish between vortical and strain-dominated regions of the flow and partition the $Q-R$ plane into four different regions depending on the topology of the flow; out of these four regions two correspond to vorticity-dominated regions of the flow and two correspond to strain-dominated 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 $Q-R$ 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 strain-dominated 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 non-monotone 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{prefix-closed constraint}---e.g., these may be given by a matroid, or an orienteering constraint, or deadline, or precedence constraint, or an arbitrary downward-closed constraint---if 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 non-adaptive strategies for $f$ being a submodular or a fractionally subadditive (XOS) function. If this gap is small, we can focus on finding good non-adaptive strategies instead, which are easier to find as well as to represent. We show that the adaptivity gap is a constant for monotone and non-monotone 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 (Best-Basis) in a stochastic multi-armed bandit game. In a Best-Basis 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 Best-Basis, and provide algorithms with nearly-optimal 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 right-hand sides of the LPs have to be (compared to the entries on the left-hand side of the constraints) to allow $(1+\epsilon)$-approximations online. It is known that the right-hand sides have to be $\Omega(\epsilon^{-2} \log m)$ times the left-hand sides, where $m$ is the number of constraints. In this paper we give a primal-dual algorithm that achieve this bound for mixed packing/covering LPs. Our algorithms construct dual solutions using a regret-minimizing online learning algorithm in a black-box fashion, and use them to construct primal solutions. The adversarial guarantee that holds for the constructed duals helps us to take care of most of the correlations that arise in the algorithm; the remaining correlations are handled via martingale concentration and maximal inequalities. These ideas lead to conceptually simple and modular algorithms, which we hope will be useful in other contexts.