An official website of the United States government
We give a combinatorial polynomial-time algorithm to find a maximum weight independent set in perfect graphs of bounded degree that do not contain a prism or a hole of length four as an induced subgraph. An even pair in a graph is a pair of vertices all induced paths between which are even. An even set is a set of vertices every two of which are an even pair. We show that every perfect graph that does not contain a prism or a hole of length four as an induced subgraph has a balanced separator which is the union of a bounded number of even sets, where the bound depends only on the maximum degree of the graph. This allows us to solve the maximum weight independent set problem using the well-known submodular function minimization algorithm. Funding: This work was supported by the Engineering and Physical Sciences Research Council [Grant EP/V002813/1]; the National Science Foundation [Grants DMS-1763817, DMS-2120644, and DMS-2303251]; and Alexander von Humboldt-Stiftung.
more »
« less
This content will become publicly available on March 4, 2026
Structural graph and backward asymptotics of tent-like unimodal maps
The tent map family is arguably the simplest one-parametric family of maps with non-trivial dynamics and it is still an active subject of research. In recent works, the second author, jointly with J. Yorke, studied the structural graph and backward limits of S-unimodal maps. In this article, we generalize those results to tent-like unimodal maps. By tent-like here we mean maps that share fundamental properties that characterize tent maps, namely unimodal maps without wandering intervals nor attracting periodic orbits and whose structural graph has a finite number of nodes. This article was started under grant DMS-1832126 and then completed and published under grant DMS-2308225.
more »
« less
- PAR ID:
- 10612862
- Publisher / Repository:
- Taylor & Francis
- Date Published:
- Journal Name:
- Journal of difference equations and applications
- Volume:
- 31
- Issue:
- 3
- ISSN:
- 1023-6198
- Page Range / eLocation ID:
- 299 to 329
- Subject(s) / Keyword(s):
- Tent map graph of a dynamical system chaotic attractor backward trajectory unimodal map
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
While the forward trajectory of a point in a discrete dynamical system is always unique, in general, a point can have infinitely many backward trajectories. The union of the limit points of all backward trajectories through x was called by Hero the “special α-limit” (sα-limit for short) of x. In this article, we show that there is a hierarchy of sα-limits of points under iterations of a S-unimodal map: the size of the sα-limit of a point increases monotonically as the point gets closer and closer to the attractor. The sα-limit of any point of the attractor is the whole nonwandering set. This hierarchy reflects the structure of the graph of a S-unimodal map recently introduced jointly by Jim Yorke and the present author.more » « less
-
We investigate a class of composite nonconvex functions, where the outer function is the sum of univariate extended-real-valued convex functions and the inner function is the limit of difference-of-convex functions. A notable feature of this class is that the inner function may fail to be locally Lipschitz continuous. It covers a range of important, yet challenging, applications, including inverse optimal value optimization and problems under value-at-risk constraints. We propose an asymptotic decomposition of the composite function that guarantees epi-convergence to the original function, leading to necessary optimality conditions for the corresponding minimization problem. The proposed decomposition also enables us to design a numerical algorithm such that any accumulation point of the generated sequence, if it exists, satisfies the newly introduced optimality conditions. These results expand on the study of so-called amenable functions introduced by Poliquin and Rockafellar in 1992, which are compositions of convex functions with smooth maps, and the prox-linear methods for their minimization. To demonstrate that our algorithmic framework is practically implementable, we further present verifiable termination criteria and preliminary numerical results. Funding: Financial support from the National Science Foundation Division of Computing and Communication Foundations [Grant CCF-2416172] and Division of Mathematical Sciences [Grant DMS-2416250] and the National Cancer Institute, National Institutes of Health [Grant 1R01CA287413-01] is gratefully acknowledged.more » « less
-
Let ρ be a general law-invariant convex risk measure, for instance, the average value at risk, and let X be a financial loss, that is, a real random variable. In practice, either the true distribution μ of X is unknown, or the numerical computation of [Formula: see text] is not possible. In both cases, either relying on historical data or using a Monte Carlo approach, one can resort to an independent and identically distributed sample of μ to approximate [Formula: see text] by the finite sample estimator [Formula: see text] (μNdenotes the empirical measure of μ). In this article, we investigate convergence rates of [Formula: see text] to [Formula: see text]. We provide nonasymptotic convergence rates for both the deviation probability and the expectation of the estimation error. The sharpness of these convergence rates is analyzed. Our framework further allows for hedging, and the convergence rates we obtain depend on neither the dimension of the underlying assets nor the number of options available for trading. Funding: Daniel Bartl is grateful for financial support through the Vienna Science and Technology Fund [Grant MA16-021] and the Austrian Science Fund [Grants ESP-31 and P34743]. Ludovic Tangpi is supported by the National Science Foundation [Grant DMS-2005832] and CAREER award [Grant DMS-2143861].more » « less
-
We consider the sequential anomaly detection problem in the one-class setting when only the anomalous sequences are available and propose an adversarial sequential detector by solving a minimax problem to find an optimal detector against the worst-case sequences from a generator. The generator captures the dependence in sequential events using the marked point process model. The detector sequentially evaluates the likelihood of a test sequence and compares it with a time-varying threshold, also learned from data through the minimax problem. We demonstrate our proposed method’s good performance using numerical experiments on simulations and proprietary large-scale credit card fraud data sets. The proposed method can generally apply to detecting anomalous sequences. History: W. Nick Street served as the senior editor for this article. Funding: This work is partially supported by the National Science Foundation [Grants CAREER CCF-1650913, DMS-1938106, and DMS-1830210] and grant support from Macy’s Technology. Data Ethics & Reproducibility Note: The code capsule is available on Code Ocean at https://doi.org/10.24433/CO.2329910.v1 and in the e-Companion to this article (available at https://doi.org/10.1287/ijds.2023.0026 ).more » « less
