In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NP-hard and hard to approximate within a factor of $n^{1-\varepsilon}$ for any $\varepsilon > 0$. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In $H$-free graphs, that is, graphs not containing a fixed graph $H$ as an induced subgraph, the problem is known to remain NP-hard and APX-hard whenever $H$ contains a cycle, a vertex of degree at least four, or two vertices of degree at least three in one connected component. For the remaining cases, where every component of $H$ is a path or a subdivided claw, the complexity of Maximum Independent Set remains widely open, with only a handful of polynomial-time solvability results for small graphs $H$ such as $P_5$, $P_6$, the claw, or the fork. We show that for every graph $H$ for which Maximum Independent Set is not known to be APX-hard and SUBEXP-hard in $H$-free graphs, the problem admits a quasi-polynomial time approximation scheme and a subexponential-time exact algorithm in this graph class. Our algorithm works also in the more general weighted setting, where the input graph is supplied with a weight function on vertices and we are maximizing the total weight of an independent set.
A new variant of Newton's method - named Backtracking New Q-Newton's method (BNQN) - which has strong theoretical guarantee, is easy to implement, and has good experimental performance, was recently introduced by the third author. Experiments performed previously showed some remarkable properties of the basins of attractions for finding roots of polynomials and meromorphic functions, with BNQN. In general, they look more smooth than that of Newton's method. In this paper, we continue to experimentally explore in depth this remarkable phenomenon, and connect BNQN to Newton's flow and Voronoi's diagram. This link poses a couple of challenging puzzles to be explained. Experiments also indicate that BNQN is more robust against random perturbations than Newton's method and Random Relaxed Newton's method.
In this paper, we present a Computer Vision (CV) based tracking and fusion algorithm, dedicated to a 3D printed gimbal system on drones operating in nature. The whole gimbal system can stabilize the camera orientation robustly in a challenging nature scenario by using skyline and ground plane as references. Our main contributions are the following: a) a light-weight Resnet-18 backbone network model was trained from scratch, and deployed onto the Jetson Nano platform to segment the image into binary parts (ground and sky); b) our geometry assumption from nature cues delivers the potential for robust visual tracking by using the skyline and ground plane as a reference; c) a spherical surface-based adaptive particle sampling, can fuse orientation from multiple sensor sources flexibly. The whole algorithm pipeline is tested on our customized gimbal module including Jetson and other hardware components. The experiments were performed on top of a building in the real landscape.
Knowing who follows whom and what patterns they are following are crucial steps to understand collective behaviors (e.g. a group of human, a school of fish, or a stock market). Time series is one of resources that can be used to get insight regarding following relations. However, the concept of following patterns or motifs and the solution to find them in time series are not obvious. In this work, we formalize a concept of following motifs between two time series and present a framework to infer following patterns between two time series. The framework utilizes one of efficient and scalable methods to retrieve motifs from time series called the Matrix Profile Method. We compare our proposed framework with several baselines. The framework performs better than baselines in the simulation datasets. In the dataset of sound recording, the framework is able to retrieve the following motifs within a pair of time series that two singers sing following each other. In the cryptocurrency dataset, the framework is capable of capturing the following motifs within a pair of time series from two digital currencies, which implies that the values of one currency follow the values of another currency patterns. Our framework can be utilized in any field of time series to get insight regarding following patterns between time series.
In this paper we focus on three major task: 1) discussing our methods: Our method captures a portion of the data in DCD flowsheets, kidney perfusion data, and Flowsheet data captured peri-organ recovery surgery. 2) demonstrating the result: We built a comprehensive, analyzable database from 2022 OPTN data. This dataset is by far larger than any previously available even in this preliminary phase; and 3) proving that our methods can be extended to all the past OPTN data and future data. The scope of our study is all Organ Procurement and Transplantation Network (OPTN) data of the USA organ donors since 2008. The data was not analyzable in a large scale in the past because it was captured in PDF documents known as ``Attachments'', whereby every donor's information was recorded into dozens of PDF documents in heterogeneous formats. To make the data analyzable, one needs to convert the content inside these PDFs to an analyzable data format, such as a standard SQL database. In this paper we will focus on 2022 OPTN data, which consists of $\approx 400,000$ PDF documents spanning millions of pages. The entire OPTN data covers 15 years (2008--20022). This paper assumes that readers are familiar with the content of the OPTN data.
In this paper, we conduct rigorous error analysis of the Lie-Totter time-splitting Fourier spectral scheme for the nonlinear Schr\"odinger equation with a logarithmic nonlinear term $f(u)=u\ln|u|^2$ (LogSE) and periodic boundary conditions on a $d$-dimensional torus $\mathbb T^d$. Different from existing works based on regularisation of the nonlinear term $ f(u)\approx f^\varepsilon(u)=u\ln (|u| + \varepsilon )^2,$ we directly discretize the LogSE with the understanding $f(0)=0.$ Remarkably, in the time-splitting scheme, the solution flow map of the nonlinear part: $g(u)= u {\rm e}^{-{\rm} i t \ln|u|^{2}}$ has a higher regularity than $f(u)$ (which is not differentiable at $u=0$ but H\"older continuous), where $g(u)$ is Lipschitz continuous and possesses a certain fractional Sobolev regularity with index $0<s<1$. Accordingly, we can derive the $L^2$-error estimate: $O\big((\tau^{s/2} + N^{-s})\ln\! N\big)$ of the proposed scheme for the LogSE with low regularity solution $u\in C((0,T]; H^s( \mathbb{T}^d)\cap L^\infty( \mathbb{T}^d)).$ Moreover, we can show that the estimate holds for $s=1$ with more delicate analysis of the nonlinear term and the associated solution flow maps. Furthermore, we provide ample numerical results to demonstrate such a fractional-order convergence for initial data with low regularity. This work is the first one devoted to the analysis of splitting scheme for the LogSE without regularisation in the low regularity setting, as far as we can tell.
In this article, we employ discontinuous Galerkin (DG) methods for the finite element approximation of the frictionless unilateral contact problem using quadratic finite elements over simplicial triangulation. We first establish an optimal \textit{a priori} error estimates under the appropriate regularity assumption on the exact solution $\b{u}$. Further, we analyze \textit{a posteriori} error estimates in the DG norm wherein, the reliability and efficiency of the proposed \textit{a posteriori} error estimator is addressed. The suitable construction of discrete Lagrange multiplier $\b{\lambda_h}$ and some intermediate operators play a key role in developing \textit{a posteriori} error analysis. Numerical results presented on uniform and adaptive meshes illustrate and confirm the theoretical findings.
We discuss Cartan-Schouten metrics (Riemannian or pseudo-Riemannian metrics that are parallel with respect to the Cartan-Schouten canonical connection) on perfect Lie groups. Applications are foreseen in Information Geometry. Throughout this work, the tangent bundle TG and the cotangent bundle T*G of a Lie group G, are always endowed with their Lie group structures induced by the right trivialization. We show that TG and T*G are isomorphic if G possesses a biinvariant Riemannian or pseudo-Riemannian metric. We also show that, if on a perfect Lie group, there exists a Cartan-Schouten metric, then it must be biinvariant. We compute all such metrics on the cotangent bundles of simple Lie groups. We further show the following. Endowed with their canonical Lie group structures, the set of unit dual quaternions is isomorphic to TSU(2), the set of unit dual split quaternions is isomorphic to T*SL(2,R). The group SE(3) of special rigid displacements of the Euclidean 3-space is isomorphic to T*SO(3). The group SE(2,1) of special rigid displacements of the Minkowski 3-space is isomorphic to T*SO(2,1). Some results on SE(3) by N. Miolane and X. Pennec, and M. Zefran, V. Kumar and C. Croke, are generalized to SE(2,1) and to T*G, for any simple Lie group G.
The back-end module of Distributed Collaborative Simultaneous Localization and Mapping (DCSLAM) requires solving a nonlinear Pose Graph Optimization (PGO) under a distributed setting, also known as SE(d)-synchronization. Most existing distributed graph optimization algorithms employ a simple sequential partitioning scheme, which may result in unbalanced subgraph dimensions due to the different geographic locations of each robot, and hence imposes extra communication load. Moreover, the performance of current Riemannian optimization algorithms can be further accelerated. In this letter, we propose a novel distributed pose graph optimization algorithm combining multi-level partitioning with an accelerated Riemannian optimization method. Firstly, we employ the multi-level graph partitioning algorithm to preprocess the naive pose graph to formulate a balanced optimization problem. In addition, inspired by the accelerated coordinate descent method, we devise an Improved Riemannian Block Coordinate Descent (IRBCD) algorithm and the critical point obtained is globally optimal. Finally, we evaluate the effects of four common graph partitioning approaches on the correlation of the inter-subgraphs, and discover that the Highest scheme has the best partitioning performance. Also, we implement simulations to quantitatively demonstrate that our proposed algorithm outperforms the state-of-the-art distributed pose graph optimization protocols.
We study the power of randomness in the Number-on-Forehead (NOF) model in communication complexity. We construct an explicit 3-player function $f:[N]^3 \to \{0,1\}$, such that: (i) there exist a randomized NOF protocol computing it that sends a constant number of bits; but (ii) any deterministic or nondeterministic NOF protocol computing it requires sending about $(\log N)^{1/3}$ many bits. This exponentially improves upon the previously best-known such separation. At the core of our proof is an extension of a recent result of the first and third authors on sets of integers without 3-term arithmetic progressions into a non-arithmetic setting.
This article presents the affordances that Generative Artificial Intelligence can have in disinformation context, one of the major threats to our digitalized society. We present a research framework to generate customized agent-based social networks for disinformation simulations that would enable understanding and evaluation of the phenomena whilst discussing open challenges.