Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Gene trees inferred from molecular sequence alignments are typically unrooted, and determining the most credible rooting edge is a classical problem in computational biology. One approach to solve this problem is unrooted reconciliation, where the rooting edge is postulated based on the split of the root from a given species tree. In this paper, we propose a novel variant of the gene tree rooting problem, where the gene tree root is inferred using a phylogenetic network of the species present in the gene tree. To obtain the best rooting, unrooted reconciliation can be applied, where the unrooted gene tree is jointly reconciled with a set of splits inferred from the network. However, the exponential size of the set induced by display trees of the network makes this approach computationally prohibitive. To address this, we propose a broader and easier-to-control set of splits based on the structural properties of the network. We then derive exact mathematical formulas for the rooting problem and propose two general rooting algorithms to handle cases where the input network does not meet the initial requirements. Our experimental study based on simulated gene trees and networks demonstrates that our algorithms infer gene tree rootings correctly or with a small error in most cases. PubDate: 2024-06-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Lattice is the main research subject in the geometry of numbers. SVP refers to finding a shortest nonzero lattice vector in a given lattice, which is thought to be a difficult optimization problem. For general lattice, the integer coefficients of a shortest nonzero vector under a lattice basis might be exponentially large, thus making the simple integer coefficient searching approach impractical. In this paper, we find that for low-dimensional circulant lattices(dimension \(n \in \{2,3,4,6\}\) ), the integer coefficients of a shortest lattice vector under its circulant basis are actually in a small set \(S=\{-1,0,1\}\) , which makes it easy to find the shortest vector in these cases. Moreover, we present the specific forms of the SVP solutions for low-dimensional circulant lattices. PubDate: 2024-06-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Diabetes is regarded as one of the deadliest chronic illnesses that increases blood sugar. But there is no reliable method for predicting diabetic severity that shows how the disease will affect various body organs in the future. Therefore, this paper introduced Optimized Dual Directional Temporal convolution and Attention based Density Clustering (ODDTADC) method for predicting and classifying risk level in diabetic patients. In the diabetic prediction stage, the prediction is done by using an Integrated Dual Directional Temporal Convolution and an Enriched Remora Optimization Algorithm. Here, dual directional temporal convolution is used to extract temporal features by integrating dilated convolution and casual convolution in the feature extraction layer. Then, the attention module is used instead of max-pooling to emphasize the various features' importance in the feature aggregation layer. The Enriched Remora Optimization Algorithm is used to find optimal hyper parameters for Integrated Dual Directional Temporal Convolution. In the classification of stages based on risk level, the values from stage-I are fed into the Attention based Density Spatial Clustering of Applications with Noise, which allocate various weights based on their density values in the Core Points. Based on the results, the Nested Long Short-Term Memory is utilized to classify the risk levels of diabetic patients over a period of two or three years. Experimental evaluations were performed on five datasets, including PIMA Indian Diabetics Database, UCI Machine Learning Repository Diabetics Dataset, Heart Diseases Dataset, Chronic Disease Dataset and Diabetic Retinopathy Debrecen Dataset. The proposed ODDTADC method demonstrates superior performance compared to existing methods, achieving remarkable results in accuracy (98.21%), recall (94.46%), kappa coefficient (98.95%), precision (98.74%), F1-score (99.01%) and Matthew’s correlation coefficient (MCC) (0.87%). PubDate: 2024-05-21

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract The diameter of an undirected or a directed graph is defined to be the maximum shortest path distance over all pairs of vertices in the graph. Given an undirected graph G, we examine the problem of assigning directions to each edge of G such that the diameter of the resulting oriented graph is minimized. The minimum diameter over all strongly connected orientations is called the oriented diameter of G. The problem of determining the oriented diameter of a graph is known to be NP-hard, but the time-complexity question is open for planar graphs. In this paper we compute the exact value of the oriented diameter for triangular grid graphs. We then prove an n/3 lower bound and an \(n/2+O\left( \sqrt{n}\right) \) upper bound on the oriented diameter of planar triangulations, where n is the number of vertices in G. It is known that given a planar graph G with bounded treewidth and a fixed positive integer k, one can determine in linear time whether the oriented diameter of G is at most k. We consider a weighted version of the oriented diameter problem and show it to be weakly NP-complete for planar graphs with bounded pathwidth. PubDate: 2024-05-20

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract The frustum model simulates network evolution by extending cliques, which represent highly interacting groups in social networks. In each time-step, new vertices are added adjacent to existing cliques of prescribed order. The model exhibits several features of social networks, such as densification, short distances, bad spectral expansion, and high local clustering. PubDate: 2024-05-20

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract The problem studied in this paper is elective surgery scheduling, with resource constraints in each of the three following stages: preoperative, perioperative, and postoperative stages. With the integrated availability of hospital beds in wards and operating rooms, the aim is to determine operation start times of surgeries and allocate the hospital beds to patients while getting patients treated as soon as possible. This task is crucial in providing timely treatments for the patients while ensuring the hospital’s resource utilization balance. For the problem, we first formulate it as mixed-integer programming, which is NP-complete. Then, we propose several heuristics to overcome the long computation time. To make the solution better, we also propose improved algorithms. Finally, we conduct a series of numerical studies to illustrate the efficiency of our proposed algorithms and examine the impact of the number of jobs, beds, and surgery blocks on the performance measure. Computational experiments showed the superior performance of our heuristics in makespan. PubDate: 2024-05-18

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract The online optimization model was first introduced in the research of machine learning problems (Zinkevich, Proceedings of ICML, 928–936, 2003). It is a powerful framework that combines the principles of optimization with the challenges of online decision-making. The present research mainly consider the case that the reveal objective functions are convex or submodular. In this paper, we focus on the online maximization problem under a special objective function \(\varPhi (x):[0,1]^n\rightarrow \mathbb {R}_{+}\) which satisfies the inequality \(\frac{1}{2}\langle u^{T}\nabla ^{2}\varPhi (x),u\rangle \le \sigma \cdot \frac{\Vert u\Vert _{1}}{\Vert x\Vert _{1}}\langle u,\nabla \varPhi (x)\rangle \) for any \(x,u\in [0,1]^n, x\ne 0\) . This objective function is named as one sided \(\sigma \) -smooth (OSS) function. We achieve two conclusions here. Firstly, under the assumption that the gradient function of OSS function is L-smooth, we propose an \((1-\exp ((\theta -1)(\theta /(1+\theta ))^{2\sigma }))\) - approximation algorithm with \(O(\sqrt{T})\) regret upper bound, where T is the number of rounds in the online algorithm and \(\theta , \sigma \in \mathbb {R}_{+}\) are parameters. Secondly, if the gradient function of OSS function has no L-smoothness, we provide an \(\left( 1+((\theta +1)/\theta )^{4\sigma }\right) ^{-1}\) -approximation projected gradient algorithm, and prove that the regret upper bound of the algorithm is \(O(\sqrt{T})\) . We think that this research can provide different ideas for online non-convex and non-submodular learning. PubDate: 2024-05-18

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract A 3-star is a complete bipartite graph \(K_{1,3}\) . A 3-star packing of a graph G is a collection of vertex-disjoint subgraphs of G in which each subgraph is a 3-star. The maximum 3-star packing problem is to find a 3-star packing of a given graph with the maximum number of 3-stars. A 2-independent set of a graph G is a subset S of V(G) such that for each pair of vertices \(u,v\in S\) , paths between u and v are all of length at least 3. In cubic graphs, the maximum 3-star packing problem is equivalent to the maximum 2-independent set problem. The maximum 2-independent set problem was proved to be NP-hard on cubic graphs (Kong and Zhao in Congressus Numerantium 143:65–80, 2000), and the best approximation algorithm of maximum 2-independent set problem for cubic graphs has approximation ratio \(\frac{8}{15}\) (Miyano et al. in WALCOM 2017, Proceedings, pp 228–240). In this paper, we first prove that the maximum 3-star packing problem is NP-hard in claw-free cubic graphs and then design a linear-time algorithm which can find a 3-star packing of a connected claw-free cubic graph G covering at least \(\frac{3v(G)-8}{4}\) vertices, where v(G) denotes the number of vertices of G. PubDate: 2024-05-18

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In this work, we introduce a game-theoretic model that assesses the cyber-security risk of cloud networks and informs security experts on the optimal security strategies. Our approach combines game theory, combinatorial optimization, and cyber-security and aims to minimize the unexpected network disruptions caused by malicious cyber-attacks under uncertainty. Methodologically, we introduce the the critical node game, a simultaneous and non-cooperative attacker-defender game where each player solves a combinatorial optimization problem parametrized in the variables of the other player. Each player simultaneously commits to a defensive (or attacking) strategy with limited knowledge about the choices of their adversary. We provide a realistic model for the critical node game and propose an algorithm to compute its stable solutions, i.e., its Nash equilibria. Practically, our approach enables security experts to assess the security posture of the cloud network and dynamically adapt the level of cyber-protection deployed on the network. We provide a detailed analysis of a real-world cloud network and demonstrate the efficacy of our approach through extensive computational tests. PubDate: 2024-05-18

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract This work deals with the classical Job Shop Scheduling Problem (JSSP) of minimizing the makespan. Metaheuristics are often used on the JSSP solution, but a performance comparable to the state-of-the-art depends on an efficient exploration of the solutions space characteristics. Thus, it is proposed an intensification approach based on the concepts of attraction basins and big valley. Suboptimal solutions obtained by the metaheuristic genetic algorithm are selected and subjected to intensification, in which a binary Bidimensional Genetic Algorithm (BGA) is utilized to enlarge the search neighborhood from a current solution, to escape of attraction basins. Then, the best solution found in this neighborhood is used as the final point of the path relinking strategy derived from the initial suboptimal solution, for exploring possible big valleys. Finally, the best solution in the path is inserted into the population. Trials with usual instances of the literature show that the proposed approach yields greater results with regards to local search, based on permutation of operations on critical blocks, either on the makespan reduction or on the number of generations, and competitive results regarding the contemporary literature. PubDate: 2024-05-18

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract The minimum connected dominating set problem is widely studied due to its applicability to mobile ad-hoc networks and sensor grids. Its variant the minimum 2-connected dominating set (M-2CDS) problem has become increasingly important because its critical role in designing fault-tolerant network. This paper presents a connected dominating degree-based local search (CDD-LS) tailored for solving the M-2CDS. The proposed algorithm implements an improved swap-based neighborhood structure as well as the corresponding fast neighborhood evaluation method using connected dominating degree data structure. The diversification techniques including tabu strategy and perturbaistion help the search jump out of the local optima improving the efficiency. This study investigates the performance of the CDD-LS algorithm on 38 publicly available benchmark datasets. The results demonstrate that the CDD-LS algorithm significantly improves the best runtime in 19 instances, while providing the equivalent performance in 8 instances. Furthermore, the CDD-LS is tested on 18 newly generated instances to check its capability on large-scale scenarios. To gain a deeper understanding of the algorithm’s effectiveness, an investigation into the key components of the CDD-LS algorithm is conducted. PubDate: 2024-05-14

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract An autonomous robot with a limited vision range finds a path to the goal in an unknown environment in 2D avoiding polygonal obstacles. In the process of discovering the environmental map, the robot has to return to some positions marked previously, the regions where the robot traverses to reach that position are defined as sequences of bundles of line segments. This paper presents a novel algorithm for finding approximately shortest paths along the sequences of bundles of line segments based on the method of multiple shooting. Three factors of the approach including bundle partition, collinear condition, and update of shooting points are presented. We then show that if the collinear condition holds, the exact shortest path of the problem is determined, otherwise, the sequence lengths of paths obtained by the update of the method converges. The algorithm is implemented in Python and some numerical examples show that the running time of path-planing for autonomous robots using our method is faster than that using the rubber band technique of Li and Klette in Euclidean Shortest Paths, Springer, 53–89 (2011). PubDate: 2024-05-11

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We consider the vertex proper coloring problem for highly restricted instances of geometric intersection graphs of line segments embedded in the plane. Provided a graph in the class UNIT-PURE-k-DIR, corresponding to intersection graphs of unit length segments lying in at most k directions with all parallel segments disjoint, and provided explicit coordinates for segments whose intersections induce the graph, we show for \(k = 4\) that it is NP-complete to decide if a proper 3-coloring exists, and moreover, \(\#P\) -complete under many-one counting reductions to determine the number of such colorings. In addition, under the more relaxed constraint that segments have at most two distinct lengths, we show these same hardness results hold for finding and counting proper \(\left( k-1\right) \) -colorings for every \(k \ge 5\) . More generally, we establish that the problem of proper 3-coloring an arbitrary graph with m edges can be reduced in \({\mathcal {O}}\left( m^2\right) \) time to the problem of proper 3-coloring a UNIT-PURE-4-DIR graph. This can then be shown to imply that no \(2^{o\left( \sqrt{n}\right) }\) time algorithm can exist for proper 3-coloring PURE-4-DIR graphs under the Exponential Time Hypothesis (ETH), and by a slightly more elaborate construction, that no \(2^{o\left( \sqrt{n}\right) }\) time algorithm can exist for counting the such colorings under the Counting Exponential Time Hypothesis (#ETH). Finally, we prove an NP-hardness result for the optimization problem of finding a maximum order proper 3-colorable induced subgraph of a UNIT-PURE-4-DIR graph. PubDate: 2024-05-05

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Given a connected graph G, two vertices \(u,v\in V(G)\) doubly resolve \(x,y\in V(G)\) if \(d_{G}(x,u)-d_{G}(y,u)\ne d_{G}(x,v)-d_{G}(y,v)\) . The doubly metric dimension \(\psi (G)\) of G is the cardinality of a minimum set of vertices that doubly resolves each pair of vertices from V(G). It is well known that deciding the doubly metric dimension of G is NP-hard. In this work we determine the exact values of doubly metric dimensions of unicyclic graphs which completes the known result. Furthermore, we give formulae for doubly metric dimensions of cactus graphs and block graphs. PubDate: 2024-05-05

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In this paper, we propose a physical protocol to verify the first nonzero term of a sequence using a deck of cards. The protocol lets a prover show the value of the first nonzero term of a given sequence to a verifier without revealing which term it is. Our protocol uses \(\varTheta (1)\) shuffles, which is asymptotically lower than that of an existing protocol of Fukusawa and Manabe which uses \(\varTheta (n)\) shuffles, where n is the length of the sequence. We also apply our protocol to construct zero-knowledge proof protocols for three well-known logic puzzles: ABC End View, Goishi Hiroi, and Toichika. These protocols enable a prover to physically show that he/she know solutions of the puzzles without revealing them. PubDate: 2024-05-05

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract A vertex coloring of a graph G is called a 2-distance coloring if any two vertices at distance at most 2 from each other receive different colors. Suppose that G is a planar graph with girth 5 and maximum degree \(\Delta \) . We prove that G admits a 2-distance \(\Delta +7\) coloring, which improves the result of Dong and Lin (J Comb Optim 32(2):645–655, 2016). Moreover, we prove that G admits a 2-distance \(\Delta +6\) coloring when \(\Delta \ge 10\) . PubDate: 2024-05-05

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We study deterministic mechanism design for constrained heterogeneous two-facility location games. The constraint here means that the feasible locations of facilities are specified and the number of facilities that can be built at each feasible location is limited. Given that a set of agents can strategically report their locations on the real line, the authority wants to design strategyproof mechanisms (i.e., mechanisms that can incentivize agents to report truthful private information) to construct two heterogeneous facilities under constraint, while optimizing the corresponding social objectives. Assuming that each agent’s individual objective depends on the sum of her distance to facilities, we consider locating desirable and obnoxious facilities respectively. For the former, we give a deterministic group strategyproof mechanism, which guarantees 3-approximation under the objectives of minimizing the sum cost and the maximum cost. We show that no deterministic strategyproof mechanism can have an approximation ratio of less than 2 under the sum/maximum cost objective. For the latter, we give a deterministic group strategyproof mechanism with 2-approximation under the objectives of maximizing the sum utility and the minimum utility. We show that no deterministic strategyproof mechanism can have an approximation ratio of less than 3/2 under the sum utility objective and 2 under the minimum utility objective, respectively. PubDate: 2024-04-27

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In recent years climate prediction has obtained more attention to mitigate the impact of natural disasters caused by climatic variability. Efficient and effective climate prediction helps palliate negative consequences and allows favourable conditions for managing the resources optimally through proper planning. Due to the environmental, geopolitical and economic consequences, forecasting of atmospheric and oceanic parameters still results in a challenging task. An efficient prediction technique named Sea Lion Autoregressive Deer Hunting Optimization-based Deep Recurrent Neural Network (SLArDHO-based Deep RNN) is developed in this research to predict the oceanic and atmospheric parameters. The extraction of technical indicators makes the devised method create optimal and accurate prediction outcomes by employing the deep learning framework. The classifier uses more training samples and this can be generated by augmenting the data samples using the oversampling method. The atmospheric and the oceanic parameters are considered for the prediction strategy using the Deep RNN classifier. Here, the weights of the Deep RNN classifier are optimally tuned by the SLArDHO algorithm to find the best value based on the fitness function. The devised method obtains minimum mean squared error (MSE), root mean square error (RMSE), mean absolute error (MAE) of 0.020, 0.142, and 0.029 for the All India Rainfall Index (AIRI) dataset. PubDate: 2024-04-27

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract An edge coloring of a graph G is to color all its edges such that adjacent edges receive different colors. It is acyclic if the subgraph induced by any two colors does not contain a cycle. Fiamcik (Math Slovaca 28:139-145, 1978) and Alon et al. (J Graph Theory 37:157-167, 2001) conjectured that every simple graph with maximum degree \(\Delta \) is acyclically edge \((\Delta + 2)\) -colorable — the well-known acyclic edge coloring conjecture. Despite many major breakthroughs and minor improvements, the conjecture remains open even for planar graphs. In this paper, we prove that planar graphs are acyclically edge \((\Delta + 5)\) -colorable. Our proof has two main steps: Using discharging methods, we first show that every non-trivial planar graph contains a local structure in one of the eight characterized groups; we then deal with each local structure to color the edges in the graph acyclically using no more than \(\Delta + 5\) colors by an induction on the number of edges. PubDate: 2024-04-27