We consider the following problem that we call the Shortest Two Disjoint Paths problem: given an undirected graph $G=(V,E)$ with edge weights $w:E\rightarrow \mathbb{R}$, two terminals $s$ and $t$ in $G$, find two internally vertex-disjoint paths between $s$ and $t$ with minimum total weight. As shown recently by Schlotter and Seb\H{o} (2023), this problem becomes NP-hard if edges can have negative weights, even if the weight function is conservative, i.e., there are are no cycles in $G$ with negative weight. We propose a polynomial-time algorithm that solves the Shortest Two Disjoint Paths problem for conservative weights in the case when the negative-weight edges form a single tree in $G$.
相關內容
We prove that the scaled maximum steady-state waiting time and the scaled maximum steady-state queue length among $N$ $GI/GI/1$-queues in the $N$-server fork-join queue, converge to a normally distributed random variable as $N\to\infty$. The maximum steady-state waiting time in this queueing system scales around $\frac{1}{\gamma}\log N$, where $\gamma$ is determined by the cumulant generating function $\Lambda$ of the service distribution and solves the Cram\'er-Lundberg equation with stochastic service times and deterministic inter-arrival times. This value $\frac{1}{\gamma}\log N$ is reached at a certain hitting time. The number of arrivals until that hitting time satisfies the central limit theorem, with standard deviation $\frac{\sigma_A}{\sqrt{\Lambda'(\gamma)\gamma}}$. By using distributional Little's law, we can extend this result to the maximum queue length. Finally, we extend these results to a fork-join queue with different classes of servers.
In this paper, we study the problem of maximizing $k$-submodular functions subject to a knapsack constraint. For monotone objective functions, we present a $\frac{1}{2}(1-e^{-2})\approx 0.432$ greedy approximation algorithm. For the non-monotone case, we are the first to consider the knapsack problem and provide a greedy-type combinatorial algorithm with approximation ratio $\frac{1}{3}(1-e^{-3})\approx 0.317$.
The Johnson--Lindenstrauss (JL) lemma is a powerful tool for dimensionality reduction in modern algorithm design. The lemma states that any set of high-dimensional points in a Euclidean space can be flattened to lower dimensions while approximately preserving pairwise Euclidean distances. Random matrices satisfying this lemma are called JL transforms (JLTs). Inspired by existing $s$-hashing JLTs with exactly $s$ nonzero elements on each column, the present work introduces an ensemble of sparse matrices encompassing so-called $s$-hashing-like matrices whose expected number of nonzero elements on each column is~$s$. The independence of the sub-Gaussian entries of these matrices and the knowledge of their exact distribution play an important role in their analyses. Using properties of independent sub-Gaussian random variables, these matrices are demonstrated to be JLTs, and their smallest and largest singular values are estimated non-asymptotically using a technique from geometric functional analysis. As the dimensions of the matrix grow to infinity, these singular values are proved to converge almost surely to fixed quantities (by using the universal Bai--Yin law), and in distribution to the Gaussian orthogonal ensemble (GOE) Tracy--Widom law after proper rescalings. Understanding the behaviors of extreme singular values is important in general because they are often used to define a measure of stability of matrix algorithms. For example, JLTs were recently used in derivative-free optimization algorithmic frameworks to select random subspaces in which are constructed random models or poll directions to achieve scalability, whence estimating their smallest singular value in particular helps determine the dimension of these subspaces.
The sequential composition of propositional logic programs has been recently introduced. This paper studies the sequential {\em decomposition} of programs by studying Green's relations $\mathcal{L,R,J}$ -- well-known in semigroup theory -- between programs. In a broader sense, this paper is a further step towards an algebraic theory of logic programming.
In the Activation Edge-Multicover problem we are given a multigraph $G=(V,E)$ with activation costs $\{c_{e}^u,c_{e}^v\}$ for every edge $e=uv \in E$, and degree requirements $r=\{r_v:v \in V\}$. The goal is to find an edge subset $J \subseteq E$ of minimum activation cost $\sum_{v \in V}\max\{c_{uv}^v:uv \in J\}$,such that every $v \in V$ has at least $r_v$ neighbors in the graph $(V,J)$. Let $k= \max_{v \in V} r_v$ be the maximum requirement and let $\theta=\max_{e=uv \in E} \frac{\max\{c_e^u,c_e^v\}}{\min\{c_e^u,c_e^v\}}$ be the maximum quotient between the two costs of an edge. For $\theta=1$ the problem admits approximation ratio $O(\log k)$. For $k=1$ it generalizes the Set Cover problem (when $\theta=\infty$), and admits a tight approximation ratio $O(\log n)$. This implies approximation ratio $O(k \log n)$ for general $k$ and $\theta$, and no better approximation ratio was known. We obtain the first logarithmic approximation ratio $O(\log k +\log\min\{\theta,n\})$, that bridges between the two known ratios -- $O(\log k)$ for $\theta=1$ and $O(\log n)$ for $k=1$. This implies approximation ratio $O\left(\log k +\log\min\{\theta,n\}\right) +\beta \cdot (\theta+1)$ for the Activation $k$-Connected Subgraph problem, where $\beta$ is the best known approximation ratio for the ordinary min-cost version of the problem.
Next Point-of-Interest (POI) recommendation is a critical task in location-based services that aim to provide personalized suggestions for the user's next destination. Previous works on POI recommendation have laid focused on modeling the user's spatial preference. However, existing works that leverage spatial information are only based on the aggregation of users' previous visited positions, which discourages the model from recommending POIs in novel areas. This trait of position-based methods will harm the model's performance in many situations. Additionally, incorporating sequential information into the user's spatial preference remains a challenge. In this paper, we propose Diff-POI: a Diffusion-based model that samples the user's spatial preference for the next POI recommendation. Inspired by the wide application of diffusion algorithm in sampling from distributions, Diff-POI encodes the user's visiting sequence and spatial character with two tailor-designed graph encoding modules, followed by a diffusion-based sampling strategy to explore the user's spatial visiting trends. We leverage the diffusion process and its reversed form to sample from the posterior distribution and optimized the corresponding score function. We design a joint training and inference framework to optimize and evaluate the proposed Diff-POI. Extensive experiments on four real-world POI recommendation datasets demonstrate the superiority of our Diff-POI over state-of-the-art baseline methods. Further ablation and parameter studies on Diff-POI reveal the functionality and effectiveness of the proposed diffusion-based sampling strategy for addressing the limitations of existing methods.
We define a family of $C^1$ functions which we call "nowhere coexpanding functions" that is closed under composition and includes all $C^3$ functions with non-positive Schwarzian derivative. We establish results on the number and nature of the fixed points of these functions, including a generalisation of a classic result of Singer.
Untargeted metabolomic profiling through liquid chromatography-mass spectrometry (LC-MS) measures a vast array of metabolites within biospecimens, advancing drug development, disease diagnosis, and risk prediction. However, the low throughput of LC-MS poses a major challenge for biomarker discovery, annotation, and experimental comparison, necessitating the merging of multiple datasets. Current data pooling methods encounter practical limitations due to their vulnerability to data variations and hyperparameter dependence. Here we introduce GromovMatcher, a flexible and user-friendly algorithm that automatically combines LC-MS datasets using optimal transport. By capitalizing on feature intensity correlation structures, GromovMatcher delivers superior alignment accuracy and robustness compared to existing approaches. This algorithm scales to thousands of features requiring minimal hyperparameter tuning. Applying our method to experimental patient studies of liver and pancreatic cancer, we discover shared metabolic features related to patient alcohol intake, demonstrating how GromovMatcher facilitates the search for biomarkers associated with lifestyle risk factors linked to several cancer types.
We introduce a novel methodology that leverages the strength of Physics-Informed Neural Networks (PINNs) to address the counterdiabatic (CD) protocol in the optimization of quantum circuits comprised of systems with $N_{Q}$ qubits. The primary objective is to utilize physics-inspired deep learning techniques to accurately solve the time evolution of the different physical observables within the quantum system. To accomplish this objective, we embed the necessary physical information into an underlying neural network to effectively tackle the problem. In particular, we impose the hermiticity condition on all physical observables and make use of the principle of least action, guaranteeing the acquisition of the most appropriate counterdiabatic terms based on the underlying physics. The proposed approach offers a dependable alternative to address the CD driving problem, free from the constraints typically encountered in previous methodologies relying on classical numerical approximations. Our method provides a general framework to obtain optimal results from the physical observables relevant to the problem, including the external parameterization in time known as scheduling function, the gauge potential or operator involving the non-adiabatic terms, as well as the temporal evolution of the energy levels of the system, among others. The main applications of this methodology have been the $\mathrm{H_{2}}$ and $\mathrm{LiH}$ molecules, represented by a 2-qubit and 4-qubit systems employing the STO-3G basis. The presented results demonstrate the successful derivation of a desirable decomposition for the non-adiabatic terms, achieved through a linear combination utilizing Pauli operators. This attribute confers significant advantages to its practical implementation within quantum computing algorithms.
An adjacency-crossing graph is a graph that can be drawn such that every two edges that cross the same edge share a common endpoint. We show that the number of edges in an $n$-vertex adjacency-crossing graph is at most $5n-10$. If we require the edges to be drawn as straight-line segments, then this upper bound becomes $5n-11$. Both of these bounds are tight. The former result also follows from a very recent and independent work of Cheong et al.\cite{cheong2023weakly} who showed that the maximum size of weakly and strongly fan-planar graphs coincide. By combining this result with the bound of Kaufmann and Ueckerdt\cite{KU22} on the size of strongly fan-planar graphs and results of Brandenburg\cite{Br20} by which the maximum size of adjacency-crossing graphs equals the maximum size of fan-crossing graphs which in turn equals the maximum size of weakly fan-planar graphs, one obtains the same bound on the size of adjacency-crossing graphs. However, the proof presented here is different, simpler and direct.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191