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

We prove that every simple 2-connected subcubic graph on $n$ vertices with $n_2$ vertices of degree 2 has a TSP walk of length at most $\frac{5n+n_2}{4}-1$, confirming a conjecture of Dvo\v{r}\'ak, Kr\'al', and Mohar. This bound is best possible; there are infinitely many subcubic and cubic graphs whose minimum TSP walks have lengths $\frac{5n+n_2}{4}-1$ and $\frac{5n}{4} - 2$ respectively. We characterize the extremal subcubic examples meeting this bound. We also give a quadratic-time combinatorial algorithm for finding such a TSP walk. In particular, we obtain a $\frac{5}{4}$-approximation algorithm for the graphic TSP on simple cubic graphs, improving on the previously best known approximation ratio of $\frac{9}{7}$.

Confidence intervals are a standard technique for analyzing data. When applied to time series, confidence intervals are computed for each time point separately. Alternatively, we can compute confidence bands, where we are required to find the smallest area enveloping $k$ time series, where $k$ is a user parameter. Confidence bands can be then used to detect abnormal time series, not just individual observations within the time series. We will show that despite being an NP-hard problem it is possible to find optimal confidence band for some $k$. We do this by considering a different problem: discovering regularized bands, where we minimize the envelope area minus the number of included time series weighted by a parameter $\alpha$. Unlike normal confidence bands we can solve the problem exactly by using a minimum cut. By varying $\alpha$ we can obtain solutions for various $k$. If we have a constraint $k$ for which we cannot find appropriate $\alpha$, we demonstrate a simple algorithm that yields $O(\sqrt{n})$ approximation guarantee by connecting the problem to a minimum $k$-union problem. This connection also implies that we cannot approximate the problem better than $O(n^{1/4})$ under some (mild) assumptions. Finally, we consider a variant where instead of minimizing the area we minimize the maximum width. Here, we demonstrate a simple 2-approximation algorithm and show that we cannot achieve better approximation guarantee.

There are distributed graph algorithms for finding maximal matchings and maximal independent sets in $O(\Delta + \log^* n)$ communication rounds; here $n$ is the number of nodes and $\Delta$ is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on $n$ is optimal: these problems cannot be solved in $o(\log^* n)$ rounds even if $\Delta = 2$. However, the dependency on $\Delta$ is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. We show that any algorithm that finds a maximal matching or maximal independent set with probability at least $1-1/n$ requires $\Omega(\min\{\Delta,\log \log n / \log \log \log n\})$ rounds in the LOCAL model of distributed computing. As a corollary, it follows that any deterministic algorithm that finds a maximal matching or maximal independent set requires $\Omega(\min\{\Delta, \log n / \log \log n\})$ rounds; this is an improvement over prior lower bounds also as a function of $n$.

The $k$-Center problem is one of the most popular clustering problems. After decades of work, the complexity of most of its variants on general metrics is now well understood. Surprisingly, this is not the case for a natural setting that often arises in practice, namely the Euclidean setting, in which the input points are points in $\mathbb{R}^d$, and the distance between them is the standard $\ell_2$ Euclidean distance. In this work, we study two Euclidean $k$-Center variants, the Matroid Center problem on the real line and the Robust Euclidean $k$-Supplier problem, and provide algorithms that improve upon the best approximation guarantees known for these problems. In particular, we present a simple $2.5$-approximation algorithm for the Matroid Center problem on the real line, thus improving upon the $3$-approximation factor algorithm of Chen, Li, Liang, and Wang (2016) that works for general metrics. Moreover, we present a $(1 + \sqrt{3})$-approximation algorithm for the Robust Euclidean $k$-Supplier problem, thus improving upon the state-of-the-art $3$-approximation algorithm for Robust $k$-Supplier on general metrics and matching the best approximation factor known for the non-robust setting by Nagarajan, Schieber and Shachnai (2020).

In the present study, we consider sparse representations of solutions to Dirichlet and heat equation problems with random boundary or initial conditions. To analyze the random signals, two types of sparse representations are developed, namely stochastic pre-orthogonal adaptive Fourier decomposition 1 and 2 (SPOAFD1 and SPOAFD2). Due to adaptive parameter selecting of SPOAFDs at each step, we obtain analytical sparse solutions of the SPDE problems with fast convergence.

Computing Nash equilibrium in multi-agent games is a longstanding challenge at the interface of game theory and computer science. It is well known that a general normal form game in N players and k strategies requires exponential space simply to write down. This Curse of Multi-Agents prompts the study of succinct games which can be written down efficiently. A canonical example of a succinct game is the graphical game which models players as nodes in a graph interacting with only their neighbors in direct analogy with markov random fields. Graphical games have found applications in wireless, financial, and social networks. However, computing the nash equilbrium of graphical games has proven challenging. Even for polymatrix games, a model where payoffs to an agent can be written as the sum of payoffs of interactions with the agent's neighbors, it has been shown that computing an epsilon approximate nash equilibrium is PPAD hard for epsilon smaller than a constant. The focus of this work is to circumvent this computational hardness by considering average case graph models i.e random graphs. We provide a quasipolynomial time approximation scheme (QPTAS) for computing an epsilon approximate nash equilibrium of polymatrix games on random graphs with edge density greater than poly(k, 1/epsilon, ln(N))$ with high probability. Furthermore, with the same runtime we can compute an epsilon-approximate Nash equilibrium that epsilon-approximates the maximum social welfare of any nash equilibrium of the game. Our primary technical innovation is an "accelerated rounding" of a novel hierarchical convex program for the nash equilibrium problem. Our accelerated rounding also yields faster algorithms for Max-2CSP on the same family of random graphs, which may be of independent interest.

We study the edges dissolution approximation (EDA) of Carnegie et al. We begin by repeating an observation from Carnegie et al., namely that in the dyad-independent case, the exact result is tractable. We then observe that taking the sparse limit of the exact result leads to a different approximation than that in Carnegie et al. We prove that this new approximation is better than the old approximation for sparse dyad-independent models, and we show via simulation that the new approximation tends to perform better than the old approximation for sparse models with sufficiently weak dyad-dependence. We then turn to general dyad-dependent models, proving that both the old and new approximations are asymptotically exact as the time step size goes to zero, for arbitrary dyad-dependent terms and some dyad-dependent constraints. In demonstrating this result, we identify a Markov chain, defined for any sufficiently small time step, whose cross-sectional and durational behavior is exactly that we desire of the EDA. This Markov chain can be simulated, and we do so for a dyad-dependent model, showing that it eliminates the biases present with either of the dyad-independent-derived approximations.

We introduce a novel minimal order hybrid Discontinuous Galerkin (HDG) and a novel mass conserving mixed stress (MCS) method for the approximation of incompressible flows. For this we employ the $H(\operatorname{div})$-conforming linear Brezzi-Douglas-Marini space and the lowest order Raviart-Thomas space for the approximation of the velocity and the vorticity, respectively. Our methods are based on the physically correct diffusive flux $-\nu \varepsilon(u)$ and provide exactly divergence-free discrete velocity solutions, optimal (pressure robust) error estimates and a minimal number of coupling degrees of freedom. For the stability analysis we introduce a new Korn-like inequality for vector-valued element-wise $H^1$ and normal continuous functions. Numerical examples conclude the work where the theoretical findings are validated and the novel methods are compared in terms of condition numbers with respect to discrete stability parameters.

Gaussian covariance graph model is a popular model in revealing underlying dependency structures among random variables. A Bayesian approach to the estimation of covariance structures uses priors that force zeros on some off-diagonal entries of covariance matrices and put a positive definite constraint on matrices. In this paper, we consider a spike and slab prior on off-diagonal entries, which uses a mixture of point-mass and normal distribution. The point-mass naturally introduces sparsity to covariance structures so that the resulting posterior from this prior renders covariance structure learning. Under this prior, we calculate posterior model probabilities of covariance structures using Laplace approximation. We show that the error due to Laplace approximation becomes asymptotically marginal at some rate depending on the posterior convergence rate of covariance matrix under the Frobenius norm. With the approximated posterior model probabilities, we propose a new framework for estimating a covariance structure. Since the Laplace approximation is done around the mode of conditional posterior of covariance matrix, which cannot be obtained in the closed form, we propose a block coordinate descent algorithm to find the mode and show that the covariance matrix can be estimated using this algorithm once the structure is chosen. Through a simulation study based on five numerical models, we show that the proposed method outperforms graphical lasso and sample covariance matrix in terms of root mean squared error, max norm, spectral norm, specificity, and sensitivity. Also, the advantage of the proposed method is demonstrated in terms of accuracy compared to our competitors when it is applied to linear discriminant analysis (LDA) classification to breast cancer diagnostic dataset.

In this paper, from a theoretical perspective, we study how powerful graph neural networks (GNNs) can be for learning approximation algorithms for combinatorial problems. To this end, we first establish a new class of GNNs that can solve strictly a wider variety of problems than existing GNNs. Then, we bridge the gap between GNN theory and the theory of distributed local algorithms to theoretically demonstrate that the most powerful GNN can learn approximation algorithms for the minimum dominating set problem and the minimum vertex cover problem with some approximation ratios and that no GNN can perform better than with these ratios. This paper is the first to elucidate approximation ratios of GNNs for combinatorial problems. Furthermore, we prove that adding coloring or weak-coloring to each node feature improves these approximation ratios. This indicates that preprocessing and feature engineering theoretically strengthen model capabilities.