More Like this

1. Variational problems for tree roots and branches

   https://doi.org/10.1007/s00526-019-1666-1  

   Bressan, Alberto ; Palladino, Michele ; Sun, Qing ( November 2019 , Calculus of variations and partial differential equations)

   This paper studies two classes of variational problems introduced in Bressan and Sun (On the optimal shape of tree roots and branches. arXiv:1803.01042), related to the optimal shapes of tree roots and branches. Given a measure μ describing the distribution of leaves, a sunlight functional S(μ) computes the total amount of light captured by the leaves. For a measure μ describing the distribution of root hair cells, a harvest functional H(μ) computes the total amount of water and nutrients gathered by the roots. In both cases, we seek a measure μ that maximizes these functionals subject to a ramified transportation cost, for transporting nutrients from the roots to the trunk or from the trunk to the leaves. Compared with Bressan and Sun, here we do not impose any a priori bound on the total mass of the optimal measure μ, and more careful a priori estimates are thus required. In the unconstrained optimization problem for branches, we prove that an optimal measure exists, with bounded support and bounded total mass. In the unconstrained problem for tree roots, we prove that an optimal measure exists, with bounded support but possibly unbounded total mass. The last section of the paper analyzes how the size of the optimal tree depends on the parameters defining the various functionals. 

   more » « less
2. Stability of a Subcritical Fluid Model for Fair Bandwidth Sharing with General File Size Distributions

   https://doi.org/10.1287/stsy.2019.0058  

   Fu, Yingjia ; Williams, Ruth J. ( September 2020 , Stochastic Systems)

   null (Ed.)

   This work concerns the asymptotic behavior of solutions to a (strictly) subcritical fluid model for a data communication network, where file sizes are generally distributed and the network operates under a fair bandwidth-sharing policy. Here we consider fair bandwidth-sharing policies that are a slight generalization of the [Formula: see text]-fair policies introduced by Mo and Walrand [Mo J, Walrand J (2000) Fair end-to-end window-based congestion control. IEEE/ACM Trans. Networks 8(5):556–567.]. Since the year 2000, it has been a standing problem to prove stability of the data communications network model of Massoulié and Roberts [Massoulié L, Roberts J (2000) Bandwidth sharing and admission control for elastic traffic. Telecommunication Systems 15(1):185–201.], with general file sizes and operating under fair bandwidth sharing policies, when the offered load is less than capacity (subcritical conditions). A crucial step in an approach to this problem is to prove stability of subcritical fluid model solutions. In 2012, Paganini et al. [Paganini F, Tang A, Ferragut A, Andrew LLH (2012) Network stability under alpha fair bandwidth allocation with general file size distribution. IEEE Trans. Automatic Control 57(3):579–591.] introduced a Lyapunov function for this purpose and gave an argument, assuming that fluid model solutions are sufficiently smooth in time and space that they are strong solutions of a partial differential equation and assuming that no fluid level on any route touches zero before all route levels reach zero. The aim of the current paper is to prove stability of the subcritical fluid model without these strong assumptions. Starting with a slight generalization of the Lyapunov function proposed by Paganini et al., assuming that each component of the initial state of a measure-valued fluid model solution, as well as the file size distributions, have no atoms and have finite first moments, we prove absolute continuity in time of the composition of the Lyapunov function with any subcritical fluid model solution and describe the associated density. We use this to prove that the Lyapunov function composed with such a subcritical fluid model solution converges to zero as time goes to infinity. This implies that each component of the measure-valued fluid model solution converges vaguely on [Formula: see text] to the zero measure as time goes to infinity. Under the further assumption that the file size distributions have finite pth moments for some p > 1 and that each component of the initial state of the fluid model solution has finite pth moment, it is proved that the fluid model solution reaches the measure with all components equal to the zero measure in finite time and that the time to reach this zero state has a uniform bound for all fluid model solutions having a uniform bound on the initial total mass and the pth moment of each component of the initial state. In contrast to the analysis of Paganini et al., we do not need their strong smoothness assumptions on fluid model solutions and we rigorously treat the realistic, but singular situation, where the fluid level on some routes becomes zero, whereas other route levels remain positive. 

   more » « less
3. Dynamic Pricing and Inventory Control with Fixed Ordering Cost and Incomplete Demand Information

   https://doi.org/10.1287/mnsc.2021.4171  

   Chen, Boxiao ; Simchi-Levi, David ; Wang, Yining ; Zhou, Yuan ( December 2021 , Management Science)

   We consider the periodic review dynamic pricing and inventory control problem with fixed ordering cost. Demand is random and price dependent, and unsatisfied demand is backlogged. With complete demand information, the celebrated [Formula: see text] policy is proved to be optimal, where s and S are the reorder point and order-up-to level for ordering strategy, and [Formula: see text], a function of on-hand inventory level, characterizes the pricing strategy. In this paper, we consider incomplete demand information and develop online learning algorithms whose average profit approaches that of the optimal [Formula: see text] with a tight [Formula: see text] regret rate. A number of salient features differentiate our work from the existing online learning researches in the operations management (OM) literature. First, computing the optimal [Formula: see text] policy requires solving a dynamic programming (DP) over multiple periods involving unknown quantities, which is different from the majority of learning problems in OM that only require solving single-period optimization questions. It is hence challenging to establish stability results through DP recursions, which we accomplish by proving uniform convergence of the profit-to-go function. The necessity of analyzing action-dependent state transition over multiple periods resembles the reinforcement learning question, considerably more difficult than existing bandit learning algorithms. Second, the pricing function [Formula: see text] is of infinite dimension, and approaching it is much more challenging than approaching a finite number of parameters as seen in existing researches. The demand-price relationship is estimated based on upper confidence bound, but the confidence interval cannot be explicitly calculated due to the complexity of the DP recursion. Finally, because of the multiperiod nature of [Formula: see text] policies the actual distribution of the randomness in demand plays an important role in determining the optimal pricing strategy [Formula: see text], which is unknown to the learner a priori. In this paper, the demand randomness is approximated by an empirical distribution constructed using dependent samples, and a novel Wasserstein metric-based argument is employed to prove convergence of the empirical distribution. This paper was accepted by J. George Shanthikumar, big data analytics. 

   more » « less
4. Evaluation of Protein Extraction Methods for Metaproteomic Analyses of Root-Associated Microbes

   https://doi.org/10.1094/MPMI-05-22-0116-TA  

   Salvato, Fernanda ; Vintila, Simina ; Finkel, Omri M. ; Dangl, Jeffery L. ; Kleiner, Manuel ( November 2022 , Molecular Plant-Microbe Interactions®)

   Metaproteomics is a powerful tool for the characterization of metabolism, physiology, and functional interactions in microbial communities, including plant-associated microbiota. However, the metaproteomic methods that have been used to study plant-associated microbiota are very laborious and require large amounts of plant tissue, hindering wider application of these methods. We optimized and evaluated different protein extraction methods for metaproteomics of plant-associated microbiota in two different plant species ( Arabidopsis and maize). Our main goal was to identify a method that would work with low amounts of input material (40 to 70 mg) and that would maximize the number of identified microbial proteins. We tested eight protocols, each comprising a different combination of physical lysis method, extraction buffer, and cell-enrichment method on roots from plants grown with synthetic microbial communities. We assessed the performance of the extraction protocols by liquid chromatography-tandem mass spectrometry–based metaproteomics and found that the optimal extraction method differed between the two species. For Arabidopsis roots, protein extraction by beating whole roots with small beads provided the greatest number of identified microbial proteins and improved the identification of proteins from gram-positive bacteria. For maize, vortexing root pieces in the presence of large glass beads yielded the greatest number of microbial proteins identified. Based on these data, we recommend the use of these two methods for metaproteomics with Arabidopsis and maize. Furthermore, detailed descriptions of the eight tested protocols will enable future optimization of protein extraction for metaproteomics in other dicot and monocot plants. [Formula: see text] Copyright © 2022 The Author(s). This is an open access article distributed under the CC BY 4.0 International license . 

   more » « less
5. A Complementary Pivot Algorithm for Competitive Allocation of a Mixed Manna

   https://doi.org/10.1287/moor.2022.1315  

   Chaudhury, Bhaskar Ray ; Garg, Jugal ; McGlaughlin, Peter ; Mehta, Ruta ( September 2022 , Mathematics of Operations Research)

   We study the fair division problem of allocating a mixed manna under additively separable piecewise linear concave (SPLC) utilities. A mixed manna contains goods that everyone likes and bads (chores) that everyone dislikes as well as items that some like and others dislike. The seminal work of Bogomolnaia et al. argues why allocating a mixed manna is genuinely more complicated than a good or a bad manna and why competitive equilibrium is the best mechanism. It also provides the existence of equilibrium and establishes its distinctive properties (e.g., nonconvex and disconnected set of equilibria even under linear utilities) but leaves the problem of computing an equilibrium open. Our main results are a linear complementarity problem formulation that captures all competitive equilibria of a mixed manna under SPLC utilities (a strict generalization of linear) and a complementary pivot algorithm based on Lemke’s scheme for finding one. Experimental results on randomly generated instances suggest that our algorithm is fast in practice. Given the [Formula: see text]-hardness of the problem, designing such an algorithm is the only non–brute force (nonenumerative) option known; for example, the classic Lemke–Howson algorithm for computing a Nash equilibrium in a two-player game is still one of the most widely used algorithms in practice. Our algorithm also yields several new structural properties as simple corollaries. We obtain a (constructive) proof of existence for a far more general setting, membership of the problem in [Formula: see text], a rational-valued solution, and an odd number of solutions property. The last property also settles the conjecture of Bogomolnaia et al. in the affirmative. Furthermore, we show that, if the number of either agents or items is a constant, then the number of pivots in our algorithm is strongly polynomial when the mixed manna contains all bads. 

   more » « less