Improved Algorithms for Uniform Partitions of Points

Abstract. We consider the following one- and two-dimensional bucketing problems: Given a set S of n points in \reals ¹ or \reals ² and a positive integer b , distribute the points of S into b equal-size buckets so that the maximum number of points in a bucket is minimized. Suppose at most (n/b) + Δ points lie in each bucket in an optimal solution. We present algorithms whose time complexities depend on b and Δ . No prior knowledge of Δ is necessary for our algorithms. For the one-dimensional problem, we give a deterministic algorithm that achieves a running time of O(b ⁴ (Δ ² +log n) + n) . For the two-dimensional problem, we present a Monte Carlo algorithm that runs in subquadratic time for small values of b and Δ . The previous algorithms, by Asano and Tokuyama [1], searched the entire parameterized space and required Ω ( n ² ) time in the worst case even for constant values of b and Δ . We also present a subquadratic algorithm for the special case of the two-dimensional problem when b=2 .     

Parallel Algorithms for Counting and Randomly Generating Integer Partitions

This paper presents parallel algorithms for determining the number of partitions of a given integerN, where the partitions may be subject to restrictions, such as being composed of distinct parts, of a given number of parts, and/or of parts belonging to a specified set. We present a series of adaptive algorithms suitable for varying numbers of processors. The fastest of these algorithms computes the number of partitions ofnwith largest part equal tok, for 1 ≤k≤n≤N, in timeO(log²(N)) usingO(N²/logN) processors. Parallel logarithmic time algorithms that generate partitions uniformly at random, using these quantities, are also presented.     

Approximation Algorithms for Aligning Points

We study the problem of aligning as many points as possible horizontally, vertically, or diagonally, when each point is allowed to be placed anywhere in its own given region. Different shapes of placement regions and different sets of alignment orientations are considered. More generally, we assume that a graph is given on the points, and only the alignments of points that are connected in the graph count. We show that for planar graphs the problem is NP-hard, and we provide an inapproximability result for general graphs. For the case of trees and planar graphs, we give approximation algorithms whose performance depends on the shape of the given regions and the set of orientations. When the orientations are the ones given by the axes and the regions are axis-parallel rectangles, we obtain a polynomial time approximation scheme.     

Token-Based Self-Stabilizing Uniform Algorithms

This work focuses on self-stabilizing algorithms for mutual exclusion and leader election—two fundamental tasks for distributed systems. Self-stabilizing systems are able to recover by themselves, regaining their consistency from any initial or intermediary faulty configuration. The proposed algorithms are designed for any directed, anonymous network and stabilize under any distributed scheduler. The keystones of the algorithms are the token management and routing policies. In order to break the network symmetry, randomization is used. The space complexity is O((D⁺+D⁻)(log(snd(n))+2)) where n is the network size, snd(n) is the smallest integer that does not divide n and D⁺ and D⁻ are the maximal out and in degree, respectively. It should be noted that snd(n) is constant on the average and equals 2 on odd-size networks.     

平面最接近点对算法

描述了平面最接近点对问题,针对这一问题给出了3种算法,循环遍历算法、分治算法和平面扫描算法,并详细分析了3种算法的时间复杂度.     

平面最接近点对算法

描述了平面最接近点对问题,针对这一问题给出了3种算法,循环遍历算法、分治算法和平面扫描算法,并详细分析了3种算法的时间复杂度。     

遗传算法的改进

简要介绍了一般遗传算法的基本原理，由此提出了一个新的改进算法，它导向以适应度比较高的模式为祖先的染色体“家族”方向。文中给出了两个典型求最大值的例子，从结果中看，改进后的遗传算法大大提高了算法的速度，精度也有所提高。     

Improved Algorithms for Partial Curve Matching

We revisit the problem of deciding whether a given curve resembles some part of a larger curve under a fixed Fréchet distance, achieving a running time of O(nm), for n and m being the number of segments in the two curves. This improves the long-standing result of Alt and Godau by an O(log(nm)) factor. Our solution is based on constructing a simple data structure which we call free-space map. Using this data structure, we obtain improved algorithms for several variants of the Fréchet distance problem, including the Fréchet distance between two closed curves, and the so-called minimum/maximum walk problems. We also improve the map matching algorithm of Alt et al. for the particular case in which the map is a directed acyclic graph.     

Improved Approximation Algorithms for Data Migration

Our work is motivated by the need to manage data items on a collection of storage devices to handle dynamically changing demand. As demand for data items changes, for performance reasons, the system needs to automatically respond to changes in demand for different data items. The problem of computing a migration plan among the storage devices is called the data migration problem. This problem was shown to be NP-hard, and an approximation algorithm achieving an approximation factor of 9.5 was presented for the half-duplex communication model in Khuller, Kim and Wan (Algorithms for data migration with cloning. SIAM J. Comput. 33(2):448–461, 2004). In this paper we develop an improved approximation algorithm that gives a bound of 6.5+o(1) using new ideas. In addition, we develop better algorithms using external disks and get an approximation factor of 4.5 using external disks. We also consider the full duplex communication model and develop an improved bound of 4+o(1) for this model, with no external disks.     

Improved Algorithms for Dynamic Shortest Paths

We describe algorithms for finding shortest paths and distances in outerplanar and planar digraphs that exploit the particular topology of the input graph. An important feature of our algorithms is that they can work in a dynamic environment, where the cost of any edge can be changed or the edge can be deleted. In the case of outerplanar digraphs, our data structures can be updated after any such change in only logarithmic time. A distance query is also answered in logarithmic time. In the case of planar digraphs, we give an interesting tradeoff between preprocessing, query, and update times depending on the value of a certain topological parameter of the graph. Our results can be extended to n -vertex digraphs of genus O(n ^1-ε ) for any ε>0 . Received September 24, 1996; revised May 13, 1998, and January 20, 1999.     

Improved Algorithms for Constructing Fault-Tolerant Spanners

Let S be a set of n points in a metric space, and let k be a positive integer. Algorithms are given that construct k -fault-tolerant spanners for S . If in such a spanner at most k vertices and/ or edges are removed, then each pair of points in the remaining graph is still connected by a ``short'' path. First, an algorithm is given that transforms an arbitrary spanner into a k -fault-tolerant spanner. For the Euclidean metric in R ^d , this leads to an O(n log n + c ^k n) -time algorithm that constructs a k -fault-tolerant spanner of degree O(c ^k ) , whose total edge length is O(c ^k ) times the weight of a minimum spanning tree of S , for some constant c . For constant values of k , this result is optimal. In the second part of the paper, algorithms are presented for the Euclidean metric in R ^d . These algorithms construct (i) in O(n log n + k ² n) time, a k -fault-tolerant spanner with O(k ² n) edges, and (ii) in O(k n log n) time, such a spanner with O(k n log n) edges.     

Improved Algorithms for Constructing Fault-Tolerant Spanners

Abstract. Let S be a set of n points in a metric space, and let k be a positive integer. Algorithms are given that construct k -fault-tolerant spanners for S . If in such a spanner at most k vertices and/ or edges are removed, then each pair of points in the remaining graph is still connected by a ``short' path. First, an algorithm is given that transforms an arbitrary spanner into a k -fault-tolerant spanner. For the Euclidean metric in R ^d , this leads to an O(n log n + c ^k n) -time algorithm that constructs a k -fault-tolerant spanner of degree O(c ^k ) , whose total edge length is O(c ^k ) times the weight of a minimum spanning tree of S , for some constant c . For constant values of k , this result is optimal. In the second part of the paper, algorithms are presented for the Euclidean metric in R ^d . These algorithms construct (i) in O(n log n + k ² n) time, a k -fault-tolerant spanner with O(k ² n) edges, and (ii) in O(k n log n) time, such a spanner with O(k n log n) edges.     

Improved Distributed Algorithms for SCC Decomposition

We study and improve the OBF technique [Barnat, J. and P.Moravec, Parallel algorithms for finding SCCs in implicitly given graphs, in: Proceedings of the 5th International Workshop on Parallel and Distributed Methods in Verification (PDMC 2006), LNCS (2007)], which was used in distributed algorithms for the decomposition of a partitioned graph into its strongly connected components. In particular, we introduce a recursive variant of OBF and experimentally evaluate several different implementations of it that vary in the degree of parallelism. For the evaluation we used synthetic graphs with a few large components and graphs with many small components. We also experimented with graphs that arise as state spaces in real model checking applications. The experimental results are compared with that of other successful SCC decomposition techniques [Orzan, S., “On Distributed Verification and Verified Distribution,” Ph.D. thesis, Free University of Amsterdam (2004); Fleischer, L.K., B. Hendrickson and A. Pinar, On identifying strongly connected components in parallel, in: Parallel and Distributed Processing, IPDPS Workshops, Lecture Notes in Computer Science 1800, 2000, pp. 505–511].     

加权3D-Matching的改进算法

Matching问题构成了一类重要的NP难问题.此类问题在诸多领域中有着重要的应用,如调度、代码优化等领域.对于加权3D-matching问题,通过深入分析问题的结构特性,可以转化成加权3D-matching augmentation问题进行求解,即从一个最大加权的k-matching着手构造权值最大的(k+1)-matching.从问题的特殊结构特性出发,给出了加权3D-matching augmentation问题特有的性质: k- matching中存在2列使得该2列至少有2k/3元素被包含在(k+1)-matching中所对应的2列中.基于给出的性质,通过运用color-coding和动态规划技术,给出了一个时间复杂度为O* (4.823k)的参数算法,最终求解加权3D-matching问题.该算法较目前文献中的最好结果O* (5.473k)有了极大的改进.     

旅行商问题(TSP)的一种改进遗传算法

传统的序号编码遗传算法(GA)使用PMX、CX和OX等特殊的交叉算子，这些算子实施起来很麻烦。针对TSP问题的求解，提出了一种新的改进遗传算法：单亲进化遗传算法(PEGA)，PEGA是利用父体所提供的有效边的信息，使用保留最小边的方法进行个体的进化。与传统的遗传算法相比，PEGA算法弥补了它们的不足之处，简化了遗传算法。给出了PEGA算法的数值算例，仿真实验表明了该算法对于对称的TSP和非对称的TSP问题，都具有收敛速度快的特点，证明了该算法的有效性。     

遗传算法的改进

简要介绍了一般遗传算法的基本原理,由此提出了一个新的改进算法,它导向以适应度比较高的模式为祖先的染色体"家族"方向.文中给出了两个典型求最大值的例子,从结果中看,改进后的遗传算法大大提高了算法的速度,精度也有所提高.     

一种混合改进遗传算法的嵌套分区算法

提出一种混合改进遗传算法的嵌套分区算法用于求解旅行商问题。该算法首先使用加权抽样法产生初始最可能域,用全局数组保存每个区域的历史最优解,设计子域交叉算子和子域变异算子,并用改进的遗传算法搜索每个子域和裙域的最好解,然后对Lin-Kernighan算法进行改进,并且在搜索裙域中最好解时,对种群中优秀个体用改进的Lin-Kernighan算法进行优化。对TSPLIB中问题实例的仿真结果表明,所提出的混合改进遗传算法的嵌套分区算法在求解旅行商问题时可以获得高质量的解。     

遗传算法“早熟”现象的改进策略

改善遗传算法中的“早熟”现象可以通过提供某种机制以恢复群体多样性。基于这种思想，该文参照其他遗传算法改进策略，从弥补丢失模式、提高模式浓度出发，提出了通过保持模式的多样性来保证群体多样性的方法。为了衡量改进策略的有效性，引入了模式再生期望值的概念，并利用模式再生期望值的分析方法分析了一种实用的改进策略。实验数据证明了该策略的有效性。     

网络最短路问题的改进算法

本文着重研究著名的Dijkstra网络最短路算法的实现效率，提出算法实现的若干技巧，大大提高了Dijkstra最短路算法的适用性和时间空间效率。