Search

In this paper, we study a discrete momentum consensus-based optimization (Momentum-CBO) algorithm which corresponds to a second-order generalization of the discrete first-order CBO [S.-Y. Ha, S. Jin and D. Kim, Convergence of a first-order consensus-based global optimization algorithm, Math. Models Methods Appl. Sci. 30 (2020) 2417–2444]. The proposed algorithm can be understood as the modification of ADAM-CBO, replacing the normalization term by unity. For the proposed Momentum-CBO, we provide a sufficient framework which guarantees the convergence of algorithm toward a global minimum of the objective function. Moreover, we present several experimental results showing that Momentum-CBO has an improved success rate of finding the global minimum compared to vanilla-CBO and show the stability of Momentum-CBO under different initialization schemes. We also show that Momentum-CBO can be used as the alternative of ADAM-CBO which does not have a proper convergence analysis. Finally, we give an application of Momentum-CBO for Lyapunov function approximation using symbolic regression techniques. [ABSTRACT FROM AUTHOR]

For an m -edge connected simple graph G , finding a spanning tree of G with the maximum number of leaves is MAXSNP-complete. The problem remains NP-complete even if G is planar and the maximal degree of G is at most four. Lu and Ravi gave the first known polynomial-time approximation algorithms with approximation factors 5 and 3. Later, they obtained a 3 -approximation algorithm that runs in near-linear time. The best known result is Solis-Oba, Bonsma, and Lowski's O (m) -time 2 -approximation algorithm. We show an alternative simple O (m) -time 2 -approximation algorithm whose analysis is simpler. This paper is dedicated to the cherished memory of our dear friend, Professor Takao Nishizeki. [ABSTRACT FROM AUTHOR]

In this paper, we present an approximation algorithm for the maximum independent set (MIS) problem over the class of B 1 -VPG graphs when the input is specified by a B 1 -VPG representation. We obtain a 6 (log n) 2 -approximation algorithm running in O (n (log n) 3) time. This is an improvement over the previously best n -approximation algorithm [J. Fox and J. Pach, Computing the independence number of intersection graphs, in Proc. Twenty-Second Annual ACM-SIAM Symp. Discrete Algorithms (SODA 2011), 2011, pp. 1161–1165, doi:10.1137/1.9781611973082.87] (for some fixed > 0) designed for some subclasses of string graphs, on B 1 -VPG graphs. [ABSTRACT FROM AUTHOR]

For a simple, undirected, connected graph G , a function h : V (G) → { 0 , 1 , 2 , 3 } which satisfies the following conditions is called a total Roman {3}-dominating function (TR3DF) of G with weight h (V) = ∑ p ∈ V h (p) : (C1) For every vertex u ∈ V if h (u) = 0 , then u has m (m ≥ 1) neighbors such that whose sum is at least 3, and if h (u) = 1 , then u has n (n ≥ 1) neighbors such that whose sum is at least 2. (C2) The subgraph induced by the set of vertices labeled one, two or three has no isolated vertices. For a graph G , the smallest possible weight of a TR3DF of G denoted γ t { R 3 } (G) is known as the total Roman { 3 } -domination number of G. The problem of determining γ t { R 3 } (G) of a graph G is called minimum total Roman {3}-domination problem (MTR3DP). In this paper, we show that the problem of deciding if G has a TR3DF of weight at most l for chordal graphs is NP-complete. We also show that MTR3DP is polynomial time solvable for bounded treewidth graphs, chain graphs and threshold graphs. We design a 3 (ln (Δ − 0. 5) + 1. 5) -approximation algorithm for the MTR3DP and show that the same cannot have (1 − δ) ln | V | ratio approximation algorithm for any δ > 0 unless NP ⊆ DTIME (| V | O (log log | V |)). Next, we show that MTR3DP is APX-complete for graphs with Δ = 4. We also show that the domination and total Roman {3}-domination problems are not equivalent in computational complexity aspects. Finally, we present an integer linear programming formulation for MTR3DP. [ABSTRACT FROM AUTHOR]

In this paper, we consider the discrete unit square cover (DUSC) problem as follows: given a set 𝒫 of n points and a set 𝒮 of m axis-aligned unit squares in ℝ 2 , the objective is (i) to check whether the union of the squares in 𝒮 covers all the points in 𝒫 , and (ii) if the answer is yes, then select a minimum cardinality subset 𝒮 ∗ ⊆ 𝒮 such that each point in 𝒫 is covered by at least one square in 𝒮 ∗ . For the DUSC problem: (i) we propose a (2 + 4 k − 2) -approximation algorithm, where k (> 2) is an integer parameter that defines a trade-off between the running time and the approximation factor of the algorithm. The running time of our proposed algorithm is O (k m k n + n log n). Our solution of the DUSC problem is based on a simple (1 + 2 k − 2) -approximation algorithm for the subproblem strip square cover (SSC) problem, where all the points in 𝒫 are lying within a horizontal strip of unit height. (ii) we also propose a 2-approximation algorithm, which runs in O (m 4 n) time. The 2-approximation algorithm is based on an algorithm for the subproblem SSC problem. The algorithm for the subproblem is developed using plane sweep and graph search traversal techniques. We also extend this algorithm to get 2-approximation result for the weighted DUSC problem where the squares are assigned weights, and the aim is to choose a subset 𝒮 ∗ ⊆ 𝒮 such that each point in 𝒫 is covered by at least one square in 𝒮 ∗ and the sum of the weights of squares in 𝒮 ∗ is minimized. [ABSTRACT FROM AUTHOR]

This paper studies the problem of orienting all edges of a weighted graph such that the maximum weighted outdegree of vertices is minimized. This problem, which has applications in the guard arrangement for example, can be shown to be $\mathcal{NP}$-hard generally. In this paper we first give optimal orientation algorithms which run in polynomial time for the following special cases: (i) the input is an unweighted graph, and (ii) the input graph is a tree. Then, by using those algorithms as sub-procedures, we provide a simple, combinatorial, $\min \{\frac{w_{max}}{w_{min}},(2 - \varepsilon)\}$-approximation algorithm for the general case, where wmax and wmin are the maximum and the minimum weights of edges, respectively, and ε is some small positive real number that depends on the input. [ABSTRACT FROM AUTHOR]

Phylogenetic networks are useful for visualizing evolutionary relationships between species with reticulate events such as hybridizations and horizontal gene transfers. In this paper, we consider the problem of constructing undirected phylogenetic networks that (1) are planar graphs and (2) admit embeddings in the plane where the vertices labeling all taxa are on the boundary of the network. We develop a new algorithm for constructing phylogenetic networks satisfying these constraints. First, we show that only approximate networks can be constructed for some distance matrices with at least five taxa. Then we prove that any five-point metric can be represented approximately by a planar boundary-labeled network with guaranteed fit value of 94.79. We extend the networks constructed in the proof to design an algorithm for computing planar boundary-labeled networks for any number of taxa. [ABSTRACT FROM AUTHOR]

The complexity status of the minimum r-star cover problem for orthogonal polygons had been open for many years, until 2004 when Ch. Worman and J. M. Keil proved it to be polynomially tractable (Polygon decomposition and the orthogonal art gallery problem, IJCGA 17(2) (2007), 105-138). However, since their algorithm has Õ(n17)-time complexity, where Õ(·) hides a polylogarithmic factor, and thus it is not practical, in this paper we present a linear-time 3-approximation algorithm. Our approach is based upon the novel partition of an orthogonal polygon into so-called o-star-shaped orthogonal polygons. [ABSTRACT FROM AUTHOR]

This paper proposes a numerical scheme to approximate the solution of (vectorial) limit load problems. The method makes use of a strictly convex perturbation of the problem, which corresponds to a projection of the deformation field under bounded deformation and incompressibility constraints. The discretized formulation of this perturbation converges to the solution of the original landslide problem when the amplitude of the perturbation tends to zero. The projection is computed numerically with a multi-step gradient descent on the dual formulation of the problem. [ABSTRACT FROM AUTHOR]

Given a set T of n points in ℝ2, a Manhattan network on T is a graph G = (V,E) with the property that all the edges in E are vertical or horizontal line segments connecting points in V ⊇ T and for all p, q ∈ T, the graph contains a path having the length exactly L1 distance between p and q. The Minimum Manhattan Network problem is to find a Manhattan network of minimum length, i.e. minimizing the total length of the line segments of the network. In this paper we present a 2-approximation algorithm with time complexity O(n log n), which improves over a recent combinatorial 2-approximation algorithm with running time O(n2). Moreover, compared with other 2-approximation algorithms using linear programming or dynamic programming techniques, we show that a greedy strategy suffices to obtain a 2-approximation algorithm. [ABSTRACT FROM AUTHOR]

Geometric spanner is a fundamental structure in computational geometry and plays an important role in many geometric networks design applications. In this paper, we consider a generalization of the classical geometric spanner problem (called segment spanner): Given a set S of n disjoint 2-D segments, find a spanning network GS with minimum size so that for any pair of points in S, there exists a path in GS with length no more than t times their Euclidean distance. Based on a number of interesting techniques (such as weakly dominating set, strongly dominating set, interval cover, and imaginary Steiner points), we present an efficient algorithm to construct the segment spanner. Our approach first identifies a set Q of Steiner points in S and then constructs a point spanner for the set of Steiner points. Our algorithm runs in O(|Q| + n2log n) time and Q is a constant approximation (in terms of its size) of the optimal solution when S has a constant relative separation ratio. The approximation ratio depends on the stretch factor t and the relative separation ratio of S. [ABSTRACT FROM AUTHOR]

We study the problem of scheduling n jobs with release dates on m identical parallel batch machines to minimize the total weighted completion time of the jobs. A batch machine with capacity B (B < n) is able to process a batch of up to B jobs simultaneously and the time needed is equal to the maximum processing time among the jobs in the batch. This model is motivated by applications in the manufacturing of integrated circuits. In this paper, we present a polynomial time approximation scheme (PTAS) for this problem. [ABSTRACT FROM AUTHOR]

Data clustering is a fundamental problem arising in many practical applications. In this paper, we present new geometric approximation and exact algorithms for the density-based data clustering problem in d-dimensional space ℝd (for any constant integer d ≥ 2). Previously known algorithms for this problem are efficient only when the specified range around each input point, called the δ-neighborhood, contains on average a constant number of input points. Different distributions of the input data points have significant impact on the efficiency of these algorithms. In the worst case when the data points are highly clustered, these algorithms run in quadratic time, although such situations might not occur very frequently on real data. By using computational geometry techniques, we develop faster approximation and exact algorithms for the density-based data clustering problem in ℝd. In particular, our approximation algorithm based on the ∊-fuzzy distance function takes O(n log n) time for any given fixed value ∊>0, and our exact algorithms take sub-quadratic time. The running times and output quality of our algorithms do not depend on any particular data distribution. We believe that our fast approximation algorithm is of considerable practical importance, while our sub-quadratic exact algorithms are more of theoretical interest. We implemented our approximation algorithm and the experimental results show that our approximation algorithm is efficient on arbitrary input point sets. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the 2D hexagonal lattice as a biologically meaningful alternative to the standard square lattice for the study of protein folding in the HP model. We show that the hexagonal lattice alleviates the "sharp turn" problem and models certain aspects of the protein secondary structure more realistically. We present a ⅙-approximation and a clustering heuristic for protein folding on the hexagonal lattice. In addition to these two algorithms, we also implement a Monte Carlo Metropolis algorithm and a branch-and-bound partial enumeration algorithm, and conduct experiments to compare their effectiveness. [ABSTRACT FROM AUTHOR]

The subtree transfer (STT) distance is one of the distance metric for comparing phylogenies. Previous work on computing the STT distance considered degree-3 trees only. In this paper, we give an approximation algorithm for the STT distance for degree-d trees with arbitrary d and with generalized STT operations. Also, some NP-hardness results related to STT distance are presented. [ABSTRACT FROM AUTHOR]

In this paper, we study a 3D geometric problem originated from computing neural maps in the computational biology community: Given a set S of n points in 3D, compute k cylindrical segments (with different radii, orientations, lengths and no segment penetrates another) enclosing S such that the sum of their radii is minimized. There is no known result in this direction except when k=1. The general problem is strongly NP-hard and we obtain a polynomial time approximation scheme (PTAS) for any fixed k>1 in O(n3k-2/δ4k-3) time by returning k cylindrical segments with sum of radii at most (1+δ) of the corresponding optimal value, if exist. Our PTAS is built upon a simple (though slower) approximation algorithm for the case when k=1. [ABSTRACT FROM AUTHOR]

Data clustering is an important theoretical topic and a sharp tool for various applications. It is a task frequently arising in geometric computing. The main objective of data clustering is to partition a given data set into clusters such that the data items within the same cluster are "more" similar to each other with respect to certain measures. In this paper, we study the pairwise data clustering problem with pairwise similarity/dissimilarity measures that need not satisfy the triangle inequality. By using a criterion, called the minimum normalized cut, we model the general pairwise data clustering problem as a graph partition problem. The graph partition problem based on minimizing the normalized cut is known to be NP-hard. For an undirected weighted graph of n vertices, we present a ((4+o(1))Inn)-approximation polynomial time algorithm for the minimum normalized cut problem; this is the first provably good approximation polynomial time algorithm for the problem. We also give a more efficient algorithm for this problem by sacrificing the approximation ratio slightly. Further, our scheme achieves a ((2+o(1))Inn)-approximation polynomial time algorithm for computing the sparsest cuts in edge-weighted and vertex-weighted undirected graphs, improving the previously best known approximation ratio by a constant factor. Some applications and implementation work of our approximation normalized cut algorithms are also discussed. [ABSTRACT FROM AUTHOR]