A linear-time algorithm for finding approximate shortest common superstrings

Approximate shortest common superstrings for a given setR of strings can be constructed by applying the greedy heuristics for finding a longest Hamiltonian path in the weighted graph that represents the pairwise overlaps between the strings inR. We develop an efficient implementation of this idea using a modified Aho-Corasick string-matching automaton. The resulting common superstring algorithm runs in timeO(n) or in timeO(n min(logm, log¦¦)) depending on whether or not the goto transitions of the Aho-Corasick automaton can be implemented by direct indexing over the alphabet . Heren is the total length of the strings inR andm is the number of such strings. The best previously known method requires timeO(n logm) orO(n logn) depending on the availability of direct indexing.This work was supported by the Academy of Finland.     

An 11/6-approximation algorithm for the network steiner problem

An instance of the Network Steiner Problem consists of an undirected graph with edge lengths and a subset of vertices; the goal is to find a minimum cost Steiner tree of the given subset (i.e., minimum cost subset of edges which spans it). An 11/6-approximation algorithm for this problem is given. The approximate Steiner tree can be computed in the time0(¦V¦ ¦E¦ + ¦S¦⁴), whereV is the vertex set,E is the edge set of the graph, andS is the given subset of vertices.     

On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems

We show that the fixed alphabet shortest common supersequence (SCS) and the fixed alphabet longest common subsequence (LCS) problems parameterized in the number of strings are W[1]-hard. Unless W[1]=FPT, this rules out the existence of algorithms with time complexity of O(f(k)nα) for those problems. Here n is the size of the problem instance, α is constant, k is the number of strings and f is any function of k. The fixed alphabet version of the LCS problem is of particular interest considering the importance of sequence comparison (e.g. multiple sequence alignment) in the fixed length alphabet world of DNA and protein sequences.     

An optimal approximation algorithm for the rectilinearm-center problem

Given a set ofn points on the plane, the rectilinearm-center problem is to findn rectilinear squares covering all thesen points such that the maximum side length of these squares is minimized. In this paper we prove that there is no polynomial-time algorithm with an error ratio < 2 for the rectilinearm-center problem unless NP = P. A polynomial-time approximation algorithm with an error ratio of 2 is also proposed.This research work was partially supported by a grant from the National Science Council of the Republic of China under Grant NSC-77-0408-E007-03.     

An algorithm for the three-dimensional packing problem with asymptotic performance analysis

The three-dimensional packing problem can be stated as follows. Given a list of boxes, each with a given length, width, and height, the problem is to pack these boxes into a rectangular box of fixed-size bottom and unbounded height, so that the height of this packing is minimized. The boxes have to be packed orthogonally and oriented in all three dimensions. We present an approximation algorithm for this problem and show that its asymptotic performance bound is between 2.5 and 2.67. This result answers a question raised by Li and Cheng [5] about the existence of an algorithm for this problem with an asymptotic performance bound less than 2.89. This research was partially supported by FAPESP (proc. 93/0603-1) and by CNPq/ProTeM-CC, project ProComb (proc. 680065/94-6).     

An efficient fault-containing self-stabilizing algorithm for the shortest path problem

Shortest path finding has a variety of applications in transportation and communication. In this paper, we propose a fault-containing self-stabilizing algorithm for the shortest path problem in a distributed system. The improvement made by the proposed algorithm in stabilization times for single-fault situations can demonstrate the desirability of an efficient fault-containing self-stabilizing algorithm. For single-fault situations, the worst-case stabilization time of the proposed algorithm is O(Δ), where Δ is the maximum node degree in the system, and the contamination number of the proposed algorithm is 1.     

An improved genetic algorithm with conditional genetic operators and its application to set-covering problem

The genetic algorithm (GA) is a popular, biologically inspired optimization method. However, in the GA there is no rule of thumb to design the GA operators and select GA parameters. Instead, trial-and-error has to be applied. In this paper we present an improved genetic algorithm in which crossover and mutation are performed conditionally instead of probability. Because there are no crossover rate and mutation rate to be selected, the proposed improved GA can be more easily applied to a problem than the conventional genetic algorithms. The proposed improved genetic algorithm is applied to solve the set-covering problem. Experimental studies show that the improved GA produces better results over the conventional one and other methods.     

BEAMR: An exact and approximate model for the p-median problem

The p-median problem is perhaps one of the most well-known location–allocation models in the location science literature. It was originally defined by Hakimi in 1964 and 1965 and involves the location of p facilities on a network in such a manner that the total weighted distance of serving all demand is minimized. This problem has since been the subject of considerable research involving the development of specialized solution approaches as well as the development of many different types of extended model formats. One element of past research that has remained almost constant is the original ReVelle–Swain formulation [ReVelle CS, Swain R. Central facilities location. Geographical Analysis 1970;2:30–42]. With few exceptions as detailed in the paper, virtually no new formulations have been proposed for general use in solving the classic p-median problem. This paper proposes a new model formulation for the p-median problem that contains both exact and approximate features. This new p-median formulation is called Both Exact and Approximate Model Representation (BEAMR). We show that BEAMR can result in a substantially smaller integer-linear formulation for a given application of the p-median problem and can be used to solve for either an exact optimum or a bounded, close to optimal solution. We also present a methodological framework in which the BEAMR model can be used. Computational results for problems found in the OR_library of Beasley [A note on solving large p-median problems. European Journal of Operational Research 1985;21:270–3] indicate that BEAMR not only extends the application frontier for the p-median problem using general-purpose software, but for many problems represents an efficient, competitive solution approach.     

An almost-linear time and linear space algorithm for the longest common subsequence problem

There are two general approaches to the longest common subsequence problem. The dynamic programming approach takes quadratic time but linear space, while the nondynamic-programming approach takes less time but more space. We propose a new implementation of the latter approach which seems to get the best for both time and space for the DNA application.     

Order relation between intervals and its application to shortest path problem

It is true that intervals are frequently partially ordered and cannot be compared. Nevertheless, varous definitions for ranking intervals have been proposed. In this paper, we propose a new definition for order relation between intervals by introducing a parameter called “a degree between partial and total order”, and apply it to the shortest path problem with arcs represented as intervals. In order to solve this problem, we modify the Dijkstra's algorithm, and propose a new algorithm obtaining some incomparable interval solutions. Finally, a numerical example is shown.     

An approximation algorithm to the k-Steiner Forest problem

Given a graph G$G$, an integer k$k$, and a demand set D={(_s1,_t1),…,(_sl,_tl)}$D=\{(s_1,t_1),\dots ,(s_l,t_l)\}$, the k$k$-Steiner Forest problem finds a forest in graph G$G$ to connect at least k$k$ demands in D$D$ such that the cost of the forest is minimized. This problem was proposed by Hajiaghayi and Jain in SODA’06. Thereafter, using a Lagrangian relaxation technique, Segev et al. gave the first approximation algorithm to this problem in ESA’06, with performance ratio O(n^2/3logl)$O(n^{2/3}logl)$. We give a simpler and faster approximation algorithm to this problem with performance ratio O(n^2/3logk)$O(n^{2/3}logk)$ via greedy approach, improving the previously best known ratio in the literature.     

Mean analysis of an online algorithm for the vertex cover problem

In 2005, Demange and Paschos proposed in [M. Demange, V.Th. Paschos, On-line vertex-covering, Theoret. Comput. Sci. 332 (2005) 83-108] an online algorithm (noted LR here) for the classical vertex cover problem. They shown that, for any graph of maximum degree Δ, LR constructs a vertex cover whose size is at most Δ times the optimal one (this bound is tight in the worst case).Very recently, two of the present authors have shown in [F. Delbot, C. Laforest, A better list heuristic for vertex cover, Inform. Process. Lett. 107 (2008) 125-127] that LR has interesting properties (it is a good “list algorithm” and it can easily be distributed). In addition, LR has good experimental behavior in spite of its Δ approximation (or competitive) ratio and the fact that it can be executed without the knowledge of the full instance at the beginning.In this paper we analyze it deeper and we show that LR has good “average” performances: we prove that its mean approximation ratio is strictly less than 2 for any graph and is equal to 1+e−2≈1.13 in paths. LR is then a very interesting algorithm for constructing small vertex covers, despite its bad worst case behavior.     

自适应布谷鸟算法及其在化工优化中的应用

动态优化问题广泛存在于化工自动控制过程中,对其求解是化工过程工业发展的一个不可忽视的环节。群智能算法求解此类优化问题时不可避免地存在后期收敛速度慢、求解精度的不高等不足,这一直是一个研究热点。针对新兴的布谷鸟算法与以上问题,提出一种变步长自适应布谷鸟搜索算法(VSACS),将基本布谷鸟搜索(CS)算法中的随机步长改进成根据迭代次数自适应调整的步长。通过15个标准测试函数的测试,结果验证了改进的算法有较快的收敛速度和较高的求解精度。最后将改进的算法用于批示反应器、管式反应器、生物反应器等3个典型的化工动态优化问题中,获得了满意的实验结果,同时也进一步表明该算法的有效性。     

背包问题混合遗传算法在电力恢复中的应用

文章把电力系统的负荷恢复问题建模为带众多约束条件的0-1背包问题,并设计了一种将贪心算法与改进遗传算法结合起来的改进混合遗传算法来对此问题进行求解.该算法的主要特点是具有群体爬山性和利用了郭涛算子的非凸组合技术使算法具有搜索的遍历性.采用此算法可以得到负荷恢复的某一阶段可恢复的最大的负荷量.求解的过程保证了求得的解是满足系统的约束条件,所以系统的负荷恢复过程是安全的.算例的结果表明了该算法的有效性.     

An improved approximation algorithm for the metric maximum clustering problem with given cluster sizes

The input to the metric maximum clustering problem with given cluster sizes consists of a complete graph G=(V,E) with edge weights satisfying the triangle inequality, and integers c₁,…,cp. The goal is to find a partition of V into disjoint clusters of sizes c₁,…,cp, maximizing the sum of weights of edges whose two ends belong to the same cluster. We describe an approximation algorithms for this problem with performance guarantee that approaches 0.5 when the cluster sizes are large.     

三层并行遗传算法及装箱问题中的应用

提出了一个新的基于线程构建模块(TBB)的三层并行遗传算法(TPGA)。与传统遗传算法相比,在保证了算法正确性的前提下提高了运行效率,并将遗传算法的数据编码、任务处理和数据解码分别进行并行化,提高了收敛速度。TBB是Intel提供的能够完整表现并行性的代码库。采用C++语言实现了基于TBB的TPGA和串行遗传算法(SGA),通过大量实验证明,TPGA同SGA相比,不但提高了收敛速度,而且能够取得一致的最优解。     

A 3.4713-approximation algorithm for the capacitated multicast tree routing problem

Given an underlying communication network represented as an edge-weighted graph G=(V,E), a source node sV, a set of destination nodes DV, and a capacity k which is a positive integer, the capacitated multicast tree routing problem asks for a minimum cost routing scheme for source s to send data to all destination nodes, under the constraint that in each routing tree at most k destination nodes are allowed to receive the data copies. The cost of the routing scheme is the sum of the costs of all individual routing trees therein. Improving on our previous approximation algorithm for the problem, we present a new algorithm which achieves a worst case performance ratio of , where ρ denotes the best known approximation ratio for the Steiner minimum tree problem. Since ρ is about 1.55 at the writing of the paper, the ratio achieved by our new algorithm is less than 3.4713. In comparison, the previously best ratio was .     

A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs

In recent years growing interest in local distributed algorithms has widely been observed. This results from their high resistance to errors and damage, as well as from their good performance, which is independent of the size of the network. A local deterministic distributed algorithm finding an approximation of a Minimum Dominating Set in planar graphs has been presented by Lenzen et al., and they proved that the algorithm returns a 130-approximation of the Minimum Dominating Set. In this article we will show that the algorithm is two times more effective than was previously assumed, and we prove that the algorithm by Lenzen et al. outputs a 52-approximation to a Minimum Dominating Set. Therefore the gap between the lower bound and the approximation ratio of the best yet local deterministic distributed algorithm is reduced by half.