More Like this

1. Competitive Algorithms for Online Multidimensional Knapsack Problems

   https://doi.org/10.1145/3491042  

   Yang, Lin ; Zeynali, Ali ; Hajiesmaili, Mohammad H. ; Sitaraman, Ramesh K. ; Towsley, Don ( December 2021 , Proceedings of the ACM on Measurement and Analysis of Computing Systems)

   In this paper, we study the online multidimensional knapsack problem (called OMdKP) in which there is a knapsack whose capacity is represented in m dimensions, each dimension could have a different capacity. Then, n items with different scalar profit values and m-dimensional weights arrive in an online manner and the goal is to admit or decline items upon their arrival such that the total profit obtained by admitted items is maximized and the capacity of knapsack across all dimensions is respected. This is a natural generalization of the classic single-dimension knapsack problem and finds several relevant applications such as in virtual machine allocation, job scheduling, and all-or-nothing flow maximization over a graph. We develop two algorithms for OMdKP that use linear and exponential reservation functions to make online admission decisions. Our competitive analysis shows that the linear and exponential algorithms achieve the competitive ratios of O(θα ) and O(łogł(θα)), respectively, where α is the ratio between the aggregate knapsack capacity and the minimum capacity over a single dimension and θ is the ratio between the maximum and minimum item unit values. We also characterize a lower bound for the competitive ratio of any online algorithm solving OMdKP and show that the competitive ratio of our algorithm with exponential reservation function matches the lower bound up to a constant factor. 

   more » « less
2. The Online Knapsack Problem with Departures

   https://doi.org/10.1145/3570618  

   Sun, Bo ; Yang, Lin ; Hajiesmaili, Mohammad ; Wierman, Adam ; Lui, John C. ; Towsley, Don ; Tsang, Danny H.K. ( December 2022 , Proceedings of the ACM on Measurement and Analysis of Computing Systems)

   The online knapsack problem is a classic online resource allocation problem in networking and operations research. Its basic version studies how to pack online arriving items of different sizes and values into a capacity-limited knapsack. In this paper, we study a general version that includes item departures, while also considering multiple knapsacks and multi-dimensional item sizes. We design a threshold-based online algorithm and prove that the algorithm can achieve order-optimal competitive ratios. Beyond worst-case performance guarantees, we also aim to achieve near-optimal average performance under typical instances. Towards this goal, we propose a data-driven online algorithm that learns within a policy-class that guarantees a worst-case performance bound. In trace-driven experiments, we show that our data-driven algorithm outperforms other benchmark algorithms in an application of online knapsack to job scheduling for cloud computing. 

   more » « less
3. Extremal spectral gaps for periodic Schrödinger operators

   https://doi.org/10.1051/cocv/2018029  

   Kao, Chiu-Yen ; Osting, Braxton ( January 2019 , ESAIM: Control, Optimisation and Calculus of Variations)

   The spectrum of a Schrödinger operator with periodic potential generally consists of bands and gaps. In this paper, for fixed m , we consider the problem of maximizing the gap-to-midgap ratio for the m th spectral gap over the class of potentials which have fixed periodicity and are pointwise bounded above and below. We prove that the potential maximizing the m th gap-to-midgap ratio exists. In one dimension, we prove that the optimal potential attains the pointwise bounds almost everywhere in the domain and is a step-function attaining the imposed minimum and maximum values on exactly m intervals. Optimal potentials are computed numerically using a rearrangement algorithm and are observed to be periodic. In two dimensions, we develop an efficient rearrangement method for this problem based on a semi-definite formulation and apply it to study properties of extremal potentials. We show that, provided a geometric assumption about the maximizer holds, a lattice of disks maximizes the first gap-to-midgap ratio in the infinite contrast limit. Using an explicit parametrization of two-dimensional Bravais lattices, we also consider how the optimal value varies over all equal-volume lattices. 

   more » « less
4. Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging

   https://doi.org/10.1145/3428336  

   Sun, Bo ; Zeynali, Ali ; Li, Tongxin ; Hajiesmaili, Mohammad ; Wierman, Adam ; Tsang, Danny H.K. ( November 2020 , Proceedings of the ACM on Measurement and Analysis of Computing Systems)

   null (Ed.)

   We introduce and study a general version of the fractional online knapsack problem with multiple knapsacks, heterogeneous constraints on which items can be assigned to which knapsack, and rate-limiting constraints on the assignment of items to knapsacks. This problem generalizes variations of the knapsack problem and of the one-way trading problem that have previously been treated separately, and additionally finds application to the real-time control of electric vehicle (EV) charging. We introduce a new algorithm that achieves a competitive ratio within an additive factor of one of the best achievable competitive ratios for the general problem and matches or improves upon the best-known competitive ratio for special cases in the knapsack and one-way trading literatures. Moreover, our analysis provides a novel approach to online algorithm design based on an instance-dependent primal-dual analysis that connects the identification of worst-case instances to the design of algorithms. Finally, we illustrate the proposed algorithm via trace-based experiments of EV charging. 

   more » « less
5. Size‐specific grazing and competitive interactions between large salps and protistan grazers

   https://doi.org/10.1002/lno.11770  

   Stukel, Michael R. ; Décima, Moira ; Selph, Karen E. ; Gutiérrez‐Rodríguez, Andres ( May 2021 , Limnology and Oceanography)

   We investigated competition betweenSalpa thompsoniand protistan grazers during Lagrangian experiments near the Subtropical Front in the southwest Pacific sector of the Southern Ocean. Over a month, the salp community shifted from dominance by large (> 100 mm) oozooids and small (< 20 mm) blastozooids to large (~ 60 mm) blastozooids. Phytoplankton biomass was consistently dominated by nano‐ and microphytoplankton (> 2 μm cells). Using bead‐calibrated flow‐cytometry light scatter to estimate phytoplankton size, we quantified size‐specific salp and protistan zooplankton grazing pressure. Salps were able to feed at a > 10,000 : 1 predator : prey size (linear‐dimension) ratio. Small blastozooids efficiently retained cells > 1.4μm (high end of picoplankton size, 0.6–2 μm cells) and also obtained substantial nutrition from smaller bacteria‐sized cells. Larger salps could only feed efficiently on > 5.9μm cells and were largely incapable of feeding on picoplankton. Due to the high biomass of nano‐ and microphytoplankton, however, all salps derived most of their (phytoplankton‐based) nutrition from these larger autotrophs. Phagotrophic protists were the dominant competitors for these prey items and consumed approximately 50% of the biomass of all phytoplankton size classes each day. Using a Bayesian statistical framework, we developed an allometric‐scaling equation for salp clearance rates as a function of salp and prey size:urn:x-wiley:00243590:media:lno11770:lno11770-math-0001where ESD is prey equivalent spherical diameter (µm), TL isS. thompsonitotal length,φ = 5.6 × 10⁻³ ± 3.6 × 10⁻⁴,ψ = 2.1 ± 0.13,θ = 0.58 ± 0.08, andγ = 0.46 ± 0.03 and clearance rate is L d^‐1salp^‐1. We discuss the biogeochemical and food‐web implications of competitive interactions among salps, krill, and protozoans.

    

   more » « less