Improved Approximation Algorithms for Tree Alignment

Multiple sequence alignment is a task at the heart of much of current computational biology[4]. Several different objective functions have been proposed to formalize the task of multiple sequence alignment, but efficient algorithms are lacking in each case. Thus multiple sequence alignment is one of the most critical, essentially unsolved problems in computational biology. In this paper we consider one of the more compelling objective functions for multiple sequence alignment, formalized as thetree alignment problem. Previously in[13], a ratio-two approximation method was developed for tree alignment, which ran incubictime (as a function of the number of fixed length strings to be aligned), along with a polynomial time approximation scheme (PTAS) for the problem. However, the PTAS in[13]had a running time which made it impractical to reduce the performance ratio much below two for small size biological sequences (100 characters long). In this paper we first develop a ratio-two approximation algorithm which runs inquadratictime, and then use it to develop a PTAS which has a better performance ratio and a vastly improved worst case running time compared to the scheme in[13]for the case where the given tree is a regular deg-ary tree. With the new approximation scheme, it is now practical to guarantee a ratio of 1.583 for strings of lengths 200 characters or less.     

Approximation Algorithms for Maximum Independent Set of Pseudo-Disks

We present approximation algorithms for maximum independent set of pseudo-disks in the plane, both in the weighted and unweighted cases. For the unweighted case, we prove that a local-search algorithm yields a PTAS. For the weighted case, we suggest a novel rounding scheme based on an LP relaxation of the problem, which leads to a constant-factor approximation. Most previous algorithms for maximum independent set (in geometric settings) relied on packing arguments that are not applicable in this case. As such, the analysis of both algorithms requires some new combinatorial ideas, which we believe to be of independent interest.     

Improved Results on Geometric Hitting Set Problems

We consider the problem of computing minimum geometric hitting sets in which, given a set of geometric objects and a set of points, the goal is to compute the smallest subset of points that hit all geometric objects. The problem is known to be strongly NP-hard even for simple geometric objects like unit disks in the plane. Therefore, unless P = NP, it is not possible to get Fully Polynomial Time Approximation Algorithms (FPTAS) for such problems. We give the first PTAS for this problem when the geometric objects are half-spaces in ?³ and when they are an r-admissible set regions in the plane (this includes pseudo-disks as they are 2-admissible). Quite surprisingly, our algorithm is a very simple local-search algorithm which iterates over local improvements only.     

Approximation Algorithms for Dispersion Problems

Given a collection of weighted sets, each containing at most k elements drawn from a finite base set, the k-set packing problem is to find a maximum weight sub-collection of disjoint sets. A greedy algorithm for this problem approximates it to within a factor of k, and a natural local search has been shown to approximate it to within a factor of roughly k − 1. However, neither paradigm can yield approximations that improve on this.We present an approximation algorithm for the weighted k-set packing problem that combines the two paradigms by starting with an initial greedy solution and then repeatedly choosing the best possible local improvement. The algorithm has a performance ratio of 2(k + 1)/3, which we show is asymptotically tight. This is the first asymptotic improvement over the straightforward ratio of k.     

Approximation Algorithms for Pick-and-Place Robots

In this paper we study the problem of finding placement tours for pick-and-place robots, also known as the printed circuit board assembly problem with m positions on a board, n bins containing m components and n locations for the bins. In the standard model where the working time of the robot is proportional to the distances travelled, the general problem appears as a combination of the travelling salesman problem and the matching problem, and for m=n we have an Euclidean, bipartite travelling salesman problem. We give a polynomial-time algorithm which achieves an approximation guarantee of 3+. An important special instance of the problem is the case of a fixed assignment of bins to bin-locations. This appears as a special case of a bipartite TSP satisfying the quadrangle inequality and given some fixed matching arcs. We obtain a 1.8 factor approximation with the stacker crane algorithm of Frederikson, Hecht and Kim. For the general bipartite case we also show a 2.0 factor approximation algorithm which is based on a new insertion technique for bipartite TSPs with quadrangle inequality. Implementations and experiments on real-world as well as random point configurations conclude this paper.     

Multi-Pass Geometric Algorithms

We propose the study of exact geometric algorithms that require limited storage and make only a small number of passes over the input. Fundamental problems such as low-dimensional linear programming and convex hulls are considered.     

Approximation Algorithms for the Achromatic Number

The achromatic number for a graph G = V, E is the largest integer m such that there is a partition of V into disjoint independent sets {V₁, …, V_m} such that for each pair of distinct sets V_i, V_j, V_i V_j is not an independent set in G. Yannakakis and Gavril (1980, SIAM J. Appl. Math.38, 364–372) proved that determining this value for general graphs is NP-complete. For n-vertex graphs we present the first o(n) approximation algorithm for this problem. We also present an O(n^5/12) approximation algorithm for graphs with girth at least 5 and a constant approximation algorithm for trees.     

Efficient Subspace Approximation Algorithms

We consider the problem of fitting a subspace of a specified dimension k to a set P of n points in ℝ ^d . The fit of a subspace F is measured by the L _τ norm, that is, it is defined as the τ-root of the sum of the τth powers of the Euclidean distances of the points in P from F, for some τ≥1. Our main result is a randomized algorithm that takes as input P, k, and a parameter 0<ε<1; runs in nd ·2^{O(fractk2e log2 frac ke)}nd cdot2^{O(frac{tau k^{2}}{varepsilon} log^{2} frac {k}{varepsilon})} time, and returns a k-subspace that with probability at least 1/2 has a fit that is at most (1+ε) times that of the optimal k-subspace.     

Approximation Algorithms for Minimum-Width Annuli and Shells

Let S be a set of n points in \re ^d . The ``roundness' of S can be measured by computing the width ω ^* =ω ^* (S) of the thinnest spherical shell (or annulus in \re ² ) that contains S . This paper contains two main results related to computing an approximation of ω ^* : (i) For d=2 , we can compute in O(n log n) time an annulus containing S whose width is at most 2ω ^* (S) . We extend this algorithm, so that, for any given parameter ε >0 , an annulus containing S whose width is at most (1+ε )ω ^* is computed in time O(n log n + n/ε ² ) . (ii) For d \geq 3 , given a parameter ε > 0 , we can compute a shell containing S of width at most (1+ε)ω ^* either in time O ( n / ε ^d ) log ( \Delata / ω ^* ε ) or in time O ( n / ε ^d-2 ) log n + 1 / εlog \Delata / ω ^* ε , where Δ is the diameter of S . Received July 6, 1999, and in revised form April 17, 2000. Online publication August\/ 11, 2000.     

Approximation Algorithms for Steiner and Directed Multicuts

In this paper we consider theSteiner multicutproblem. This is a generalization of the minimum multicut problem where instead of separating nodepairs, the goal is to find a minimum weight set of edges that separates all givensetsof nodes. A set is considered separated if it is not contained in a single connected component. We show anO(log³(kt)) approximation algorithm for the Steiner multicut problem, wherekis the number of sets andtis the maximum cardinality of a set. This improves theO(t log k) bound that easily follows from the previously known multicut results. We also consider an extension of multicuts to directed case, namely the problem of finding a minimum-weight set of edges whose removal ensures that none of the strongly connected components includes one of the prespecifiedknode pairs. In this paper we describe anO(log² k) approximation algorithm for this directed multicut problem. Ifk ? n, this represents an improvement over theO(log n log log n) approximation algorithm that is implied by the technique of Seymour.     

Fast Enumeration Algorithms for Non-crossing Geometric Graphs

A non-crossing geometric graph is a graph embedded on a set of points in the plane with non-crossing straight line segments. In this paper we present a general framework for enumerating non-crossing geometric graphs on a given point set. Applying our idea to specific enumeration problems, we obtain faster algorithms for enumerating plane straight-line graphs, non-crossing spanning connected graphs, non-crossing spanning trees, and non-crossing minimally rigid graphs. Our idea also produces efficient enumeration algorithms for other graph classes, for which no algorithm has been reported so far, such as non-crossing matchings, non-crossing red-and-blue matchings, non-crossing k-vertex or k-edge connected graphs, or non-crossing directed spanning trees. The proposed idea is relatively simple and potentially applies to various other problems of non-crossing geometric graphs.     

Algorithms for the Set Covering Problem

The Set Covering Problem (SCP) is a main model for several important applications, including crew scheduling in railway and mass-transit companies. In this survey, we focus our attention on the most recent and effective algorithms for SCP, considering both heuristic and exact approaches, outlining their main characteristics and presenting an experimental comparison on the test-bed instances of Beasley's OR Library.     

基于CCH的SVM几何算法及其应用

支持向量机(support vector machine(SVM))是一种数据挖掘中新型机器学习方法.提出了基于压缩凸包(compressed convex hull(CCH))的SVM分类问题的几何算法.对比简约凸包(reducedconvex hull(RCH)),CCH保持了数据的几何体形状,并且易于得到确定其极点的充要条件.作为CCH的实际应用,讨论了该几何算法的稀疏化方法及概率加速算法.数值试验结果表明所讨论的算法可降低核计算并取得较好的性能.     

Exact and Approximation Algorithms for Minimum-Width Cylindrical Shells

Let S be a set of n points in reals ³ . Let opt be the width (i.e., thickness) of a minimum-width infinite cylindrical shell (the region between two co-axial cylinders) containing S . We first present an O(n ⁵ ) -time algorithm for computing opt , which as far as we know is the first nontrivial algorithm for this problem. We then present an O(n ^2+δ ) -time algorithm, for any δ>0 , that computes a cylindrical shell of width at most 56opt containing S . Received May 31, 2000, and in revised form October 25, 2000. Online publication August 29, 2001.     

Approximation Algorithms for Min–Max Tree Partition

We consider the problem of partitioning the node set of a graph intopequal sized subsets. The objective is to minimize the maximum length, over these subsets, of a minimum spanning tree. We show that no polynomial algorithm with bounded error ratio can be given for the problem unless P = NP. We present anO(n²) time algorithm for the problem, wherenis the number of nodes in the graph. Assuming that the edge lengths satisfy the triangle inequality, its error ratio is at most 2p − 1. We also present an improved algorithm that obtains as an input a positive integerx. It runs inO(2^{(p + x)p}n²) time, and its error ratio is at most (2 − x/(x + p − 1))p.     

A Strong Approximation Theorem for Stochastic Recursive Algorithms

The constant stepsize analog of Gelfand–Mitter type discrete-time stochastic recursive algorithms is shown to track an associated stochastic differential equation in the strong sense, i.e., with respect to an appropriate divergence measure.     

Convergent Outer Approximation Algorithms for Solving Unary Programs

Interesting cutting plane approaches for solving certain difficult multiextremal global optimization problems can fail to converge. Examples include the concavity cut method for concave minimization and Ramana's recent outer approximation method for unary programs which are linear programming problems with an additional constraint requiring that an affine mapping becomes unary. For the latter problem class, new convergent outer approximation algorithms are proposed which are based on sufficiently deep l-norm or quadratic cuts. Implementable versions construct optimal simplicial inner approximations of Euclidean balls and of intersections of Euclidean balls with halfspaces, which are of general interest in computational convexity. Computational behavior of the algorithms depends crucially on the matrices involved in the unary condition. Potential applications to the global minimization of indefinite quadratic functions subject to indefinite quadratic constraints are shown to be practical only for very small problem sizes.