The Gromov-Hausdorff distance ($d_\mathrm{GH}$) provides a natural way of quantifying the dissimilarity between two given metric spaces. It is known that computing $d_\mathrm{GH}$ between two finite metric spaces is NP-hard, even in the case of finite ultrametric spaces which are highly structured metric spaces in the sense that they satisfy the so-called \emph{strong triangle inequality}. Ultrametric spaces naturally arise in many applications such as hierarchical clustering, phylogenetics, genomics, and even linguistics. By exploiting the special structures of ultrametric spaces, (1) we identify a one parameter family $\{d_\mathrm{GH}^{(p)}\}_{p\in[1,\infty]}$ of distances defined in a flavor similar to the Gromov-Hausdorff distance on the collection of finite ultrametric spaces, and in particular $d_\mathrm{GH}^{(1)} =d_\mathrm{GH}$. The extreme case when $p=\infty$, which we also denote by $u_\mathrm{GH}$, turns out to be an ultrametric on the collection of ultrametric spaces. Whereas for all $p\in[1,\infty)$, $d_\mathrm{GH}^{(p)}$ yields NP-hard problems, we prove that surprisingly $u_\mathrm{GH}$ can be computed in polynomial time. The proof is based on a structural theorem for $u_\mathrm{GH}$ established in this paper; (2) inspired by the structural theorem for $u_\mathrm{GH}$, and by carefully leveraging properties of ultrametric spaces, we also establish a structural theorem for $d_\mathrm{GH}$ when restricted to ultrametric spaces. This structural theorem allows us to identify special families of ultrametric spaces on which $d_\mathrm{GH}$ is computationally tractable. These families are determined by properties related to the doubling constant of metric space. Based on these families, we devise a fixed-parameter tractable (FPT) algorithm for computing the exact value of $d_\mathrm{GH}$ between ultrametric spaces. We believe ours is the first such algorithm to be identified.
相關內容
A graph $G$ is called self-ordered (a.k.a asymmetric) if the identity permutation is its only automorphism. Equivalently, there is a unique isomorphism from $G$ to any graph that is isomorphic to $G$. We say that $G=(V,E)$ is robustly self-ordered if the size of the symmetric difference between $E$ and the edge-set of the graph obtained by permuting $V$ using any permutation $\pi:V\to V$ is proportional to the number of non-fixed-points of $\pi$. In this work, we initiate the study of the structure, construction and utility of robustly self-ordered graphs. We show that robustly self-ordered bounded-degree graphs exist (in abundance), and that they can be constructed efficiently, in a strong sense. Specifically, given the index of a vertex in such a graph, it is possible to find all its neighbors in polynomial-time (i.e., in time that is poly-logarithmic in the size of the graph). We also consider graphs of unbounded degree, seeking correspondingly unbounded robustness parameters. We again demonstrate that such graphs (of linear degree) exist (in abundance), and that they can be constructed efficiently, in a strong sense. This turns out to require very different tools. Specifically, we show that the construction of such graphs reduces to the construction of non-malleable two-source extractors (with very weak parameters but with some additional natural features). We demonstrate that robustly self-ordered bounded-degree graphs are useful towards obtaining lower bounds on the query complexity of testing graph properties both in the bounded-degree and the dense graph models. One of the results that we obtain, via such a reduction, is a subexponential separation between the query complexities of testing and tolerant testing of graph properties in the bounded-degree graph model.
In the Geometric Median problem with outliers, we are given a finite set of points in d-dimensional real space and an integer m, the goal is to locate a new point in space (center) and choose m of the input points to minimize the sum of the Euclidean distances from the center to the chosen points. This problem can be solved "almost exactly" in polynomial time if d is fixed and admits an approximation scheme PTAS in high dimensions. However, the complexity of the problem was an open question. We prove that, if the dimension of space is not fixed, Geometric Median with outliers is strongly NP-hard, does not admit approximation schemes FPTAS unless P=NP, and is W[1]-hard with respect to the parameter m. The proof is done by a reduction from the Independent Set problem. Based on a similar reduction, we also get the NP-hardness of closely related geometric 2-clustering problems in which it is required to partition a given set of points into two balanced clusters minimizing the cost of median clustering. Finally, we study Geometric Median with outliers in $\ell_\infty$ space and prove the same complexity results as for the Euclidean problem.
We study variants of the mean problem under the $p$-Dynamic Time Warping ($p$-DTW) distance, a popular and robust distance measure for sequential data. In our setting we are given a set of finite point sequences over an arbitrary metric space and we want to compute a mean point sequence of given length that minimizes the sum of $p$-DTW distances, each raised to the $q$th power, between the input sequences and the mean sequence. In general, the problem is $\mathrm{NP}$-hard and known not to be fixed-parameter tractable in the number of sequences. We show that it is even hard to approximate within any constant factor unless $\mathrm{P} = \mathrm{NP}$ and moreover if there exists a $\delta>0$ such that there is a $(\log n)^{\delta}$-approximation algorithm for DTW mean then $\mathrm{NP} \subseteq \mathrm{QP}$. On the positive side, we show that restricting the length of the mean sequence significantly reduces the hardness of the problem. We give an exact algorithm running in polynomial time for constant-length means. We explore various approximation algorithms that provide a trade-off between the approximation factor and the running time. Our approximation algorithms have a running time with only linear dependency on the number of input sequences. In addition, we use our mean algorithms to obtain clustering algorithms with theoretical guarantees.
Hypergeometric structures in single and multiscale Feynman integrals emerge in a wide class of topologies. Using integration-by-parts relations, associated master or scalar integrals have to be calculated. For this purpose it appears useful to devise an automated method which recognizes the respective (partial) differential equations related to the corresponding higher transcendental functions. We solve these equations through associated recursions of the expansion coefficient of the multivalued formal Taylor series. The expansion coefficients can be determined using either the package {\tt Sigma} in the case of linear difference equations or by applying heuristic methods in the case of partial linear difference equations. In the present context a new type of sums occurs, the Hurwitz harmonic sums, and generalized versions of them. The code {\tt HypSeries} transforming classes of differential equations into analytic series expansions is described. Also partial difference equations having rational solutions and rational function solutions of Pochhammer symbols are considered, for which the code {\tt solvePartialLDE} is designed. Generalized hypergeometric functions, Appell-,~Kamp\'e de F\'eriet-, Horn-, Lauricella-Saran-, Srivasta-, and Exton--type functions are considered. We illustrate the algorithms by examples.
The ternary relation $B(x,y,z)$ of betweenness states that an element $y$ is between the elements $x$ and $z$, in some sense depending on the considered structure. In a partially ordered set $(N,\leq)$, $B(x,y,z):\Longleftrightarrow x<y<z\vee z<y<x$. The corresponding betweenness structure is $(N,B)$. The class of betweenness structures of linear orders is first-order definable. That of partial orders is monadic second-order definable. An order-theoretic tree is a partial order such that the set of elements larger that any element is linearly ordered and any two elements have an upper-bound. Finite or infinite rooted trees ordered by the ancestor relation are order-theoretic trees. In an order-theoretic tree, we define $B(x,y,z)$ to mean that $x<y<z$ or $z<y<x$ or $x<y\leq x\sqcup z$ or $z<y\leq x\sqcup z$ provided the least upper-bound $x\sqcup z$ of $x$ and $z$ is defined when $x$ and $z$ are incomparable. In a previous article, we established that the corresponding class of betweenness structures is monadic second-order definable.We prove here that the induced substructures of the betweenness structures of the countable order-theoretic trees form a monadic second-order definable class, denoted by IBO. The proof uses a variant of cographs, the partitioned probe cographs, and their known six finite minimal excluded induced subgraphs called the bounds of the class. This proof links two apparently unrelated topics: cographs and order-theoretic trees.However, the class IBO has finitely many bounds, i.e., minimal excluded finite induced substructures. Hence it is first-order definable. The proof of finiteness uses well-quasi-orders and does not provide the finite list of bounds. Hence, the associated first-order defining sentence is not known.
We present a novel class of projected methods, to perform statistical analysis on a data set of probability distributions on the real line, with the 2-Wasserstein metric. We focus in particular on Principal Component Analysis (PCA) and regression. To define these models, we exploit a representation of the Wasserstein space closely related to its weak Riemannian structure, by mapping the data to a suitable linear space and using a metric projection operator to constrain the results in the Wasserstein space. By carefully choosing the tangent point, we are able to derive fast empirical methods, exploiting a constrained B-spline approximation. As a byproduct of our approach, we are also able to derive faster routines for previous work on PCA for distributions. By means of simulation studies, we compare our approaches to previously proposed methods, showing that our projected PCA has similar performance for a fraction of the computational cost and that the projected regression is extremely flexible even under misspecification. Several theoretical properties of the models are investigated and asymptotic consistency is proven. Two real world applications to Covid-19 mortality in the US and wind speed forecasting are discussed.
In the current work we are concerned with sequences of graphs having a grid geometry, with a uniform local structure in a bounded domain $\Omega\subset {\mathbb R}^d$, $d\ge 1$. When $\Omega=[0,1]$, such graphs include the standard Toeplitz graphs and, for $\Omega=[0,1]^d$, the considered class includes $d$-level Toeplitz graphs. In the general case, the underlying sequence of adjacency matrices has a canonical eigenvalue distribution, in the Weyl sense, and it has been shown in the theoretical part of this work that we can associate to it a symbol $\boldsymbol{\mathfrak{f}}$. The knowledge of the symbol and of its basic analytical features provides key information on the eigenvalue structure in terms of localization, spectral gap, clustering, and global distribution. In the present paper, many different applications are discussed and various numerical examples are presented in order to underline the practical use of the developed theory. Tests and applications are mainly obtained from the approximation of differential operators via numerical schemes such as Finite Differences (FDs), Finite Elements (FEs), and Isogeometric Analysis (IgA). Moreover, we show that more applications can be taken into account, since the results presented here can be applied as well to study the spectral properties of adjacency matrices and Laplacian operators of general large graphs and networks, whenever the involved matrices enjoy a uniform local structure.
Let $G$ be a strongly connected directed graph and $u,v,w\in V(G)$ be three vertices. Then $w$ strongly resolves $u$ to $v$ if there is a shortest $u$-$w$-path containing $v$ or a shortest $w$-$v$-path containing $u$. A set $R\subseteq V(G)$ of vertices is a strong resolving set for a directed graph $G$ if for every pair of vertices $u,v\in V(G)$ there is at least one vertex in $R$ that strongly resolves $u$ to $v$ and at least one vertex in $R$ that strongly resolves $v$ to $u$. The distances of the vertices of $G$ to and from the vertices of a strong resolving set $R$ uniquely define the connectivity structure of the graph. The Strong Metric Dimension of a directed graph $G$ is the size of a smallest strong resolving set for $G$. The decision problem Strong Metric Dimension is the question whether $G$ has a strong resolving set of size at most $r$, for a given directed graph $G$ and a given number $r$. In this paper we study undirected and directed co-graphs and introduce linear time algorithms for Strong Metric Dimension. These algorithms can also compute strong resolving sets for co-graphs in linear time.
In this paper we propose a new algorithm for solving large-scale algebraic Riccati equations with low-rank structure, which is based on the found elegant closed form of the stabilizing solution that involves an intrinsic Toeplitz structure and the fast Fourier transform used to accelerate the multiplication of a Toeplitz matrix and vectors. The algorithm works without unnecessary assumptions, shift selection trategies, or matrix calculations of the cubic order with respect to the problem scale. Numerical examples are given to illustrate its features. Besides, we show that it is theoretically equivalent to several algorithms existing in the literature in the sense that they all produce the same sequence under the same parameter setting.
We study timed systems in which some timing features are unknown parameters. Parametric timed automata (PTAs) are a classical formalism for such systems but for which most interesting problems are undecidable. Notably, the parametric reachability emptiness problem, i.e., the emptiness of the parameter valuations set allowing to reach some given discrete state, is undecidable. Lower-bound/upper-bound parametric timed automata (L/U-PTAs) achieve decidability for reachability properties by enforcing a separation of parameters used as upper bounds in the automaton constraints, and those used as lower bounds. In this paper, we first study reachability. We exhibit a subclass of PTAs (namely integer-points PTAs) with bounded rational-valued parameters for which the parametric reachability emptiness problem is decidable. Using this class, we present further results improving the boundary between decidability and undecidability for PTAs and their subclasses such as L/U-PTAs. We then study liveness. We prove that: (1) the existence of at least one parameter valuation for which there exists an infinite run in an L/U-PTA is PSPACE-complete; (2) the existence of a parameter valuation such that the system has a deadlock is however undecidable; (3) the problem of the existence of a valuation for which a run remains in a given set of locations exhibits a very thin border between decidability and undecidability.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191