Special Issue on Memetic Algorithms

The ten papers in this special section are devoted to memetic algorithms. The papers are loosely grouped into two categories: memetic algorithm methodologies and domain-specific memetic algorithms. Briefly summarizes the articles included in this section.     

Approximation Algorithms for Treewidth

This paper presents algorithms whose input is an undirected graph, and whose output is a tree decomposition of width that approximates the optimal, the treewidth of that graph. The algorithms differ in their computation time and their approximation guarantees. The first algorithm works in polynomial-time and finds a factor-O(log OPT) approximation, where OPT is the treewidth of the graph. This is the first polynomial-time algorithm that approximates the optimal by a factor that does not depend on n, the number of nodes in the input graph. As a result, we get an algorithm for finding pathwidth within a factor of O(log OPT⋅log n) from the optimal. We also present algorithms that approximate the treewidth of a graph by constant factors of 3.66, 4, and 4.5, respectively and take time that is exponential in the treewidth. These are more efficient than previously known algorithms by an exponential factor, and are of practical interest. Finding triangulations of minimum treewidth for graphs is central to many problems in computer science. Real-world problems in artificial intelligence, VLSI design and databases are efficiently solvable if we have an efficient approximation algorithm for them. Many of those applications rely on weighted graphs. We extend our results to weighted graphs and weighted treewidth, showing similar approximation results for this more general notion. We report on experimental results confirming the effectiveness of our algorithms for large graphs associated with real-world problems.     

在线学习算法综述

随着信息技术的迅猛发展,尤其是互联网行业的广泛应用,越来越多的领域出现了对海量、高速到达的数据实时处理需求。如何从浩瀚的“数据海洋”中挖掘有用的知识变得尤为重要。传统批处理模式的机器学习算法在面临 大数据时变得力不从心,而在线学习通过流式计算框架,在内存中直接对数据实时运算,为大数据的学习提供了有力的工具,这类在线学习框架有望应对大数据背景下机器学习任务面临的困境与挑战。本文总结了经典和目前主流的在线学习算法,主要包括：(1）在线线性学习算法;(2）基于核的在线学习算法;(3）其他经典的在线学习算法;(4）在线学习算法的优化理论。本文介绍在线学习与深度学习结合方法的研究现状,探讨在线学习算法研究中的关键问题与应用场景,最后展望了在线学习下一步的研究方向。     

Exact and Approximation Algorithms for Clustering

In this paper we present an n^ O(k ^1-1/d ) -time algorithm for solving the k -center problem in \reals ^d , under L _∈ fty - and L ₂ -metrics. The algorithm extends to other metrics, and to the discrete k -center problem. We also describe a simple (1+ɛ) -approximation algorithm for the k -center problem, with running time O(nlog k) + (k/ɛ)^ O(k ^1-1/d ) . Finally, we present an n^ O(k ^1-1/d ) -time algorithm for solving the L -capacitated k -center problem, provided that L=Ω(n/k ^1-1/d ) or L=O(1) . Received July 25, 2000; revised April 6, 2001.     

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.     

Approximation Algorithms for Intersection Graphs

We study three complexity parameters that, for each vertex v, are an upper bound for the number of cliques that are sufficient to cover a subset S(v) of its neighbors. We call a graph k-perfectly groupable if S(v) consists of all neighbors, k-simplicial if S(v) consists of the neighbors with a higher number after assigning distinct numbers to all vertices, and k-perfectly orientable if S(v) consists of the endpoints of all outgoing edges from v for an orientation of all edges. These parameters measure in some sense how chordal-like a graph is—the last parameter was not previously considered in literature. The similarity to chordal graphs is used to construct simple polynomial-time approximation algorithms with constant approximation ratio for many NP-hard problems, when restricted to graphs for which at least one of the three complexity parameters is bounded by a constant. As applications we present approximation algorithms with constant approximation ratio for maximum weighted independent set, minimum (independent) dominating set, minimum vertex coloring, maximum weighted clique, and minimum clique partition for large classes of intersection graphs.     

基于变精度上近似与程度下近似的双量化边界及其算法

近似空间中,精度与程度结合形成的双量化是一个创新课题.利用笛卡尔积进行量化信息合成,基于变精度上近似与程度下近似探讨双量化边界及其算法.首先,基于上述两个近似,自然地构建了双量化扩张粗糙集模型,定义了双量化扩张边界.接着,分析了该边界的双量化语义,得到了该边界的精确刻画与数学性质;为计算该边界,提出了近似集算法与信息粒算法,进行了算法分析与算法比较,得到了信息粒算法具有更优的算法空间复杂性的重要结论.最后,应用一个医疗实例对该边界及其算法进行了说明.该边界扩张了经典Pawlak边界,并对局部不确定性进行了双量化的完备与精细刻画,这对双量化的不确定性分析与应用具有重要意义.     

Approximation Algorithms for Time-Constrained Scheduling on Line Networks

We consider the problem of time-constrained scheduling of packets in a communication network. Each packet has, in addition to its source and its destination, a release time and a deadline. The goal of an algorithm is to maximize the number of packets that arrive to their destinations by their respective deadlines, given the network constraints.     

关于Steiner网络设计问题的近似算法综述

随着因特网中应用的爆炸性增长与网络通讯技术的发展,无论在国防、财政和电源产业等传统领域,还是在新兴的可信计算和网络、云计算系统和下一代互联网等领域,网络的可靠性都得到越来越多的重视.如何在最小化占用网络资源的同时,通过网络的拓扑结构提高网络的可靠性,吸引了广大研究者的兴趣.著名的最小Steiner网络问题就是这个课题中最为引人关注的问题之一.在过去的十年里,作为可靠网络领域的基础问题之一,Steiner网络设计问题得到很好的研究.我们总结了关于Steiner网络设计问题当前最好的近似算法的近似比与时间复杂度,并简明的概述了这些算法的主要思想.