More Like this

1. Prediction of the survival status for multispecies competition system

   https://doi.org/10.1063/5.0164710  

   Wang, Youwen; Vasilyeva, Maria; Sadovski, Alexey (January 2023, AIP Conference Proceedings)

   We consider a multispecies competition model in a one- and two-dimensional formulation. To solve the problem numerically, we construct a discrete system using finite volume approximation by space with semi-implicit time approximation. The solution of the multispecies competition model converges to the final equilibrium state that does not depend on the initial condition of the system. The final equilibrium state characterizes the survival status of the multispecies system (one or more species survive or no one survives). In real-world problems values of the parameters are unknown and vary in some range. For such problems, the series of Monte Carlo simulations can be used to estimate the system, where a large number of simulations are needed to be performed with random values of the parameters. A numerical solution is expensive, especially for high-dimensional problems, and requires a large amount of time to perform. In this work, to reduce the cost of simulations, we use a deep neural network to fast predict the survival status. Numerical results are presented for different neural network configurations. The comparison with convenient classifiers is presented. 

   more » « less
2. Breaking the r _max Barrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem

   https://doi.org/10.1287/ijoc.2020.0975  

   Ran, Yingli; Zhang, Zhao; Tang, Shaojie; Du, Ding-Zhu (October 2020, INFORMS Journal on Computing)

   null (Ed.)

   Given an element set E of order n, a collection of subsets [Formula: see text], a cost c S on each set [Formula: see text], a covering requirement r e for each element [Formula: see text], and an integer k, the goal of a minimum partial set multicover problem (MinPSMC) is to find a subcollection [Formula: see text] to fully cover at least k elements such that the cost of [Formula: see text] is as small as possible and element e is fully covered by [Formula: see text] if it belongs to at least r e sets of [Formula: see text]. This problem generalizes the minimum k-union problem (MinkU) and is believed not to admit a subpolynomial approximation ratio. In this paper, we present a [Formula: see text]-approximation algorithm for MinPSMC, in which [Formula: see text] is the maximum size of a set in S. And when [Formula: see text], we present a bicriteria algorithm fully covering at least [Formula: see text] elements with approximation ratio [Formula: see text], where [Formula: see text] is a fixed number. These results are obtained by studying the minimum density subcollection problem with (or without) cardinality constraint, which might be of interest by itself. 

   more » « less
3. A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems

   https://doi.org/10.1007/s11590-023-02008-6  

   Liang, Wei; Zhang, Zhao; Du, Ding-Zhu (May 2023, Optimization Letters)

   In a sweep cover problem, mobile sensors move around to collect information from positions of interest (PoIs) periodically and timely. A PoI is sweep-covered if it is visited at least once in every time period t. In this paper, we study approximation algorithms on three types of sweep cover problems. The partial sweep cover problem (PSC) aims to use the minimum number of mobile sensors to sweep-cover at least a given number of PoIs. The prize-collecting sweep cover problem aims to minimize the cost of mobile sensors plus the penalties on those PoIs that are not sweep-covered. The budgeted sweep cover problem (BSC) aims to use a budgeted number N of mobile sensors to sweep-cover as many PoIs as possible. We propose a unified approach which can yield approximation algorithms for PSC and PCSC within approximation ratio at most 8, and a bicriteria (4, 1 2 )-approximation algorithm for BSC (that is, no more than 4N mobile sensors are used to sweep-cover at least 1 2 opt PoIs, where opt is the number of PoIs that can be sweep-covered by an optimal solution). Furthermore, our results for PSC and BSC can be extended to their weighted version, and our algorithm for PCSC answers a question proposed in Liang etal. (Theor Comput Sci, 2022) on PCSC 

   more » « less
4. Data-driven low-rank approximation for the electron-hole kernel and acceleration of time-dependent GW calculations

   https://doi.org/10.1038/s41524-025-01680-9  

   Hou, Bowen; Wu, Jinyuan; Chang_Lee, Victor; Guo, Jiaxuan; Liu, Luna Y; Qiu, Diana Y (December 2025, npj Computational Materials)

   Many-body interactions are essential for understanding non-linear optics and ultrafast spectroscopy of materials. Recent first principles approaches based on nonequilibrium Green’s function formalisms, such as the time-dependent adiabatic GW (TD-aGW) approach, can predict nonequilibrium dynamics of excited states including electron-hole interactions. However, the high-dimensionality of the electron-hole kernel poses significant computational challenges. Here, we develop a data-driven low-rank approximation for the electron-hole kernel, leveraging localized excitonic effects in the Hilbert space of crystalline systems to achieve significant data compression through singular value decomposition (SVD). We show that the subspace of non-zero singular values remains small even as the k-grid grows, ensuring computational tractability with extremely dense k-grids. This low-rank property enables at least 95% data compression and an order-of-magnitude speedup of TD-aGW calculations. Our approach avoids intensive training processes and eliminates time-accumulated errors, seen in previous approaches, providing a general framework for high-throughput, nonequilibrium simulation of light-driven dynamics in materials. 

   more » « less
5. Space Complexity of Minimum Cut Problems in Single-Pass Streams

   https://doi.org/10.4230/LIPIcs.ITCS.2025.43  

   Ding, Matthew; Garces, Alexandro; Li, Jason; Lin, Honghao; Nelson, Jelani; Shah, Vihan; Woodruff, David P (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   We consider the problem of finding a minimum cut of a weighted graph presented as a single-pass stream. While graph sparsification in streams has been intensively studied, the specific application of finding minimum cuts in streams is less well-studied. To this end, we show upper and lower bounds on minimum cut problems in insertion-only streams for a variety of settings, including for both randomized and deterministic algorithms, for both arbitrary and random order streams, and for both approximate and exact algorithms. One of our main results is an Õ(n/ε) space algorithm with fast update time for approximating a spectral cut query with high probability on a stream given in an arbitrary order. Our result breaks the Ω(n/ε²) space lower bound required of a sparsifier that approximates all cuts simultaneously. Using this result, we provide streaming algorithms with near optimal space of Õ(n/ε) for minimum cut and approximate all-pairs effective resistances, with matching space lower-bounds. The amortized update time of our algorithms is Õ(1), provided that the number of edges in the input graph is at least (n/ε²)^{1+o(1)}. We also give a generic way of incorporating sketching into a recursive contraction algorithm to improve the post-processing time of our algorithms. In addition to these results, we give a random-order streaming algorithm that computes the exact minimum cut on a simple, unweighted graph using Õ(n) space. Finally, we give an Ω(n/ε²) space lower bound for deterministic minimum cut algorithms which matches the best-known upper bound up to polylogarithmic factors. 

   more » « less