基于最小代价和生成树的算法研究

最小生成树问题是一类经典的组合优化问题,已有许多快速有效的算法。但是在实际中更多存在这样的网络,除边有权值外,结点也有权值,并且结点的权值有多种情况,这就产生了基于代价和最小的生成树问题。根据结点权值的取值情况,对几种最小代价和生成树问题进行分类和求解,得到了一些有价值的性质和算法,有一定的实际应用背景。     

A bounded approximation for the minimum cost 2-sat problem

Given a satisfiable Boolean formula in 2-CNF, it is NP-hard to find a satisfying assignment that contains a minimum number of true variables. A polynomial-time approximation algorithm is given that finds an assignment with at most twice as many true variables as necessary. The algorithm also works for a weighted generalization of the problem. An application to the optimal stable roommates problem is given in detail, and other applications are mentioned.D. Gusfield was supported in part by NSF Grant CCR-8803704. Part of this work was done while he was at Yale University, partially supported by NSF Grant MCS-8105894. L. Pitt was supported in part by NSF Grant IRI-8809570. Part of this work was done while he was at Yale University, supported by NSF Grants MCS-8002447, MCS-8116678, and MCS-8204246.     

Minimum Weakly Fundamental Cycle Bases Are Hard To Find

In the last years, new variants of the minimum cycle basis (MCB) problem and new classes of cycle bases have been introduced, as motivated by several applications from disparate areas of scientific and technological inquiry. At present, the complexity status of the MCB problem is settled only for undirected, directed, and strictly fundamental cycle bases (SFCB’s). Weakly fundamental cycle bases (WFCB’s) form a natural superclass of SFCB’s. A cycle basis of a graph G is a WFCB iff ν=0 or there exists an edge e of G and a circuit C _i in such that is a WFCB of G∖e. WFCB’s still possess several of the nice properties offered by SFCB’s. At the same time, several classes of graphs enjoying WFCB’s of cost asymptotically inferior to the cost of the cheapest SFCB’s have been found and exhibited in the literature. Considered also the computational difficulty of finding cheap SFCB’s, these works advocated an in-depth study of WFCB’s. In this paper, we settle the complexity status of the MCB problem for WFCB’s (the MWFCB problem). The problem turns out to be -hard. However, in this paper, we also offer a simple and practical 2⌈log ₂ n⌉-approximation algorithm for the MWFCB problem. In O(n ν) time, this algorithm actually returns a WFCB whose cost is at most 2⌈log ₂ n⌉∑ _e∈E(G) w _e , thus allowing a fast 2⌈log ₂ n⌉-approximation also for the MCB problem. With this algorithm, we provide tight bounds on the cost of any MCB and MWFCB.     

Approximations for Maximum Transportation with Permutable Supply Vector and Other Capacitated Star Packing Problems

We describe approximation algorithms for the maximum transportation with permutable supply vector and related problems.     

On Constrained Facility Location Problems

Given m facilities each with an opening cost, n demands, and distance between every demand and facility, the Facility Location problem finds a solution which opens some facilities to connect every demand to an opened facility such that the total cost of the solution is minimized. The k-Facility Location problem further requires that the number of opened facilities is at most k, where k is a parameter given in the instance of the problem. We consider the Facility Location problems satisfying that for every demand the ratio of the longest distance to facilities and the shortest distance to facilities is at most ω, where ω is a predefined constant. Using the local search approach with scaling technique and error control technique, for any arbitrarily small constant > 0, we give a polynomial-time approximation algorithm for the ω-constrained Facility Location problem with approximation ratio 1 + ω + 1 + ε, which significantly improves the previous best known ratio (ω + 1)/α for some 1≤α≤2, and a polynomial-time approximation algorithm for the ω-constrained k- Facility Location problem with approximation ratio ω+1+ε. On the aspect of approximation hardness, we prove that unless NP■DTIME(nO(loglogn)), the ω-constrained Facility Location problem cannot be approximated within 1 + lnω - 1, which slightly improves the previous best known hardness result 1.243 + 0.316ln(ω - 1). The experimental results on the standard test instances of Facility Location problem show that our algorithm also has good performance in practice.     

Minimum cost source location problem with local 3-vertex-connectivity requirements

Let G=(V,E)$G=(V,E)$ be a simple undirected graph with a set V$V$ of vertices and a set E$E$ of edges. Each vertex v∈V$v\in V$ has a demand d(v)∈_Z+$d\left(v\right)\in Z_{+}$ and a cost c(v)∈_R+$c\left(v\right)\in R_{+}$, where _Z+$Z_{+}$ and _R+$R_{+}$ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph G$G$ requires finding a set S$S$ of vertices minimizing _∑v∈Sc(v)${\sum }_{v\in S}c\left(v\right)$ such that there are at least d(v)$d\left(v\right)$ pairwise vertex-disjoint paths from S$S$ to v$v$ for each vertex v∈V−S$v\in V-S$. It is known that if there exists a vertex v∈V$v\in V$ with d(v)≥4$d\left(v\right)\ge 4$, then the problem is NP-hard even in the case where every vertex has a uniform cost. In this paper, we show that the problem can be solved in O(|V|⁴log²|V|)$O\left({\left|V\right|}^4{log}^2\left|V\right|\right)$ time if d(v)≤3$d\left(v\right)\le 3$ holds for each vertex v∈V$v\in V$.     

Parallel VNS for Bus Terminal Location Problem

This paper considers the Bus Terminal Location Problem (BTLP) which incorporates characteristics of both the p-median and maximal covering problems. We propose a parallel variable neighborhood search algorithm (PVNS) for solving BTLP. Improved local search, based on efficient neighborhood interchange, is used for the p-median problem, and is combined with a reduced neighborhood size for the maximal covering part of the problem. The proposed parallel algorithm is compared with its non-parallel version. Parallelization yielded significant time improvement in function of the processor core count. Computational results show that PVNS improves all existing results from the literature, while using significantly less time. New larger instances, based on rl instances from the TSP library, are introduced and computational results for those new instances are reported.     

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.     

Approximating Maximum Weight Cycle Covers in Directed Graphs with Weights Zero and One

A cycle cover of a graph is a spanning subgraph, each node of which is part of exactly one simple cycle. A k-cycle cover is a cycle cover where each cycle has length at least k. Given a complete directed graph with edge weights zero and one, Max-k-DDC(0,1) is the problem of finding a k-cycle cover with maximum weight. We present a 2/3 approximation algorithm for Max-k-DDC(0,1) with running time O(n ^5/2). This algorithm yields a 4/3 approximation algorithm for Max-k-DDC(1,2) as well. Instances of the latter problem are complete directed graphs with edge weights one and two. The goal is to find a k-cycle cover with minimum weight. We particularly obtain a 2/3 approximation algorithm for the asymmetric maximum traveling salesman problem with distances zero and one and a 4/3 approximation algorithm for the asymmetric minimum traveling salesman problem with distances one and two. As a lower bound, we prove that Max-k-DDC(0,1) for k 3 and Max-k-UCC(0,1) (finding maximum weight cycle covers in undirected graphs) for k 7 are \APX-complete.     

一种基于改进堆优化Dijkstra算法的最小费用最大流算法

通过最短路径算法在残存网络中搜索汇点的最小费用路径是流网络中求解最小费用最大流的主要方式,而Dijkstra算法是最高效的最短路径算法之一。本文通过证明残存网络中不存在负循环,采用改进的堆优化Dijkstra算法在残存网络中搜索最小费用路径以提升算法的效率。实验结果表明,与经典的基于最短路径快速算法的最小费用最大流算法和基于Bellman-Ford算法的最小费用最大流算法对比,本文提出的改进算法具有更高的时间效率。     

基于设施选址的Steiner问题的算法

在设施选址问题的基础上给出了广义Steiner树-星问题的两个近似比分别为3．55和3．582的近似算法,并在问题转化的基础上研究了其他若干特殊情形的Steiner树问题的近似算法。     

基于佳点集遗传算法的Flow Shop调度问题求解

利用数论中的佳点集理论和方法,结合传统的遗传算法来求解flow shop问题。算法的应用结果显示了该方法求解问题的较好性能,大大地改善了SGA的求解质量。     

An Approximation Algorithm for a Large-Scale Facility Location Problem

We developed a new practical optimization method that gives approximate solutions for large-scale real instances of the Uncapacitated Facility Location Problem. The optimization consists of two steps: application of the Greedy—Interchange heuristic using a small subset of warehouse candidates, and application of the newly developed heuristic named Balloon Search that takes account of all warehouse candidates, and runs in ( O (3n + 2n log n ) ) expected time (n is the number of nodes of the underlying graph). Our experiments on the spare parts logistics of a Japanese manufacturing company with 6000 customers and 380,000 warehouse candidates led us to conclude that the Greedy heuristic improved the total cost by 9%-11%, that the Interchange heuristic improved the total cost by an additional 0.5%—1.5%, and that Balloon Search improved it by a further 0.5%—1.5%.     

Drawing Borders Efficiently

A spreadsheet, especially MS Excel, is probably one of the most popular software applications for personal-computer users and gives us convenient and user-friendly tools for drawing tables. Using spreadsheets, we often wish to draw several vertical and horizontal black lines on selective gridlines to enhance the readability of our spreadsheet. Such situations we frequently encounter are formulated as the Border Drawing Problem (BDP). Given a layout of black line segments, we study how to draw it efficiently from an algorithmic view point, by using a set of border styles and investigate its complexity. (i) We first define a formal model based on MS Excel, under which the drawability and the efficiency of border styles are discussed, and then (ii) show that unfortunately the problem is -hard for the set of the Excel border styles and for any reasonable subset of the styles. Moreover, in order to provide potentially more efficient drawing, (iii) we propose a new compact set of border styles and show a necessary and sufficient condition of its drawability.     

基于最小费用最大流的大规模资源调度方法

并行作业是大规模资源调度的研究热点.已有研究工作通常采用队列进行资源调度建模,仅能满足局部最优解,只能适应调度目标固定不变的场景,灵活性不够.提出了一种基于最小费用最大流的大规模资源调度建模方法,将任务的资源需求和物理资源供给问题转换成最小费用最大流图的构造和求解问题.首先,选择公平性、优先级和放置约束三种典型度量作为切入点,从资源视角映射为图的构造问题,通过改变图的结构使其具备适应性调整能力.其次,针对图的求解时间复杂度高的问题,实现了一种增量式优化算法.最后,实验对比公平性、优先级和放置约束三种资源调度典型系统,验证了本方法可通过按需配置,支持多种调度目标,具备灵活性.并通过实验仿真验证了万级规模下基于图的资源调度延迟,比基于未优化图算法的资源调度延迟最多降低10倍.     

Approximation Algorithms for Multi-Criteria Traveling Salesman Problems

We analyze approximation algorithms for several variants of the traveling salesman problem with multiple objective functions. First, we consider the symmetric TSP (STSP) with γ-triangle inequality. For this problem, we present a deterministic polynomial-time algorithm that achieves an approximation ratio of and a randomized approximation algorithm that achieves a ratio of . In particular, we obtain a 2+ε approximation for multi-criteria metric STSP. Then we show that multi-criteria cycle cover problems admit fully polynomial-time randomized approximation schemes. Based on these schemes, we present randomized approximation algorithms for STSP with γ-triangle inequality (ratio ), asymmetric TSP (ATSP) with γ-triangle inequality (ratio ), STSP with weights one and two (ratio 4/3) and ATSP with weights one and two (ratio 3/2). A preliminary version of this work has been presented at the 4th Workshop on Approximation and Online Algorithms (WAOA 2006) (Lecture Notes in Computer Science, vol. 4368, pp. 302–315, 2007). B. Manthey is supported by the Postdoc-Program of the German Academic Exchange Service (DAAD). He is on leave from Saarland University and has done part of the work at the Institute for Theoretical Computer Science of the University of Lübeck supported by DFG research grant RE 672/3 and at the Department of Computer Science at Saarland University.     

Notes on inverse bin-packing problems

In bin-packing problems, given items need to be packed using a minimum number of bins. Inverse bin-packing number problems, IBPN for short, assume a given set of items and number of bins. The objective is to achieve the minimum perturbation to the item-size vector so that all the items can be packed into the prescribed number of bins. In this paper, complexity status and approximation behavior for IBPN were investigated. Under the _Lp$L_p$-norm, ∀p∈{1,2,…,∞}$\forall p\in \{1,2,\dots ,\infty \}$, IBPN turns out to be NP-hard in the strong sense. IBPN under the _L1$L_1$-norm admits a polynomial time differential approximation scheme, and a fully polynomial time approximation scheme if a constant number of machines is provided as input. We also consider another IBPN variant where a specified feasible solution is given instead of a target bin number. The objective is to make the given solution optimal with minimum modification. We provide the hardness result for this problem.     

废弃物处理站选址问题的和谐搜索算法

近年来,随着人们环保意识的增强和环保法规力度的加大,逆向物流逐渐受到人们的关注与重视。废弃物处理站的选址问题(end-of-life items disposal facilities' location prohlem, EIDFI_P)是逆向物流研究领域的关键问题,该问题能否有效解决直接关系到人们的日常生活环境能否得到有效改善。针对文献中的具有多个目标的EIDFLP,首先将问题转化为单目标问题,之后采用一种新颖的和谐搜索优化算法(harmony search algorithm, HSA)对问题进行了求解。计算结果显示:1)本算法的最优解与文献中的最优解相同;2)本算法的计算时间明显少于文献中算法的计算时间;3)原文献中的一个解存在错误之处。