Multistart Iterated Tabu Search for Bandwidth Coloring Problem

This paper presents a Multistart Iterated Tabu Search (MITS) algorithm for solving Bandwidth Coloring Problem (BCP) and Bandwidth MultiColoring Problem (BMCP). The proposed MITS algorithm exhibits several distinguishing features, such as integrating an Iterated Tabu Search (ITS) algorithm with a multistart method and a problem specific perturbation operator. Tested on two sets of 66 public benchmark instances widely used in the literature, the MITS algorithm achieves highly competitive results compared with the best performing algorithms, improving the previous best known results for 22 instances while matching the previous best known results for 39 ones. Furthermore, two important features of the proposed algorithm are analyzed.     

A DSATUR-based algorithm for the Equitable Coloring Problem

This paper describes a new exact algorithm for the Equitable Coloring Problem, a coloring problem where the sizes of two arbitrary color classes differ in at most one unit. Based on the well known DSatur algorithm for the classic Coloring Problem, a pruning criterion arising from equity constraints is proposed and analyzed. The good performance of the algorithm is shown through computational experiments over random and benchmark instances.     

求图着色问题的新算法

图着色问题是NP-难度的问题。基于两种传统的启发式算法，提出了两种新的求解策略，由此给出了求图着色问题的两个新算法。与传统算法相比，其中一个新算法在时间复杂度不变的条件下，解的质量有明显提高；另一个则在时间复杂度稍有增加的前提下，进一步较显著地提高了所得解的质量。     

A memetic algorithm for the Minimum Sum Coloring Problem

Given an undirected graph G, the Minimum Sum Coloring Problem (MSCP) is to find a legal assignment of colors (represented by natural numbers) to each vertex of G such that the total sum of the colors assigned to the vertices is minimized. This paper presents a memetic algorithm for MSCP based on a tabu search procedure with two neighborhoods and a multi-parent crossover operator. Experiments on a set of 77 well-known DIMACS and COLOR 2002–2004 benchmark instances show that the proposed algorithm achieves highly competitive results in comparison with five state-of-the-art algorithms. In particular, the proposed algorithm can improve the best known results for 15 instances.     

Acyclic orientation graph coloring for software-managed memory allocation

This paper presents a novel compiler algorithm,called acyclic orientation graph coloring(AOG coloring),for managing data objects in software-managed memory allocation.The key insight is that softwaremanaged memory allocation could be solved as an interval coloring problem,or equivalently,an acyclic orientation problem.We generalize graph coloring register allocation to interval coloring memory allocation by maintaining an acyclic orientation to the currently colored subgraph.This is achieved with some well-crafted heuristics,including Aggressive Simplify that does not necessarily preserve colorability and Best-Fit Select that assigns intervals(i.e.,colors)to nodes by possibly adjusting the colors already assigned to other nodes earlier.Our algorithm generalizes and subsumes as a special case the classical graph coloring register allocation algorithm without notably increased complexity:it deals with memory allocation while preserving the elegance and practicality of traditional graph coloring register allocation.We have implemented our algorithm and tested it on Appel’s 27921 interference graphs for scalars(augmented with node weights).Our algorithm outperforms Memory Coloring,the best in the literature,for software-managed memory allocation,on 98.64%graphs,in which,the gaps are more than 20%on 68.31%graphs and worse only on 0.29%graphs.We also tested it on all the 73 DIMACS weighted benchmarks(weighted graphs),AOG Coloring outperforms Memory Coloring on all of the benchmarks,in which,the gaps are more than 20%on 83.56%graphs.     

反馈集问题的研究进展

反馈集问题是经典的NP难问题,在电路测试、操作系统解死锁、分析工艺流程、生物计算等领域都有重要应用,按照反馈集中元素类型可分为反馈顶点集(FVS)问题和反馈边集(FAS)问题。人们利用线性规划和局部搜索等技术设计了一系列关于FVS和FAS问题的近似算法,并基于分枝一剪枝策略和加权分治技术提出了FVS问题的精确算法。随着参数计算理论的发展,近年来参数化反馈集问题引起了人们的重视,并取得了很大突破。目前已经证明了无向图和有向图中FVS问题和FAS问题都是固定参数可解的(FPT)。利用树分解、分支搜索、迭代压缩等技术,对无向图FVS问题提出了一系列FPT算法。针对某些特殊的应用,人们开展了对具有特殊性质的图上FVS问题的研究,提出了一些多项式时间可解的精确算法。现首先介绍了在无向图中关于FVS问题的近似算法与精确算法,然后具体分析了FVS问题的参数化算法。进一步阐述了关于有向图和特殊图上FVS问题的研究现状,介绍了FAS问题的研究成果。基于对反馈集问题研究现状的分析,提出了今后FVS问题研究中值得关注的几个方面。     

基于最小点覆盖及多参数方法的关键蛋白识别

针对已有方法对关键蛋白识别度不高的现状,认为进一步提高识别度有两条途径：一是发现与关键蛋白关系更密切的参数,二是充分挖掘现有参数的信息并进行有效地整合。由于点覆盖在网络（图）拓扑结构上的重要地位而研究将其引入关键蛋白质的识别中：针对算法的复杂性引进参数计算的相关算法将复杂度大幅度降低的同时对蛋白质网络进行最小点覆盖分析并获得一种新的拓扑参数-点覆盖参数,相关分析表明该参数与关键蛋白有着密切的联系。进一步研究发现,参数之间相关性的大小在很大程度上预示它们所蕴含的关键蛋白信息之间互补性的强弱,根据这一发现探讨利用包括点覆盖在内的各个参数的有限信息进行有效整合,仿真结果证实该方法能明显提高关键蛋白识别度。     

密钥覆盖问题的建模、变换及近似算法

组密钥管理是组安全、多播安全中的核心问题.本文给出了密钥覆盖问题模型的建立过程,首次给出密钥覆盖问题（KCP）与顶点覆盖问题（VCP）的相互变换.基于从VCP到KCP的变换,证明了密钥覆盖问题是NP完全的;基于从KCP到VCP的变换,基于VCP的算法为KCP设计了一类近似算法并给出了模拟试验.本文的结果为组安全、多播安全研究提供了更为坚实的算法基础.     

An exact algorithm with learning for the graph coloring problem

Given an undirected graph G=(V,E), the Graph Coloring Problem (GCP) consists in assigning a color to each vertex of the graph G in such a way that any two adjacent vertices are assigned different colors, and the number of different colors used is minimized. State-of-the-art algorithms generally deal with the explicit constraints in GCP: any two adjacent vertices should be assigned different colors, but do not specially deal with the implicit constraints between non-adjacent vertices implied by the explicit constraints. In this paper, we propose an exact algorithm with learning for GCP which exploits the implicit constraints using propositional logic. Our algorithm is compared with several exact algorithms among the best in the literature. The experimental results show that our algorithm outperforms other algorithms on many instances. Specifically, our algorithm allows to close the open DIMACS instance 4-Fullins_5.     

– Ant System

Ant System, the first Ant Colony Optimization algorithm, showed to be a viable method for attacking hard combinatorial optimization problems. Yet, its performance, when compared to more fine-tuned algorithms, was rather poor for large instances of traditional benchmark problems like the Traveling Salesman Problem. To show that Ant Colony Optimization algorithms could be good alternatives to existing algorithms for hard combinatorial optimization problems, recent research in this area has mainly focused on the development of algorithmic variants which achieve better performance than Ant System.In this paper, we present – Ant System ( ), an Ant Colony Optimization algorithm derived from Ant System. differs from Ant System in several important aspects, whose usefulness we demonstrate by means of an experimental study. Additionally, we relate one of the characteristics specific to — that of using a greedier search than Ant System — to results from the search space analysis of the combinatorial optimization problems attacked in this paper. Our computational results on the Traveling Salesman Problem and the Quadratic Assignment Problem show that is currently among the best performing algorithms for these problems.     

A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops

Obtaining an optimal solution for a permutation flowshop scheduling problem with the total flowtime criterion in a reasonable computational timeframe using traditional approaches and optimization tools has been a challenge. This paper presents a discrete artificial bee colony algorithm hybridized with a variant of iterated greedy algorithms to find the permutation that gives the smallest total flowtime. Iterated greedy algorithms are comprised of local search procedures based on insertion and swap neighborhood structures. In the same context, we also consider a discrete differential evolution algorithm from our previous work. The performance of the proposed algorithms is tested on the well-known benchmark suite of Taillard. The highly effective performance of the discrete artificial bee colony and hybrid differential evolution algorithms is compared against the best performing algorithms from the existing literature in terms of both solution quality and CPU times. Ultimately, 44 out of the 90 best known solutions provided very recently by the best performing estimation of distribution and genetic local search algorithms are further improved by the proposed algorithms with short-term searches. The solutions known to be the best to date are reported for the benchmark suite of Taillard with long-term searches, as well.     

Variable neighborhood search for the Vertex Separation Problem

The Vertex Separation Problem belongs to a family of optimization problems in which the objective is to find the best separator of vertices or edges in a generic graph. This optimization problem is strongly related to other well-known graph problems; such as the Path-Width, the Node Search Number or the Interval Thickness, among others. All of these optimization problems are NP-hard and have practical applications in VLSI (Very Large Scale Integration), computer language compiler design or graph drawing. Up to know, they have been generally tackled with exact approaches, presenting polynomial-time algorithms to obtain the optimal solution for specific types of graphs. However, in spite of their practical applications, these problems have been ignored from a heuristic perspective, as far as we know. In this paper we propose a pure 0-1 optimization model and a metaheuristic algorithm based on the variable neighborhood search methodology for the Vertex Separation Problem on general graphs. Computational results show that small instances can be optimally solved with this optimization model and the proposed metaheuristic is able to find high-quality solutions with a moderate computing time for large-scale instances.     

图着色算法解决考试时间安排问题的优化

时间表问题是将有限的时间资源分配给多个对象的资源分配问题,它是一类具有多约束条件的组合优化问题。时间表问题已经被证明是一个NP完全问题。大学考试时间安排问题是时间表问题的一个应用,利用改进的图着色算法来处理大学考试的时间安排问题能够最大程度上使考试时间安排得更加人性化、合理化。实验测试表明,基于所给出的算法实现的考试时间安排系统具有良好的可行性、实用性和优越性。     

Constructive heuristics for the Mixed Capacity Arc Routing Problem under Time Restrictions with Intermediate Facilities

The Mixed Capacity Arc Routing Problem under Time Restrictions with Intermediate Facilities (MCARPTIF) is an extension of the Arc Routing Problem under Capacity and Length Restrictions with Intermediate Facilities (CLARPIF) with application in municipal waste collection. This paper evaluates four constructive heuristics capable of computing feasible solutions for the MCARPTIF with a primary objective to either minimise total cost or to minimise the fleet size. The heuristics were adapted from Path-Scanning and Improved-Merge for the Mixed Capacitated Arc Routing Problem, and compared against two Route-First-Cluster-Second heuristics for the MCARPTIF. The objective was to identify the best performing heuristic for application purposes. In practice, the CARP is often solved for real-time or near real-time decision support. Computational time required by the heuristics was thus also evaluated. Identifying the best heuristic proved difficult due to a lack of realistic MCARPTIF benchmark sets, with the two CLARPIF sets predominantly solved in the literature not resembling actual waste collection instances. Route-First-Cluster-Second heuristics, linked with a new vehicle reduction heuristic performed the worst on the two CLARPIF sets, yet performed the best on new waste collection sets taken from the literature and introduced in this paper. Improved-Merge performed the best on two existing CLARPIF sets and on a realistic set with Intermediate-Facilities incident with the vehicle depot, but struggled on all other sets and in minimising fleet size. Path-Scanning was the most robust heuristic, performing reasonably well on all benchmark sets and both objectives. Results further show that due to the high computational time of one of the Route-First-Cluster-Second heuristics, which was only exposed on realistically sized sets, the slightly worse version is the best alternative when real-time support is required for waste collection applications.     

Linear time self-stabilizing colorings

We propose two new self-stabilizing distributed algorithms for proper Δ+1 (Δ is the maximum degree of a node in the graph) colorings of arbitrary system graphs. Both algorithms are capable of working with multiple type of daemons (schedulers) as is the most recent algorithm by Gradinariu and Tixeuil [OPODIS'2000, 2000, pp. 55-70]. The first algorithm converges in O(m) moves while the second converges in at most n moves (n is the number of nodes and m is the number of edges in the graph) as opposed to the O(Δ×n) moves required by the algorithm by Gradinariu and Tixeuil [OPODIS'2000, 2000, pp. 55-70]. The second improvement is that neither of the proposed algorithms requires each node to have knowledge of Δ, as is required by Gradinariu and Tixeuil [OPODIS'2000, 2000, pp. 55-70]. Further, the coloring produced by our first algorithm provides an interesting type of coloring, called a Grundy Coloring [Jensen and Toft, Graph Coloring Problems, 1995].     

Exponential Separation of Quantum and Classical Online Space Complexity

Although quantum algorithms realizing an exponential time speed-up over the best known classical algorithms exist, no quantum algorithm is known performing computation using less space resources than classical algorithms. In this paper, we study, for the first time explicitly, space-bounded quantum algorithms for computational problems where the input is given not as a whole, but bit by bit. We show that there exist such problems that a quantum computer can solve using exponentially less work space than a classical computer. More precisely, we introduce a very natural and simple model of a space-bounded quantum online machine and prove an exponential separation of classical and quantum online space complexity, in the bounded-error setting and for a total language. The language we consider is inspired by a communication problem (the disjointness function) that Buhrman, Cleve and Wigderson used to show an almost quadratic separation of quantum and classical bounded-error communication complexity. We prove that, in the framework of online space complexity, the separation becomes exponential.     

Hybrid teaching–learning-based optimization algorithms for the Quadratic Assignment Problem

Teaching–Learning-Based Optimization (TLBO) is a novel swarm intelligence metaheuristic that is reported as an efficient solution method for many optimization problems. It consists of two phases where all individuals are trained by a teacher in the first phase and interact with classmates to improve their knowledge level in the second phase. In this study, we propose a set of TLBO-based hybrid algorithms to solve the challenging combinatorial optimization problem, Quadratic Assignment. Individuals are trained with recombination operators and later a Robust Tabu Search engine processes them. The performances of sequential and parallel TLBO-based hybrid algorithms are compared with those of state-of-the-art metaheuristics in terms of the best solution and computational effort. It is shown experimentally that the performance of the proposed algorithms are competitive with the best reported algorithms for the solution of the Quadratic Assignment Problem with which many real life problems can be modeled.     

Experimental Analysis of Approximation Algorithms for the Vertex Cover and Set Covering Problems

Several approximation algorithms with proven performance guarantees have been proposed to find approximate solutions to classical combinatorial optimization problems. However, theoretical results may not reflect the experimental performance of the proposed algorithms. As a consequence, a question arises: how “far” from the theoretically proved performance are the experimental results? We conduct a controlled empirical study of approximation algorithms for the Vertex Cover and the Set Covering Problems. Many authors have proposed approximation algorithms for those problems. Our main goal is to better understand their strengths, weaknesses, and operation. Although we implement more than one algorithm to find feasible solutions to either problems, this work does not emphasize competition between them. The quality of the solutions related to the theoretical performance guarantees are analyzed instead. The computational experiments showed that the proven performance guarantees of all tested algorithms did not forecast well the empirical performance.     

一种基于加减法求交和顶点类型的凹多边形水平扫描填色算法

本文给出了一种只有加减运算就能求大平线线与凹多边形边界交点的方法,并根据顶点类型定义,将凹多边形顶点分成“水平顶点”、“极占”、“拐点”三类。设计了基于三类顶点的边界存储结构;建立了凹多边形水平扫描填色算法,解决了当交为顶点时可能产生的“交点对”不配对的问题。