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.     

叠层连续开口圆柱壳的精确解

抛弃任何有关位移和应力模式的假设，引入δ-函数，对正变异性连续开口圆柱壳建立状态方程．给出薄的、中厚的和强厚的叠层连续开口圆柱壳静力问题的统一的精确解．数值结果和SAPS解进行了对比．     

非均匀双向加肋圆柱壳非线性轴对称变形的精确解析法

本文首次利用精确解析法分析了环向和纵向加肋非均匀圆柱壳在任意载荷和边界条件下非线性轴对称变形问题.导出了一致收敛于精确解的位移和内力解析表达式,文中给出收敛性问题.问题最后归结为求解二元一次代数方程组,计算既简便又迅速.文末给出四个数值算例表明,本文提出的方法,可以得到满意的结果.     

An Asymptotic Dynamic Theory for Cylindrical Shells

By expanding the displacement and stress components together with the axial length scale in terms of a small thin shell parameter, three asymptotic shell theories are obtained which incorporate thickness effects in a systematic way. The expansions are made in the equations of linear three-dimensional elasticity. These theories are used to examine the problem of longitudinal wave propagation in a shell of infinite length.     

Exact Controllability and Asymptotic Analysis for Shallow Shells

The authors consider the exact controllability of the vibrations of a thin shallow shell, of thickness 2εwith controls imposed on the lateral surface and at the top and bottom of the shell. Apart from proving the existence of exact controls, it is shown that the solutions of the three dimensional exact controllability problems converge, as the thickness of the shell goes to zero, to the solution of an exact controllability problem in two dimensions.     

The Number of Cylindrical Shells

Given a set P of n points in three dimensions, a cylindrical shell (or zone cylinder) is formed by two circular cylinders with the same axis such that all points of P are between the two cylinders. We prove that the number of cylindrical shells enclosing P passing through combinatorially different subsets of P has size (n ³) and O(n ⁴) (the previously known bound was O(n ⁵)). As a consequence, the minimum enclosing shell can be found in O(n ⁴) time.     

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.     

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 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.     

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 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.     

复合材料叠层圆柱壳的非线性动力稳定性理论

用Hamilton原理建立了复合材料叠层圆柱壳非线性动力稳定性理论的一般性基本方程,其中包含了非线性大挠度,横向剪切,纵向惯性力等因素。用变分法获得基本方程的解。分析表明:叠层圆柱壳在动载荷下会发生参数共振而进入动力不稳定区域而导致动力失稳。计算了几种典型复合材料圆柱壳:即T300/5208石墨环氧,E-玻璃环氧和ARALL圆柱壳。结果表明:这些因素对于各种复合材料圆柱壳的动力稳定性具有程度不同的重要影响,所以研究叠层圆柱壳动力稳定性时,考虑这些因素是重要的。     

多层复合材料圆柱壳的非线性失稳计算

本文用能量法和有限差分法分析了多层复合材料圆柱壳在轴压、静水压力及扭转等载荷作用下的非线性屈曲和后屈曲性能。本文考虑了柱壳的初始缺陷、几何非线性、材料的物理非线性(剪切模量非线性)等因素对于临界载荷的影响。同时还讨论了横向剪切效应。计算分析结果与一些实验结果比较一致。     

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.     

Improved Approximation Algorithms for Geometric Set Cover

Given a collection S of subsets of some set and the set cover problem is to find the smallest subcollection that covers that is, where denotes We assume of course that S covers While the general problem is NP-hard to solve, even approximately, here we consider some geometric special cases, where usually Combining previously known techniques [4], [5], we show that polynomial-time approximation algorithms with provable performance exist, under a certain general condition: that for a random subset and nondecreasing function f(·), there is a decomposition of the complement into an expected at most f(|R|) regions, each region of a particular simple form. Under this condition, a cover of size O(f(|C|)) can be found in polynomial time. Using this result, and combinatorial geometry results implying bounding functions f(c) that are nearly linear, we obtain o(log c) approximation algorithms for covering by fat triangles, by pseudo-disks, by a family of fat objects, and others. Similarly, constant-factor approximations follow for similar-sized fat triangles and fat objects, and for fat wedges. With more work, we obtain constant-factor approximation algorithms for covering by unit cubes in and for guarding an x-monotone polygonal chain.     

Complexity Results and Exact Algorithms for Robust Knapsack Problems

This paper studies the robust knapsack problem, for which solutions are, up to a certain point, immune from data uncertainty. We complement the works found in the literature, where uncertainty affects only the profits or only the weights of the items, by studying the complexity and approximation of the general setting with uncertainty regarding both the profits and the weights, for three different objective functions. Furthermore, we develop a scenario-relaxation algorithm for solving the general problem and present computational results.     

强厚度叠层悬臂圆柱壳的精确解

抛弃任何有关位移或应力模式的人为假设，在柱坐标系下对正交异性体建立其状态方程，给出强厚度叠层闭口悬臂圆柱壳静力问题的精确解，此解满足所有基本方程，包含了全部弹性常数可得到任意需要的精度。