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

Facility Location with Hierarchical Facility Costs

ACM TRANSACTIONS ON algorithmS 2010年第2期6卷 1–22页

作者： Svitkina, Zoya Tardos, Eva Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Cornell Univ Dept Comp Sci Ithaca NY 14853 USA

We introduce a facility location problem with submodular facility cost functions, and give an O(log n) approximation algorithm for it. Then we focus on a special case of submodular costs, called hierarchical facility costs, and give a (4.237 + epsilon)-approximation algorithm using local search. The hierarchical facility costs model multilevel service installation. Shmoys et al. [ 2004] gave a constant factor approximation algorithm for a two-level version of the problem. Here we consider a multilevel problem, and give a constant factor approximation algorithm, independent of the number of levels, for the case of identical costs on all facilities.

关键词： algorithms Theory approximation algorithm facility location local search sub-modular function

来源：评论

学校读者我要写书评

暂无评论

Convex Optimization algorithms for Cooperative Localization in Autonomous Underwater Vehicles

引用

Acta Automatica Sinica 2010年第5期36卷 704-710页

作者： Ming-Yong LIU Wen-Bai LI Xuan PEI College of Marine Northwestern Polytechnical University Xi an 710072 P. R. China

In this paper, a cooperative localization algorithm for autonomous underwater vehicles (AUVs) is proposed. A “parallel” model is adopted to describe the cooperative localization problem instead of the traditional “leader-follower” model, and a linear programming associated with convex optimization method is used to deal with the problem. After an unknown-but-bounded model for sensor noise is assumed, bearing and range measurements can be modeled as linear constraints on the configuration space of the AUVs. Merging these constraints induces a convex polyhedron representing the set of all configurations consistent with the sensor measurements. Estimates for the uncertainty in the position of a single AUV or the relative positions of two or more nodes can then be obtained by projecting this polyhedron onto appropriate subspaces of the configuration space. Two different optimization algorithms are given to recover the uncertainty region according to the number of the AUVs. Simulation results are presented for a typical localization example of the AUV formation. The results show that our positioning method offers a good localization accuracy, although a small number of low-cost sensors are needed for each vehicle, and this validates that it is an economical and practical positioning approach compared with the traditional approach.

关键词： Autonomous underwater vehicle (AUV) convex optimization cooperative localization uncertainty region screening algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Randomized approximation algorithm for a Geometrical Multidimensional Assignment Problem

引用

Electronic Notes in Discrete Mathematics 2006年 27卷 63-64页

作者： Kuroki, Yusuke Matsui, Tomomi Mathematical Informatics The University of Tokyo Tokyo Japan Information and System Engineering Chuo University Tokyo Japan

来源：评论

学校读者我要写书评

暂无评论

A New Smooth Method for the l1 Exact Penalty Function for Inequality Constrained Optimization

A New Smooth Method for the l1 Exact Penalty Function for In...

引用

The Third International Joint Conference on Computational Science and Optimization(第三届计算科学与优化国际大会 CSO 2010)

作者： Zhijie Wang Sanming Liu School of Electrical Engineering Shanghai Dianji University Shanghai China Department of Mathematics and Physics Shanghai Dianji University Shanghai China

Exact penalty function methods for the solution of constrained optimization problem are based on the construction of a function whose unconstrained minimizing points are also solution of the constrained problem. One of the popular exact penalty functions is l1 exact penalty function. However l1 exact penalty function is not a smooth function. In this paper, we propose a new method for smoothing the l1 exact penalty function for inequality constrained optimization. Error estimations are obtained among the optimal objective function values of the smoothed penalty problem, of the nonsmooth penalty problem problem and of the original optimization problem. We develop an efficient algorithm for solving the optimization problem based the smoothed penalty function and prove the convergence of the algorithm.

关键词： l1 exact penalty function smoothing method approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Survey of approximation algorithms for set cover problem

Survey of approximation algorithms for set cover problem

引用

作者： Dutta, Himanshu Shekhar University of North Texas

学位级别：M.S.

In this thesis, I survey 11 approximation algorithms for unweighted set cover problem. I have also implemented the three algorithms and created a software library that stores the code I have written. The algorithms I survey are: (1) Johnson’s standard greedy; (2) f-frequency greedy; (3) Goldsmidt, Hochbaum and Yu’s modified greedy; (4) Halldorsson’s local optimization; (5) Dur and Furer semi local optimization; (6) Asaf Levin’s improvement to Dur and Furer; (7) Simple rounding; (8) Randomized rounding; (9) LP duality; (10) Primal-dual schema; and (11) Network flow technique. Most of the algorithms surveyed are refinements of standard greedy algorithm.

关键词： Set cover approximation algorithm greedy algorithm approximation algorithms. Set theory

来源：评论

学校读者我要写书评

暂无评论

A Bin-packing Model Based on File Preservation Problem

A Bin-packing Model Based on File Preservation Problem

引用

2010 International Conference of Informationa Science and Management Engineering(2010年信息科学与管理工程国际学术会议 ISME 2010)

作者： Qingshan ZHANG Jida HUANG Huazhen CHANG Shaobo LI School of Mines China University of Mining & Technology Xuzhou China

This paper established a bin-packing model according to file preservation problems, which is a NP hard problem, the paper use FF and FFD algorithm to obtain the corresponding results, by comparing the results, with the bound theory of the optimal solution to prove the obtained solution from FFD algorithm shall be the optimal solution. This paper further analysis of a large-scale one-dimensional packing problem solving method, in order to overcome the disadvantage of classical algorithm in space and time, and for searching a good convergence, with strong local search and to avoid falling into local optimal solution algorithm, this paper give the processes of simulated annealing algorithm.

关键词： bin-packing model NP Hard File Preservation approximation algorithm SA

来源：评论

学校读者我要写书评

暂无评论

Determining Storage Locations and Capacities for Emergency Response

Determining Storage Locations and Capacities for Emergency R...

引用

第九届运筹学及其应用国际研讨会

作者： Jianming Zhu Degang Liu Jun Huang Jiye Han College of Engineering Graduate University of Chinese Academy of Sciences Institute of Applied Mathematics Academy of Mathematics and Systems Science CAS

In this paper, we consider the problem of emergency response resource storage locations and capacities. Resources are important for disaster relief operations in coping with natural and manmade emergencies. In order to enhance the ability of response to disasters, different levels of reserve system need to be set up for holding relief resources. These emergency storages may have different capacities and construction costs. In this paper, we formulate a model to determine the storage locations and their capacities at minimum total construction cost. Then, an approximation algorithm is presented by introducing LP-rounding technique. Finally, the proofs of correctness and approximation ratio are shown.

关键词： Location Resource Reserve System LP-rounding approximation algorithm Emergency Response

来源：评论

学校读者我要写书评

暂无评论

The Single-machine Parallel-batching Scheduling Problem with Family Jobs to Minimize Makespan

The Single-machine Parallel-batching Scheduling Problem with...

引用

2010 Second International Conference on Communication Systems, Networks and Applications (ICCSNA 2010)

作者： Meng Jintao,Lu Xiaoxu Zhengzhou Institute of Aeronautical Industry Management Zhengzhou 450015,China

In this paper we consider the single-machine parallel-batching scheduling problem with family jobs under on-line setting in the sense that we construct our schedule irrevocably as time proceeds and do not know of the existence of any job until its *** objective is to minimize the maximum completion time of the jobs（makespan）.We deal with the special variant of the problem:the unbounded model in which the machine can handle infinite number of jobs simultaneously,the jobs only have two distinct arrival times and come from m *** provide an on-line algorithm with a worst case ratio of 2-α/2,where α = 5-1]/2.

关键词： single machine scheduling worst-case analysis approximation algorithm on-line Parallelbatching Scheduling

来源：评论

学校读者我要写书评

暂无评论

Assigning tasks for efficiency in Hadoop: extended abstract 10

Assigning tasks for efficiency in Hadoop: extended abstract

引用

Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures

作者： Michael J. Fischer Xueyuan Su Yitong Yin Yale University New Haven CT USA Nanjing University Nanjing China

ISBN: (纸本)9781450300797

In recent years Google's MapReduce has emerged as a leading large-scale data processing architecture. Adopted by companies such as Amazon, Facebook, Google, IBM and Yahoo! in daily use, and more recently put in use by several universities, it allows parallel processing of huge volumes of data over cluster of machines. Hadoop is a free Java implementation of MapReduce. In Hadoop, files are split into blocks and replicated and spread over all servers in a network. Each job is also split into many small pieces called tasks. Several tasks are processed on a single server, and a job is not completed until all the assigned tasks are finished. A crucial factor that affects the completion time of a job is the particular assignment of tasks to servers. Given a placement of the input data over servers, one wishes to find the assignment that minimizes the completion time. In this paper, an idealized Hadoop model is proposed to investigate the Hadoop task assignment problem. It is shown that there is no feasible algorithm to find the optimal Hadoop task assignment unless P = NP. Assignments that are computed by the round robin algorithm inspired by the current Hadoop scheduler are shown to deviate from optimum by a multiplicative factor in the worst case. A flow-based algorithm is presented that computes assignments that are optimal to within an additive constant.

关键词： np-completeness hadoop approximation algorithm mapreduce load balancing task assignment

来源：评论

学校读者我要写书评

暂无评论

Nonlinear Discrete Optimization

引用

丛书名： Zurich lectures in advanced mathematics

2010年

作者： Shmuel Onn

ISBN: (数字)9783037195932

ISBN: (纸本)9783037190937

This monograph develops an algorithmic theory of nonlinear discrete optimization. It introduces a simple and useful setup which enables the polynomial time solution of broad fundamental classes of nonlinear combinatorial optimization and integer programming problems in variable dimension. An important part of this theory is enhanced by recent developments in the algebra of Graver bases. The power of the theory is demonstrated by deriving the first polynomial time algorithms in a variety of application areas within operations research and statistics, including vector partitioning, matroid optimization, experimental design, multicommodity flows, multi-index transportation and privacy in statistical databases. The monograph is intended for graduate students and researchers. It is accessible to anyone with standard undergraduate knowledge and mathematical maturity.

关键词： Integer programming combinatorial optimization optimization linear programming stochastic programming randomized algorithm approximation algorithm polynomial time transportation problem multi index transportation problem transshipment problem multicommodity flow congestion game spanning tree matroid submodular function matching partitioning clustering polytope zonotope edge direction totally unimodular matrix test set Graver base contingency table statistical table multiway table disclosure control data security privacy algebraic statistics experimental design Frobenius number Grobner base Hilbert scheme zero-dimensional ideal

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：