An official website of the United States government
Abstract Continuous-time Markov chains are frequently used to model the stochastic dynamics of (bio)chemical reaction networks. However, except in very special cases, they cannot be analyzed exactly. Additionally, simulation can be computationally intensive. An approach to address these challenges is to consider a more tractable diffusion approximation. Leite and Williams (Ann. Appl. Prob.29, 2019) proposed a reflected diffusion as an approximation for (bio)chemical reaction networks, which they called the constrained Langevin approximation (CLA) as it extends the usual Langevin approximation beyond the first time some chemical species becomes zero in number. Further explanation and examples of the CLA can be found in Anderson et al.( SIAM Multiscale Modeling Simul.17, 2019). In this paper, we extend the approximation of Leite and Williams to (nearly) density-dependent Markov chains, as a first step to obtaining error estimates for the CLA when the diffusion state space is one-dimensional, and we provide a bound for the error in a strong approximation. We discuss some applications for chemical reaction networks and epidemic models, and illustrate these with examples. Our method of proof is designed to generalize to higher dimensions, provided there is a Lipschitz Skorokhod map defining the reflected diffusion process. The existence of such a Lipschitz map is an open problem in dimensions more than one.
more »
« less
A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”
In the article “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs” (Networks39(1) (2002), 53‐60), Williams introduced an extended formulation for the spanning tree polytope of a planar graph. This formulation is remarkably small (using onlyO(n) variables and constraints) and remarkably strong (defining an integral polytope). In this note, we point out that Williams' formulation, as originally stated, is incorrect. Specifically, we construct a binary feasible solution to Williams' formulation that does not represent a spanning tree. Fortunately, there is a simple fix, which is to restrict the choice of the root vertices in the primal and dual spanning trees, whereas Williams explicitly allowed them to be chosen arbitrarily. The same flaw and fix apply to a subsequent formulation of Williams (“A zero‐one programming model for contiguous land acquisition.” Geographical Analysis34(4) (2002), 330‐349).
more »
« less
- Award ID(s):
- 1662757
- PAR ID:
- 10078297
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Networks
- Volume:
- 73
- Issue:
- 1
- ISSN:
- 0028-3045
- Page Range / eLocation ID:
- p. 135-142
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Two‐phase flow, a system where Stokes flow and Darcy flow are coupled, is of great importance in the Earth's interior, such as in subduction zones, mid‐ocean ridges, and hotspots. However, it remains challenging to solve the two‐phase equations accurately in the zero‐porosity limit, for example, when melt is fully frozen below solidus temperature. Here we propose a new three‐field formulation of the two‐phase system, with solid velocity (vs), total pressure (Pt), and fluid pressure (Pf) as unknowns, and present a robust finite‐element implementation, which can be used to solve problems in which domains of both zero porosity and non‐zero porosity are present. The reformulated equations include regularization to avoid singularities and exactly recover to the standard single‐phase incompressible Stokes problem at zero porosity. We verify the correctness of our implementation using the method of manufactured solutions and analytic solutions and demonstrate that we can obtain the expected convergence rates in both space and time. Example experiments, such as self‐compaction, falling block, and mid‐ocean ridge spreading show that this formulation can robustly resolve zero‐ and non‐zero‐porosity domains simultaneously, and can be used for a large range of applications in various geodynamic settings.more » « less
-
Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimizeregret, defined as the maximum difference between the solution’s cost and that of an optimal solution in hindsight once the input has been realized. For graph problems inP, such as shortest path and minimum spanning tree, robust polynomial-time algorithms that obtain a constant approximation on regret are known. In this paper, we study robust algorithms for minimizing regret inNP-hard graph optimization problems, and give constant approximations on regret for the classical traveling salesman and Steiner tree problems.more » « less
-
Abstract We study a class of bilevel spanning tree (BST) problems that involve two independent decision‐makers (DMs), the leader and the follower with different objectives, who jointly construct a spanning tree in a graph. The leader, who acts first, selects an initial subset of edges that do not contain a cycle, from the set under her control. The follower then selects the remaining edges to complete the construction of a spanning tree, but optimizes his own objective function. If there exist multiple optimal solutions for the follower that result in different objective function values for the leader, then the follower may choose either the one that is the most (optimistic version) or least (pessimistic version) favorable to the leader. We study BST problems with the sum‐ and bottleneck‐type objective functions for the DMs under both the optimistic and pessimistic settings. The polynomial‐time algorithms are then proposed in both optimistic and pessimistic settings for BST problems in which at least one of the DMs has the bottleneck‐type objective function. For BST problem with the sum‐type objective functions for both the leader and the follower, we provide an equivalent single‐level linear mixed‐integer programming formulation. A computational study is then presented to explore the efficacy of our reformulation.more » « less
-
We presentcalf, acost-awarelogicalframework for studying quantitative aspects of functional programs. Taking inspiration from recent work that reconstructs traditional aspects of programming languages in terms of a modal account ofphase distinctions, we argue that the cost structure of programs motivates a phase distinction betweenintensionandextension. Armed with this technology, we contribute a synthetic account of cost structure as a computational effect in which cost-aware programs enjoy an internal noninterference property: input/output behavior cannot depend on cost. As a full-spectrum dependent type theory,calfpresents a unified language for programming and specification of both cost and behavior that can be integrated smoothly with existing mathematical libraries available in type theoretic proof assistants. We evaluatecalfas a general framework for cost analysis by implementing two fundamental techniques for algorithm analysis: themethod of recurrence relationsandphysicist’s method for amortized analysis. We deploy these techniques on a variety of case studies: we prove a tight, closed bound for Euclid’s algorithm, verify the amortized complexity of batched queues, and derive tight, closed bounds for the sequential andparallelcomplexity of merge sort, all fully mechanized in the Agda proof assistant. Lastly we substantiate the soundness of quantitative reasoning incalfby means of a model construction.more » « less
