检索结果-内蒙古大学图书馆

On the approximation ability of evolutionary optimization with application to minimum set cover

ARTIFICIAL INTELLIGENCE 2012年 180卷 20-33页

作者： Yu, Yang Yao, Xin Zhou, Zhi-Hua Nanjing Univ Natl Key Lab Novel Software Technol Nanjing 210093 Jiangsu Peoples R China Univ Birmingham Sch Comp Sci Ctr Excellence Res Computat Intelligence & Applic Birmingham B15 2TT W Midlands England

Evolutionary algorithms (EAs) are heuristic algorithms inspired by natural evolution. They are often used to obtain satisficing solutions in practice. In this paper, we investigate a largely underexplored issue: the approximation performance of EAs in terms of how close the solution obtained is to an optimal solution. We study an EA framework named simple EA with isolated population (SEIP) that can be implemented as a single- or multi-objective EA. We analyze the approximation performance of SEIP using the partial ratio, which characterizes the approximation ratio that can be guaranteed. Specifically, we analyze SEIP using a set cover problem that is NP-hard. We find that in a simple configuration, SEIP efficiently achieves an H-n-approximation ratio, the asymptotic lower bound, for the unbounded set cover problem. We also find that SEIP efficiently achieves an (H-k - k-1/8k(9))- approximation ratio, the currently best-achievable result, for the k-set cover problem. Moreover, for an instance class of the k-set cover problem, we disclose how SEIP, using either one-bit or bit-wise mutation, can overcome the difficulty that limits the greedy algorithm. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Evolutionary algorithms approximation algorithm approximation ratio k-Set cover Time complexity analysis

来源：评论

学校读者我要写书评

暂无评论

An improved approximation algorithm for capacitated multicast routings in networks

引用

THEORETICAL COMPUTER SCIENCE 2008年第1期390卷 81-91页

作者： Morsy, Ehab Nagamochi, Hiroshi Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan

Let G = (V, E) be a connected graph such that each edge e is an element of E is weighted by nonnegative real w(e). Let s be a vertex designated as a source, k be a positive integer, and S subset of V be a set of terminals. The capacitated multicast tree routing problem (CMTR) asks to find a partition {Z(1), Z(2), . . . , Z(l)} of S and a set {T-1, T-2, . . . , T-l} of trees of G such that Z(i) consists of at most k terminals and each Ti spans Z(i) boolean OR {s}. The objective is to minimize Sigma(l)(i=1) w(T-i), where w(T-i) denotes the sum of weights of all edges in T-i. In this paper, we propose a (3/2 + (4/3)rho)-approximation algorithm to the CMTR, where rho is the best achievable approximation ratio for the Steiner tree problem. (C) 2007 Elsevier B.V. All rights reserved.

关键词： approximation algorithm graph algorithm multicast routing problem network optimization tree cover

来源：评论

学校读者我要写书评

暂无评论

On New Approaches of Assessing Network Vulnerability: Hardness and approximation

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2012年第2期20卷 609-619页

作者： Dinh, Thang N. Xuan, Ying Thai, My T. Pardalos, Panos M. Znati, Taieb Univ Florida Dept Comp & Informat Sci & Engn Gainesville FL 32611 USA Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA Univ Pittsburgh Dept Comp Sci Pittsburgh PA 15215 USA

Society relies heavily on its networked physical infrastructure and information systems. Accurately assessing the vulnerability of these systems against disruptive events is vital for planning and risk management. Existing approaches to vulnerability assessments of large-scale systems mainly focus on investigating inhomogeneous properties of the underlying graph elements. These measures and the associated heuristic solutions are limited in evaluating the vulnerability of large-scale network topologies. Furthermore, these approaches often fail to provide performance guarantees of the proposed solutions. In this paper, we propose a vulnerability measure, pairwise connectivity, and use it to formulate network vulnerability assessment as a graph-theoretical optimization problem, referred to as beta-disruptor. The objective is to identify the minimum set of critical network elements, namely nodes and edges, whose removal results in a specific degradation of the network global pairwise connectivity. We prove the NP-completeness and inapproximability of this problem and propose an O(log n log log n) pseudo-approximation algorithm to computing the set of critical nodes and an O(log(1.5) n) pseudo-approximation algorithm for computing the set of critical edges. The results of an extensive simulation-based experiment show the feasibility of our proposed vulnerability assessment framework and the efficiency of the proposed approximation algorithms in comparison to other approaches.

关键词： approximation algorithm hardness network vulnerability pairwise connectivity

来源：评论

学校读者我要写书评

暂无评论

Absolute approximation ratios for packing rectangles into bins

引用

JOURNAL OF SCHEDULING 2012年第1期15卷 63-75页

作者： Harren, Rolf van Stee, Rob Max Planck Inst Comp Sci MPII D-66123 Saarbrucken Germany

We consider the problem of packing rectangles into bins that are unit squares, where the goal is to minimize the number of bins used. All rectangles have to be packed non-overlapping and orthogonal, i. e., axis-parallel. We present an algorithm with an absolute worst-case ratio of 2 for the case where the rectangles can be rotated by 90 degrees. This is optimal provided P not equal NP. For the case where rotation is not allowed, we prove an approximation ratio of 3 for the algorithm HYBRID FIRST FIT which was introduced by Chung et al. (SIAM J. Algebr. DiscreteMethods 3(1): 6676, 1982) and whose running time is slightly better than the running time of Zhang's previously known 3-approximation algorithm (Zhang in Oper. Res. Lett. 33(2): 121-126, 2005).

关键词： Bin packing Rectangle packing approximation algorithm Absolute worst-case ratio

来源：评论

学校读者我要写书评

暂无评论

A faster, better approximation algorithm for the minimum latency problem

引用

SIAM JOURNAL ON COMPUTING 2008年第5期37卷 1472-1498页

作者： Archer, Aaron Levin, Asaf Williamson, David P. AT&T Shannon Res Lab Algorithms & Optimizat Dept Florham Pk NJ 07932 USA Hebrew Univ Jerusalem Dept Stat IL-91905 Jerusalem Israel Cornell Univ Sch Operat Res & Ind Engn Ithaca NY 14853 USA

We give a 7.18-approximation algorithm for the minimum latency problem that uses only O(n log n) calls to the prize-collecting Steiner tree (PCST) subroutine of Goemans and Williamson. This improves the previous best algorithms in both performance guarantee and running time. A previous algorithm of Goemans and Kleinberg for the minimum latency problem requires an approximation algorithm for the k-minimum spanning tree (k-MST) problem which is called as a black box for each value of k. Their algorithm can achieve an approximation factor of 10.77 while making O(n(n + log C) log n) PCST calls, a factor of 8.98 using O(n(3)(n + log C) log n) PCST calls, or a factor of 7.18 + epsilon using n(O(1/epsilon)) log C PCST calls, via the k-MST algorithms of Garg, Arya and Ramesh, and Arora and Karakostas, respectively. Here n denotes the number of nodes in the instance, and C is the largest edge cost in the input. In all cases, the running time is dominated by the PCST calls. Since the PCST subroutine can be implemented to run in O(n(2)) time, the overall running time of our algorithm is O(n3 log n). We also give a faster randomized version of our algorithm that achieves the same approximation guarantee in expectation, but uses only O(log(2) n) PCST calls, and derandomize it to obtain a deterministic algorithm with factor 7.18 + epsilon, using O(1/epsilon log(2) n) PCST calls. The basic idea for our improvement is that we do not treat the k-MST algorithm as a black box. This allows us to take advantage of some special situations in which the PCST subroutine delivers a 2-approximate k-MST. We are able to obtain the same approximation ratio that would be given by Goemans and Kleinberg if we had access to 2-approximate k-MSTs for all values of k, even though we have them only for some values of k that we are not able to specify in advance. We also extend our algorithm to a weighted version of the minimum latency problem.

关键词： minimum latency problem traveling repairman approximation algorithm Lagrangian relaxation prize-collecting Steiner tree

来源：评论

学校读者我要写书评

暂无评论

Tight approximation algorithm for connectivity augmentation problems

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2008年第5期74卷 662-670页

作者： Kortsarz, Guy Nutov, Zeev Rutgers State Univ Camden NJ 08102 USA Open Univ Raanana Israel

The S-connectivity lambda(S)(G)(u,nu) of (u,nu)in a graph G is the maximum number of uv-paths that no two of them have an edge or a node in S - {u, nu} in common. The corresponding Connectivity Augmentation (CA) problem is: given a graph G(0) = (V, E-0), S subset of V, and requirements r(u, nu) on V x V, find a minimum size set F of new edges (any edge is allowed) so that lambda(S)(G0+F)(u, nu) >= r(u, nu) for all u,nu is an element of V. Extensively studied particular choices of S are the edge-CA (when S = phi) and the node-CA (when S = V). A. Frank gave a polynomial algorithm for undirected edge-CA and observed that the directed case even with rooted {0, 1}-requirements is at least as hard as the Set-Cover problem (in rooted requirements there is s is an element of V - S so that if r(u, v) > 0 then: u = s for directed graphs, and u = s or nu = s for undirected graphs). Both directed and undirected node-CA have approximation threshold Omega(2log(1-epsilon) n). The only polylogarithmic approximation ratio known for CA was for rooted requirements-O(logn . logr(max)) = O(log(2)n), where r(max) = max(u,nu is an element of V) r(u, nu). No nontrivial approximation algorithms were known fordirected CA even forr(u, nu) is an element of {0, 1}, nor for undirected CA with S arbitrary. We give an approximation algorithm for the general case that matches the known approximation thresholds. For both directed and undirected CA with arbitrary requirements our approximation ratio is: O(logn) for S not equal V arbitrary, and O(r(max) . log n) for S = V. (c) 2007 Published by Elsevier Inc.

关键词： connectivity augmentation approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion

引用

OPERATIONS RESEARCH LETTERS 2008年第3期36卷 343-344页

作者： Kasperski, Adam Zielinski, Pawel Wroclaw Univ Technol Inst Ind Engn & Management PL-50370 Wroclaw Poland Wroclaw Univ Technol Inst Math & Comp Sci PL-50370 Wroclaw Poland

In this paper we discuss a minmax regret version of the single-machine scheduling problem with the total flow time criterion. Uncertain processing times are modeled by closed intervals. We show that if the deterministic problem is polynomially solvable, then its minmax regret version is approximable within 2. (C) 2007 Elsevier B.V. All rights reserved.

关键词： scheduling interval data minmax regret approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Python-based Optimization Model and algorithm for Rescue Routes During Gas Leak Emergencies

Python-based Optimization Model and Algorithm for Rescue Rou...

引用

第三十二届中国控制会议

作者： Wen-mei GAI Yun-feng DENG Jing LI Yan DU School of Civil and Environmental Engineering University of Science and Technology Beijing Chinese Academy of Governance Institute of Public Safety China Academy of science and Technology School of Civil and Environmental Engineering University of Science and Technology Beijing

ISBN: (纸本)9781479900305

Based on the theories and methods of operations research,a mathematical model for the short est rescue route during gas leak emergencies in high-sulfur oil and gas fields is built in this pap er,which contains two weights of rescue rout e optimization,and serves the bi-objective optimization *** approximate search algorithm with two optimization objectives is proposed for the model based on heuristic algorithm,which could find out the shortest escape route from the double-weight escape route network by construct ing anxiliary *** the study case of the gas leak emergency rescue system of the Puguang gas field in Sichnan,the algorithm procedures are introduced,the convergence rate of the algorithm are analyzed,and the time complexity and the strengths of the algorithm are *** this algorithm,decision makers can find out the optimum rescue route on the distribution sketch map of the Puguang gas field,thus realizing the two optimizing targets,and providing strong technical support for gas leak rescue in the gas field.

关键词： Gas leak bi-objective optimization relief route approximation algorithm mathematical model Python major accidents emergency rescue

来源：评论

学校读者我要写书评

暂无评论

HEURISTICS FOR THE TRANSPOSITION DISTANCE PROBLEM

引用

JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY 2013年第5期11卷 1350013页

作者： Dias, Ulisses Dias, Zanoni Univ Estadual Campinas Inst Comp BR-13083852 Campinas SP Brazil

Transpositions are large-scale mutational events that occur when a block of genes moves from a region of a chromosome to another region within the same chromosome. The transposition distance problem is the minimum number of transpositions required to transform one genome into another. Recently, Bulteau et al. [Bulteau L, Fertin G, Rusu U, Automata, Languages and Programming, Vol. 6755 of Lecture Notes in Computer Science, pp. 654-665, Springer Berlin, Heidelberg, 2011] proved that finding the transposition distance is a NP-Hard problem. Some approximation algorithm for this problem have been presented to date [Bafna V, Pevzner PA, SIAM J Discr Math 11(2): 224-240, 1998;Elias I, Hartman T, IEEE/ACM Trans Comput Biol Bioinform 3(4): 369-379, 2006;Mira CVG, Dias Z, Santos HP, Pinto GA, Walter ME, Proc 3rd Brazilian Symp Bioinformatics (BSB'2008), pp. 115-126, Santo Andre, Brazil, 2008;Walter MEMT, Dias Z, Meidanis J, Proc String Processing and Information Retrieval (SPIRE'2000), pp. 199-208, Coruna, Spain, 2000]. Here we focus on developing heuristics to provide an improved approximated solution. Our approach outperforms other algorithms on small sized permutations. We also show that our algorithm keeps the good performance on longer permutations.

关键词： Genome rearrangement sorting by transposition approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Complex-Demand Knapsack Problems and Incentives in AC Power Systems 13

Complex-Demand Knapsack Problems and Incentives in AC Power ...

引用

International Conference on Autonomous Agents and Multiagent Systems

作者： Lan Yu Chi-Kin Chau Nanyang Technological University Singapore Singapore Masdar Institute of Science and Technology Abu Dhabi Uae

ISBN: (纸本)9781450319935

We consider AC electrical systems where each electrical device has a power demand expressed as a complex number, and there is a limit on the magnitude of total power supply. Motivated by this scenario, we introduce the complex-demand knapsack problem (C-KP), a new variation of the traditional knapsack problem, where each item is associated with a demand as a complex number, rather than a real number often interpreted as weight or size of the item. While keeping the same goal as to maximize the sum of values of the selected items, we put the capacity limit on the magnitude of the sum of satisfied demands. For C-KP, we prove its inapproximability by FPTAS (unless P = NP), as well as presenting a (1/2 - ε)-approximation algorithm. Furthermore, we investigate the selfish multi-agent setting where each agent is in charge of one item, and an agent may misreport the demand and value of his item for his own interest. We show a simple way to adapt our approximation algorithm to be monotone, which is sufficient for the existence of incentive compatible payments such that no agent has an incentive to misreport. Our results shed insight on the design of multi-agent systems for smart grid.

关键词： Knapsack problem approximation algorithm FPTAS Incentive compatibility Truthfulness AC electrical system Smart grid

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：