skip to main content

Search for: All records

Creators/Authors contains: "Sun, Bo"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. 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.
    Free, publicly-accessible full text available December 1, 2023
  2. Free, publicly-accessible full text available April 1, 2023
  3. The Princess Elizabeth Land sector of the East Antarctic Ice Sheet is a significant reservoir of grounded ice and is adjacent to regions that experienced great change during Quaternary glacial cycles and Pliocene warm episodes. The existence of an extensive subglacial water system in Princess Elizabeth Land (to date only inferred from satellite imagery) bears the potential to significantly impact the thermal and kinematic conditions of the overlying ice sheet. We confirm the existence of a major subglacial lake, herein referred to as Lake Snow Eagle (LSE), for the first time using recently acquired aerogeophysical data. We systematically investigated LSE’s geological characteristics and bathymetry from two-dimensional geophysical inversion models. The inversion results suggest that LSE is located along a compressional geologic boundary, which provides reference for future characterization of the geologic and tectonic context of this region. We estimate LSE to be ~42 km in length and 370 km2 in area, making it one of the largest subglacial lakes in Antarctica. Additionally, the airborne ice-penetrating radar observations and geophysical inversions reveal a layer of unconsolidated water-saturated sediment around and at the bottom of LSE, which—given the ultralow rates of sedimentation expected in such environments—may archive valuable records of paleoenvironmental changesmore »and the early history of East Antarctic Ice Sheet evolution in Princess Elizabeth Land.« less
    Free, publicly-accessible full text available May 9, 2023
  4. Abstract

    Cell shape is linked to cell function. The significance of cell morphodynamics, namely the temporal fluctuation of cell shape, is much less understood. Here we study the morphodynamics of MDA-MB-231 cells in type I collagen extracellular matrix (ECM). We systematically vary ECM physical properties by tuning collagen concentrations, alignment, and gelation temperatures. We find that morphodynamics of 3D migrating cells are externally controlled by ECM mechanics and internally modulated by Rho/ROCK-signaling. We employ machine learning to classify cell shape into four different morphological phenotypes, each corresponding to a distinct migration mode. As a result, we map cell morphodynamics at mesoscale into the temporal evolution of morphological phenotypes. We characterize the mesoscale dynamics including occurrence probability, dwell time and transition matrix at varying ECM conditions, which demonstrate the complex phenotype landscape and optimal pathways for phenotype transitions. In light of the mesoscale dynamics, we show that 3D cancer cell motility is a hidden Markov process whereby the step size distributions of cell migration are coupled with simultaneous cell morphodynamics. Morphological phenotype transitions also facilitate cancer cells to navigate non-uniform ECM such as traversing the interface between matrices of two distinct microstructures. In conclusion, we demonstrate that 3D migrating cancer cellsmore »exhibit rich morphodynamics that is controlled by ECM mechanics, Rho/ROCK-signaling, and regulate cell motility. Our results pave the way to the functional understanding and mechanical programming of cell morphodynamics as a route to predict and control 3D cell motility.

    « less
  5. Free, publicly-accessible full text available February 23, 2023
  6. The design of online algorithms has tended to focus on algorithms with worst-case guarantees, e.g., bounds on the competitive ratio. However, it is well-known that such algorithms are often overly pessimistic, performing sub-optimally on non-worst-case inputs. In this paper, we develop an approach for data-driven design of online algorithms that maintain near-optimal worst-case guarantees while also performing learning in order to perform well for typical inputs. Our approach is to identify policy classes that admit global worst-case guarantees, and then perform learning using historical data within the policy classes. We demonstrate the approach in the context of two classical problems, online knapsack, and online set cover, proving competitive bounds for rich policy classes in each case. Additionally, we illustrate the practical implications via a case study on electric vehicle charging.
  7. 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.