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]

Emerging applications such as optimal budget allocation and sensor placement impose problems of maximizing variants of submodular functions with constraints under a streaming setting. In this paper, we first devise a streaming algorithm based on Sieve-Streaming for maximizing a monotone diminishing return submodular (DR-submodular) function with a cardinality constraint on the integer lattice and show it is a one-pass algorithm with approximation ratio 1 2 − . The key idea to ensure one pass for the algorithm is to combine binary search for determining the level of an element with the exponential-growth method for estimating the OPT. Inspired by Sieve-Streaming++, we then improve the memory of the algorithm to O (k ) and the query complexity to O (k log 2 k ). [ABSTRACT FROM AUTHOR]

k -submodular maximization is a generalization of submodular maximization, which requires us to select k disjoint subsets instead of one subset. Attracted by practical values and applications, we consider k -submodular maximization with two kinds of constraints. For total size and individual size difference constraints, we present a 1 − e − 1 k − 𝜖 -approximation algorithm for maximizing a nonnegative k-submodular function, running in time O (n (k − 1) ! 𝜖 log n 𝜖 + k (k − 1)) at worst. Specially, if B is multiple of k , the approximation ratio can reduce to 1 − e − 1 k − 1 − 𝜖 , running in time O n (k − 1) ! 𝜖 log n 𝜖 at worst. Besides, this algorithm can be applied to α -bisubmodular achieving 1 − 1 e − 𝜖 -approximation running in time O n 𝜖 log n 𝜖 + 2 . Furthermore, if B is multiple of 2, the approximation ratio can reduce to (1 − 1 / e − 𝜖) , running in time O n 𝜖 log n 𝜖 at worst. For individual size constraint, there is a (1 − 1 / e − 𝜖) -approximation algorithm for maximizing a nonnegative k -submodular function and an nonnegative α -bisubmodular function, running in time O n k ! 𝜖 log n 𝜖 and O 2 n 𝜖 log n 𝜖 , respectively, at worst. [ABSTRACT FROM AUTHOR]

We present new results on two types of guarding problems for polygons. For the first problem, we present an optimal linear time algorithm for computing a smallest set of points that guard a given shortest path in a simple polygon having n edges. We also prove that in polygons with holes, there is a constant c > 0 such that no polynomial-time algorithm can solve the problem within an approximation factor of c log n , unless P=NP. For the second problem, we present a (k + h) -FPT algorithm for computing a shortest tour that sees k specified points in a polygon with h holes. We also present a k -FPT approximation algorithm for this problem having approximation factor 2 . In addition, we prove that the general problem cannot be polynomially approximated better than by a factor of c log n , for some constant c > 0 , unless P  = NP. [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]

Applying principal component analysis (PCA) to find synergy signal for specific motion of Robot is a standard method. However, implementation of PCA gives synergy solely on quantitative basis. The algorithms proposed in this paper advocates the enhancement of qualitative measure of PCA to locate well-coordinated synergy signals. The two main control strategies of central nervous system (CNS) are taken into account for enhancement of algorithms. First one is the CNS strategy of separate synergy generation for individual limbs and second is the trajectory generation of complex movement using via-points. The proposed algorithms find the synergy without loss of generality of implementation. Humanoid robot NAO is used as a robotic platform to test the result of the algorithm. The synergy for a group of motors is calculated by implementing the algorithm on motors position sensor data of the robot corresponding to three motion pattern 1. Knee bend sitting-standing, 2. Sitting-standing on chair, and 3. Walking. The improvement in result is statistically measured by calculating error between original and reconstructed signal for proposed algorithms and applying Z-test tested on error signals. Another statistical measure of improvement is treated by calculating 'Goodness of Fit' for original and reconstructed signal. [ABSTRACT FROM AUTHOR]

Motivated by a crane assignment problem, we consider a Euclidean bipartite matching problem with edge-crossing constraints. Specifically, given red points and blue points in the plane, we want to construct a perfect matching between red and blue points that minimizes the length of the longest edge, while imposing a constraint that no two edges may cross each other. We show that the problem cannot be approximately solved within a factor less than 1:277 in polynomial time unless . We give simple dynamic programming algorithms that solve our problem in two special cases, namely (1) the case where the red and blue points form the vertices of a convex polygon and (2) the case where the red points are collinear and the blue points lie to one side of the line through the red points. [ABSTRACT FROM AUTHOR]

We consider the problem of computing a minimum-weight Hamiltonian cycle on an undi-rected graph with edges' weights from set {0,1, 2}, where 0-weight edges create a perfect matching of the graph. We provide a (4/3)-approximation algorithm and show that the problem is APX-complete. [ABSTRACT FROM AUTHOR]

The firefighter problem models the situation where an infection, a computer virus, an idea or fire etc. is spreading through a network and the goal is to save as many as possible nodes of the network through targeted vaccinations. The number of nodes that can be vaccinated at a single time-step is typically one, or more generally O(l). In a non-standard model, the so called spreading model, the vaccinations also spread in contrast to the standard model. Our main results are concerned with general graphs in the spreading model. We provide a very simple exact 20(√n log n) -time algorithm. In the special case of trees, where the standard and spreading model are equivalent, our algorithm is substan-tially simpler than that exact subexponential algorithm for trees presented in Ref. 2. On the other hand, we show that the firefighter problem on weighted directed graphs in the spreading model cannot be approximated within a constant factor better than 1 -- 1/e unless NP C DTIME (nO(log log n)) We also present several results in the standard model. We provide approximation algorithms for planar graphs in case when at least two vaccinations can be performed at a time-step. We also derive trade-offs between approximation factors for polynomial-time solutions and the time complexity of exact or nearly exact solutions for instances of the firefighter problem for the so called directed layered graphs. [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]

Let A and B be two sets of n resp. m disjoint unit disks in the plane, with m ≥ n. We consider the problem of finding a translation or rigid motion of A that maximizes the total area of overlap with B. The function describing the area of overlap is quite complex, even for combinatorially equivalent translations and, hence, we turn our attention to approximation algorithms. We give deterministic (1 - ∊)-approximation algorithms for translations and for rigid motions, which run in O((nm/∊2) log(m/∊)) and O((n2m2/∊3) log m)) time, respectively. For rigid motions, we can also compute a (1 - ∊)-approximation in O((m2n4/3Δ1/3/∊3) log n log m) time, where Δ is the diameter of set A. Under the condition that the maximum area of overlap is at least a constant fraction of the area of A, we give a probabilistic (1 - ∊)-approximation algorithm for rigid motions that runs in O((m2/∊4) log2(m/∊) log m) time and succeeds with high probability. Our results generalize to the case where A and B consist of possibly intersecting disks of different radii, provided that (i) the ratio of the radii of any two disks in A ∪ B is bounded, and (ii) within each set, the maximum number of disks with a non-empty intersection is bounded. [ABSTRACT FROM AUTHOR]

We consider the multimessage multicasting over the n processor complete (or fully connected) static network when there are l incoming (message) buffers on every processor. We present an efficient algorithm to route the messages for every degree d problem instance in d2/l + l - 1 total communication rounds, where d is the maximum number of messages that each processor may send (or receive). Our algorithm takes linear time with respect to the input length, i.e. O(n + q) where q is the total number of messages that all processors must receive. For l = d we present a lower bound for the total communication time. The lower bound matches the upper bound for the schedules generated by our algorithm. For convenience we assume that the network is completely connected. However, it is important to note that each communication round can be automatically translated into one communication round for processors interconnected via a replication network followed by a permutation network (e.g., two adjacent Benes networks), because in these networks all possible one-to-many communications can be performed in a single communication round. [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]

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]

We study the problem of maintaining a (1 + ∊)-factor approximation of the diameter of a stream of points under the sliding window model. In one dimension, we give a simple algorithm that only needs to store $O({\frac{1}{\epsilon}}\,{\rm log}\,R)$ points at any time, where the parameter R denotes the "spread" of the point set. This bound is optimal and improves Feigenbaum, Kannan, and Zhang's recent solution by two logarithmic factors. We then extend our one-dimensional algorithm to higher constant dimensions and, at the same time, correct an error in the previous solution. In high nonconstant dimensions, we also observe a constant-factor approximation algorithm that requires sublinear space. Related optimization problems, such as the width, are also considered in the two-dimensional case. [ABSTRACT FROM AUTHOR]

We present approximation algorithms for cutting out a polygon P with n vertices from another convex polygon Q with m vertices by line cuts and ray cuts. For line cuts we require both P and Q are convex while for ray cuts we require Q is convex and P is ray cuttable. Our results answer a number of open problems and are either the first solutions or significantly improve over previously known solutions. For the line cutting version, we prove a key property that leads to a simple, constant factor approximation algorithm. For the ray cutting version, we prove it is possible to compute in almost linear time a cutting sequence that is an O(log2 n)-factor approximation of an optimal cutting sequence. No algorithms were previously known for the ray cutting version. [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]

Given a graph with the edge costs satisfying the β-sharpened triangle inequality: cost(u,v)≤β(cost(u,x)+cost(x,v)), for l/2≤β<1, we study the NP-hard problem of finding a minimum cost spanning subgraph which is k-vertex-connected, k≥2. We analyze an approximation quadratic-time algorithm whose performance ratio is $\frac{\beta}{1-\beta}$. The main motivation of this study is to provide an algorithm with a good performance ratio and a practical worst case running time for significative subclasses of the metric Travelling Salesman Problem and the naturally related to it connectivity problems. [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]

We investigate the max flow time scheduling problem in the off-line and on-line setting. We prove positive and negative theoretical results. In the off-line setting, we address the unrelated parallel machines model and present the first known fully polynomial time approximation scheme, when the number of machines is fixed. In the on-line setting and when the machines are identical, we analyze the first In First Out (FIFO) heuristic when preemption is allowed. We show that FIFO is an on-line algorithm with a (3 - 2/m)-competitive ratio. Finally, we present two lower bounds on the competitive ratio of deterministic on-line algorithms. [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]