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 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
-
This paper focuses on the system identification of an important class of nonlinear systems: nonlinear systems that are linearly parameterized, which enjoy wide applications in robotics and other mechanical systems. We consider two system identification methods: least-squares estimation (LSE), which is a point estimation method; and set-membership estimation (SME), which estimates an uncertainty set that contains the true parameters. We provide non-asymptotic convergence rates for LSE and SME under i.i.d. control inputs and control policies with i.i.d. random perturbations, both of which are considered as non-active-exploration inputs. Compared with the counter-example based on piecewise-affine systems in the literature, the success of non-active exploration in our setting relies on a key assumption about the system dynamics: we require the system functions to be real-analytic. Our results, together with the piecewise-affine counter-example, reveal the importance of differentiability in nonlinear system identification through non-active exploration. Lastly, we numerically compare our theoretical bounds with the empirical performance of LSE and SME on a pendulum example and a quadrotor example.more » « less
-
Abstract In this paper we provide a thorough investigation of the cluster sampling scheme for Morris' elementary effects method (MM), a popular model‐free factor screening method originated in the setting of design and analysis of computational experiments. We first study the sampling mechanism underpinning the two sampling schemes of MM (i.e., cluster sampling and noncluster sampling) and unveil its nature as a two‐level nested sampling process. This in‐depth understanding sets up a foundation for tackling two important aspects of cluster sampling: budget allocation and sampling plan. On the one hand, we study the budget allocation problem for cluster sampling under the analysis of variance framework and derive optimal budget allocations for efficient estimation of the importance measures. On the other hand, we devise an efficient cluster sampling algorithm with two variants to achieve enhanced statistical properties. The numerical evaluations demonstrate the superiority of the proposed cluster sampling algorithm and the budget allocations derived (when used both separately and in conjunction) to existing cluster and noncluster sampling schemes.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1002/sam.11697
