亚洲男人的天堂2018av,欧美草比,久久久久久免费视频精选,国色天香在线看免费,久久久久亚洲av成人片仓井空

We prove that the discrete Laplace operator has a bounded $ H^\infty$-calculus,independent of the spatial mesh size. As an application, we obtain the discrete stochastic maximal $ L^p $-regularity estimate for a spatial semidiscretization of a stochastic parabolic equation. In addition, we derive some (nearly) sharp error estimates for this spatial semidiscretization.

We advance the theoretical study of $\{0, 1/2\}$-cuts for integer programming problems $\max\{c^T x \colon A x \leq b, x \text{ integer}\}$. Such cuts are Gomory-Chv\'atal cuts that only need multipliers of value $0$ or $1/2$ in their derivation. The intersection of all $\{0, 1/2\}$-cuts derived from $Ax \le b$ is denoted by $P_{1/2}$ and called the $\{0,1/2\}$-closure of $P = \{x : Ax \le b\}$. The primal separation problem for $\{0, 1/2\}$-cuts is: Given a vertex $\hat x$ of the integer hull of $P$ and some fractional point $x^* \in P$, does there exist a $\{0,1/2\}$-cut that is tight at $\hat x$ and violated by $x^*$? Primal separation is the key ingredient of primal cutting-plane approaches to integer programming. In general, primal separation for $\{0,1/2\}$-cuts is NP-hard. We present two cases for which primal separation is solvable in polynomial time. As an interesting side product, we obtain a(nother) simple proof that matching can be solved in polynomial time. Furthermore, since optimization over the Gomory-Chv\'atal closure is also NP-hard, there has been recent research on solving the optimization problem over the Gomory-Chv\'atal closure approximately. In a similar spirit, we show that the optimization problem over the $\{0,1/2\}$-closure can be solved in polynomial time up to a factor $(1 + \varepsilon)$, for any fixed $\varepsilon > 0$.

Originating in Girard's Linear logic, Ehrhard and Regnier's Taylor expansion of $\lambda$-terms has been broadly used as a tool to approximate the terms of several variants of the $\lambda$-calculus. Many results arise from a Commutation theorem relating the normal form of the Taylor expansion of a term to its B\"ohm tree. This led us to consider extending this formalism to the infinitary $\lambda$-calculus, since the $\Lambda_{\infty}^{001}$ version of this calculus has B\"ohm trees as normal forms and seems to be the ideal framework to reformulate the Commutation theorem. We give a (co-)inductive presentation of $\Lambda_{\infty}^{001}$. We define a Taylor expansion on this calculus, and state that the infinitary $\beta$-reduction can be simulated through this Taylor expansion. The target language is the usual resource calculus, and in particular the resource reduction remains finite, confluent and terminating. Finally, we state the generalised Commutation theorem and use our results to provide simple proofs of some normalisation and confluence properties in the infinitary $\lambda$-calculus.

Out-of-distribution (OOD) detection discerns OOD data where the predictor cannot make valid predictions as in-distribution (ID) data, thereby increasing the reliability of open-world classification. However, it is typically hard to collect real out-of-distribution (OOD) data for training a predictor capable of discerning ID and OOD patterns. This obstacle gives rise to data generation-based learning methods, synthesizing OOD data via data generators for predictor training without requiring any real OOD data. Related methods typically pre-train a generator on ID data and adopt various selection procedures to find those data likely to be the OOD cases. However, generated data may still coincide with ID semantics, i.e., mistaken OOD generation remains, confusing the predictor between ID and OOD data. To this end, we suggest that generated data (with mistaken OOD generation) can be used to devise an auxiliary OOD detection task to facilitate real OOD detection. Specifically, we can ensure that learning from such an auxiliary task is beneficial if the ID and the OOD parts have disjoint supports, with the help of a well-designed training procedure for the predictor. Accordingly, we propose a powerful data generation-based learning method named Auxiliary Task-based OOD Learning (ATOL) that can relieve the mistaken OOD generation. We conduct extensive experiments under various OOD detection setups, demonstrating the effectiveness of our method against its advanced counterparts.

We obtain an expression for the error in the approximation of $f(A) \boldsymbol{b}$ and $\boldsymbol{b}^T f(A) \boldsymbol{b}$ with rational Krylov methods, where $A$ is a symmetric matrix, $\boldsymbol{b}$ is a vector and the function $f$ admits an integral representation. The error expression is obtained by linking the matrix function error with the error in the approximate solution of shifted linear systems using the same rational Krylov subspace, and it can be exploited to derive both a priori and a posteriori error bounds. The error bounds are a generalization of the ones given in [T. Chen, A. Greenbaum, C. Musco, C. Musco, SIAM J. Matrix Anal. Appl., 43 (2022), pp. 787--811] (arXiv:2106.09806) for the Lanczos method for matrix functions. A technique that we employ in the rational Krylov context can also be applied to refine the bounds for the Lanczos case.

This paper presents a randomized algorithm for the problem of single-source shortest paths on directed graphs with real (both positive and negative) edge weights. Given an input graph with $n$ vertices and $m$ edges, the algorithm completes in $\tilde{O}(mn^{8/9})$ time with high probability. For real-weighted graphs, this result constitutes the first asymptotic improvement over the classic $O(mn)$-time algorithm variously attributed to Shimbel, Bellman, Ford, and Moore.

We study integration and $L^2$-approximation of functions of infinitely many variables in the following setting: The underlying function space is the countably infinite tensor product of univariate Hermite spaces and the probability measure is the corresponding product of the standard normal distribution. The maximal domain of the functions from this tensor product space is necessarily a proper subset of the sequence space $\mathbb{R}^\mathbb{N}$. We establish upper and lower bounds for the minimal worst case errors under general assumptions; these bounds do match for tensor products of well-studied Hermite spaces of functions with finite or with infinite smoothness. In the proofs we employ embedding results, and the upper bounds are attained constructively with the help of multivariate decomposition methods.

Erd\H{o}s and West (Discrete Mathematics'85) considered the class of $n$ vertex intersection graphs which have a {\em $d$-dimensional} {\em $t$-representation}, that is, each vertex of a graph in the class has an associated set consisting of at most $t$ $d$-dimensional axis-parallel boxes. In particular, for a graph $G$ and for each $d \geq 1$, they consider $i_d(G)$ to be the minimum $t$ for which $G$ has such a representation. For fixed $t$ and $d$, they consider the class of $n$ vertex labeled graphs for which $i_d(G) \leq t$, and prove an upper bound of $(2nt+\frac{1}{2})d \log n - (n - \frac{1}{2})d \log(4\pi t)$ on the logarithm of size of the class. In this work, for fixed $t$ and $d$ we consider the class of $n$ vertex unlabeled graphs which have a {\em $d$-dimensional $t$-representation}, denoted by $\mathcal{G}_{t,d}$. We address the problem of designing a succinct data structure for the class $\mathcal{G}_{t,d}$ in an attempt to generalize the relatively recent results on succinct data structures for interval graphs (Algorithmica'21). To this end, for each $n$ such that $td^2$ is in $o(n / \log n)$, we first prove a lower bound of $(2dt-1)n \log n - O(ndt \log \log n)$-bits on the size of any data structure for encoding an arbitrary graph that belongs to $\mathcal{G}_{t,d}$. We then present a $((2dt-1)n \log n + dt\log t + o(ndt \log n))$-bit data structure for $\mathcal{G}_{t,d}$ that supports navigational queries efficiently. Contrasting this data structure with our lower bound argument, we show that for each fixed $t$ and $d$, and for all $n \geq 0$ when $td^2$ is in $o(n/\log n)$ our data structure for $\mathcal{G}_{t,d}$ is succinct. As a byproduct, we also obtain succinct data structures for graphs of bounded boxicity (denoted by $d$ and $t = 1$) and graphs of bounded interval number (denoted by $t$ and $d=1$) when $td^2$ is in $o(n/\log n)$.

We design and implement two single-pass semi-streaming algorithms for the maximum weight $k$-disjoint matching ($k$-DM) problem. Given an integer $k$, the $k$-DM problem is to find $k$ pairwise edge-disjoint matchings such that the sum of the weights of the matchings is maximized. For $k \geq 2$, this problem is NP-hard. Our first algorithm is based on the primal-dual framework of a linear programming relaxation of the problem and is $\frac{1}{3+\varepsilon}$-approximate. We also develop an approximation preserving reduction from $k$-DM to the maximum weight $b$-matching problem. Leveraging this reduction and an existing semi-streaming $b$-matching algorithm, we design a $\frac{k}{(2+\varepsilon)(k+1)}$-approximate semi-streaming algorithm for $k$-DM. For any constant $\varepsilon > 0$, both of these algorithms require $O(nk \log_{1+\varepsilon}^2 n)$ bits of space. To the best of our knowledge, this is the first study of semi-streaming algorithms for the $k$-DM problem. We compare our two algorithms to state-of-the-art offline algorithms on 82 real-world and synthetic test problems. On the smaller instances, our streaming algorithms used significantly less memory (ranging from 6$\times$ to 114$\times$ less) and were faster in runtime than the offline algorithms. Our solutions were often within 5\% of the best weights from the offline algorithms. On a collection of six large graphs with a memory limit of 1 TB and with $k=8$, the offline algorithms terminated only on one graph (mycielskian20). The best offline algorithm on this instance required 640 GB of memory and 20 minutes to complete. In contrast, our slowest streaming algorithm for this instance took under four minutes and produced a matching that was 18\% better in weight, using only 1.4 GB of memory.