An official website of the United States government
We describe a 3/2-approximation algorithm, \lse, for computing a b-edgecover of minimum weight in a graph with weights on the edges. The b-edgecover problem is a generalization of the better-known Edge Cover problem in graphs, where the objective is to choose a subset C of edges in the graph such that at least a specified number b(v) of edges in C are incident on each vertex v. In the weighted b-edgecover problem, we minimize the sum of the weights of the edges in C. We prove that the Locally Subdominant edge (LSE) algorithm computes the same b-edge cover as the one obtained by the Greedy algorithm for the problem. However, the Greedy algorithm requires edges to be sorted by their effective weights, and these weights need to be updated after each iteration. These requirements make the Greedy algorithm sequential and impractical for massive graphs. The LSE algorithm avoids the sorting step, and is amenable for parallelization. We implement the algorithm on a serial machine and compare its performance against a collection of approximation algorithms for the b-edge cover problem. Our results show that the algorithm is 3 to 5 times faster than the Greedy algorithm on a serial processor. The approximate edge covers obtained by the LSE algorithm have weights greater by at most 17% of the optimal weight for problems where we could compute the latter. We also investigate the relationship between the b-edge cover and the b-matching problems, show that the latter has a faster implementation since edge weights are static in this algorithm, and obtain a heuristic solution for the former from the latter.
more »
« less
Sequential metamodel‐based approaches to level‐set estimation under heteroscedasticity
Abstract This paper proposes two sequential metamodel‐based methods for level‐set estimation (LSE) that leverage the uniform bound built on stochastic kriging: predictive variance reduction (PVR) and expected classification improvement (ECI). We show that PVR and ECI possess desirable theoretical performance guarantees and provide closed‐form expressions for their respective sequential sampling criteria to seek the next design point for performing simulation runs, allowing computationally efficient one‐iteration look‐ahead updates. To enhance understanding, we reveal the connection between PVR and ECI's sequential sampling criteria. Additionally, we propose integrating a budget allocation feature with PVR and ECI, which improves computational efficiency and potentially enhances robustness to the impacts of heteroscedasticity. Numerical studies demonstrate the superior performance of the proposed methods compared to state‐of‐the‐art benchmarking approaches when given a fixed simulation budget, highlighting their effectiveness in addressing LSE problems.
more »
« less
- PAR ID:
- 10535617
- Publisher / Repository:
- Wiley
- Date Published:
- Journal Name:
- Statistical Analysis and Data Mining: The ASA Data Science Journal
- Volume:
- 17
- Issue:
- 3
- ISSN:
- 1932-1864
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract The knowledge of the material budget with a high precision is fundamental for measurements of direct photonproduction using the photon conversion method due to its direct impact on the total systematic uncertainty. Moreover, it influences many aspects of the charged-particle reconstruction performance. In this article, two procedures to determine data-driven corrections to the material-budget description in ALICE simulation software are developed.One is based on the precise knowledge of the gas composition in the Time Projection Chamber. The other is based on the robustness of the ratio between the produced number of photons and charged particles, to a large extent due to the approximate isospin symmetry in the number of produced neutral and charged pions. Both methods are applied to ALICE data allowing for a reduction of theoverall material budget systematic uncertainty from 4.5% down to2.5%. Using these methods, a locally correct material budget is alsoachieved. The two proposed methods are generic and can be applied toany experiment in a similar fashion.more » « less
-
Abstract Cognitive diagnosis models (CDMs) are psychometric tools that can provide detailed diagnostic information. The expectation-maximization (EM) algorithm is one of the most widely used methods for estimating parameters of CDMs. However, when the number of dimensions is large, the EM algorithm may become infeasible due to the computational burden. This paper proposes an efficient stochastic EM algorithm, which adopts a sequential Gibbs sampling method to reduce the computational cost. We investigate the performance of the proposed method through extensive simulations and examine its viability using two real datasets.more » « less
-
Abstract A major subglacial lake, Lake Snow Eagle (LSE), was identified in East Antarctica by airborne geophysical surveys. LSE, contained within a subglacial canyon, likely hosts a valuable sediment record of the geological and glaciological changes of interior East Antarctica. Understanding past lake activity is crucial for interpreting this record. Here, we present the englacial radiostratigraphy in the LSE area mapped by airborne ice-penetrating radar, which reveals a localized high-amplitude variation in ice unit thickness that is estimated to be ∼12 ka old. Using an ice-flow model that simulates englacial stratigraphy, we investigate the origin of this feature and its relationship to changes in ice dynamical boundary conditions. Our results reveal that local snowfall redistribution initiated around the early Holocene is likely the primary cause, resulting from a short-wavelength (∼10 km) high-amplitude (∼20 m) ice surface slope variation caused by basal lubrication over a large subglacial lake. This finding indicates an increase in LSE water volume during the Holocene, illustrating the sensitivity in volume of a major topographically constrained subglacial lake across a single glacial cycle. This study demonstrates how englacial stratigraphy can provide valuable insight into subglacial hydrological changes before modern satellite observations, both for LSE and potentially at other locations.more » « less
-
Abstract Accurate modeling of dependencies between variables of interest is imperative for understanding biophysical processes and mechanisms relevant to biogeosciences research. This study presents copula‐based cosimulation (CopCoSim) as an approach to model the temporal or spatial joint distributions of multiple variables by capturing their dependencies and correlations. We compared CopCoSim with the traditional Sequential Gaussian CoSimulation (SGCoSim) technique through two applications, representing one (i.e., time) and two dimensions (i.e., space) on a topic relevant to biogeosciences. Specifically, we present an application for soil CO2efflux, which is a major flux in the global carbon budget, using two case studies: (a) temporal distribution of soil CO2efflux and temperature and (b) spatial distribution of soil CO2efflux and temperature across the conterminous United States (CONUS). The methodology involves three steps: selecting a representative training data set, applying stochastic simulation methods, and evaluating model performance. The results indicate that CopCoSim provides a more accurate model with higher precision for representing variables of interest. CopCoSim better reproduces the univariate probability distribution, temporal or spatial autocorrelation, and dependency relationships between the predictor and response variables. Because CopCoSim does not rely on linear correlation structures and normality assumptions, it captures complex dependence structures and behaviors among variables. We propose that CopCoSim is useful for research in biogeosciences, where variables of interest (e.g., soil CO2efflux and temperature) are often interdependent and exhibit complex temporal or spatial patterns.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- https://doi.org/10.1002/sam.11697
