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

7th Latin American Symposium on Theoretical Informatics (LATIN 2006)

作者： Sakashita, Mariko Makino, Kazuhisa Fujishige, Satoru Univ Tokyo Grad Sch Informat Sci & Technol Tokyo 1138656 Japan Kyoto Univ Grad Sch Informat Kyoto 6068501 Japan Kyoto Univ Math Sci Res Inst Kyoto 6068501 Japan

ISBN: (纸本)354032755X

In this paper, we consider source location problems and their generalizations with three connectivity requirements (arc-connectivity requirements lambda and two kinds of vertex-connectivity requirements kappa and (kappa) over cap), where the source location problems are to find a minimum-cost set S subset of V in a given graph G=(V,A) with a capacity function u:A -> R(+) such that for each vertex v is an element of V, the connectivity from S to v (resp., from v to S) is at least a given demand d(-)(v) (resp., d(+)(v)). We show that the source location problem with edge-connectivity requirements in undirected networks is strongly NP-hard, which solves an open problem posed by Arata et al. (J. algorithms 42: 54-68, 2002). Moreover, we show that the source location problems with three connectivity requirements are inapproximable within a ratio of c ln D for some constant c, unless every problem in NP has an O(N (log log) (N))-time deterministic algorithm. Here D denotes the sum of given demands. We also devise (1+lnD)-approximation algorithms for all the extended source location problems if we have the integral capacity and demand functions. By the inapproximable results above, this implies that all the source location problems are Theta(ln Sigma (v epsilon V) (d(+)(v)+d(-)(v)))-approximable.

关键词： connectivity location problem combinatorial optimization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Clustering for Metric and Non-Metric Distance Measures

Clustering for Metric and Non-Metric Distance Measures

引用

19th ACM-SIAM Symposium on Discrete algorithms

作者： Ackermann, Marcel R. Bloemer, Johannes Sohler, Christian Univ Gesamthsch Paderborn Dept Comp Sci Fac Elect Engn Comp Sci & Math D-33095 Paderborn Germany

ISBN: (纸本)9780898716474

We study a generalization of the k-median problem with respect to an arbitrary dissimilarity measure D. Given a finite set P, our goal is to find a set C of size k such that the sum of errors D(P,C) = Sigma(p is an element of p) min(c is an element of C){D(p,c)} is minimized. The main result in this paper can be stated as follows: There exists an O(n2((k/t)O(1))) time (I + epsilon)-approximation algorithm for the k-median problem with respect to D, if the 1-median problem can be approximated within a factor of (1 + by taking a random sample of constant size and solving the 1-median problem on the sample exactly. Using this characterization, we obtain the first linear time (1+ e)-approximation algorithms for the k-median problem in an arbitrary metric space with bounded doubling dimension, for the Kullback-Leibler divergence (relative entropy), for Malialanobis distances, and for some special cases of Bregman divergences. Moreover, we obtain previously known results for the Euclidean k-median problem and the Euclidean k-means problem in a simplified manner. Our results are based on a new analysis of an algorithm from [20].

关键词： κ-means clustering κ-median clustering approximation algorithm Bregman divergences Itakura-Saito divergence Kullback-Leibler divergence Mahalanobis distance Random sampling

来源：评论

学校读者我要写书评

暂无评论

Embeddings of Negative-Type Metrics and An Improved approximation to Generalized Sparsest Cut

引用

ACM TRANSACTIONS ON algorithmS 2008年第2期4卷 22-22页

作者： Chawla, Shuchi Gupta, Anupam Raecke, Harald Univ Wisconsin Madison WI 53706 USA Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA Univ Warwick Coventry CV4 7AL W Midlands England

In this article, we study metrics of negative type, which are metrics ( V, d) such that root d is an Euclidean metric;these metrics are thus also known as l(2)-squared metrics. We show how to embed n-point negative-type metrics into Euclidean space l(2) with distortion D = O(log (3/4) n). This embedding result, in turn, implies an O(log (3/4) k)-approximation algorithm for the Sparsest Cut problem with nonuniform demands. Another corollary we obtain is that n-point subsets of l(1) embed into l(2) with distortion O(log (3/4) n).

关键词： approximation algorithm embedding metrics negative-type metric sparsest cut

来源：评论

学校读者我要写书评

暂无评论

A New Nature-inspired algorithm for Load Balancing

A New Nature-inspired Algorithm for Load Balancing

引用

11th IEEE Singapore International Conference on Communication Systems

作者： Feng, Xiang Lau, Francis C. M. Shuai, Dianxun East China Univ Sci & Technol Dept Comp Sci Shanghai 200237 Peoples R China Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China

ISBN: (纸本)9781424424238

The classical Load Balancing Problem (LBP) is to map tasks to processors so as to minimize the maximum load. Solving the LBP successfully would lead to better utilization of resources and better performance. The LBP has been proven to be NP-hard, thus generating the exact solutions in a tractable amount of time becomes infeasible when the problems become large. We present a new nature-inspired approximation algorithm based on the Particle Mechanics (PM) model to compute in parallel approximate efficient solutions for LBPs. Just like other Nature-inspired algorithms (NAs) drawing from observations of physical processes that occur in nature, the PM algorithm is inspired by physical models of particle kinematics and dynamics. The PM algorithm maps the classical LBP to the movement of particles in a force field by a corresponding mathematical model in which all particles move according to certain defined rules until reaching a stable state. By anti-mapping the stable state, the solution to LBP can be obtained.

关键词： Load balancing approximation algorithm nature-inspired algorithm particle mechanics model distributed and parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

On routing in VLSI design and communication networks

引用

16th International Symposium on algorithms and Computations (ISAAC 2005)

作者： Terlaky, Tamas Vannelli, Anthony Zhang, Hu Canadian Imperial Bank Commerce Toronto ON Canada McMaster Univ Sch Computat Engn & Sci Dept Comp & Software Hamilton ON Canada Univ Guelph Coll Phys & Engn Sci Guelph ON N1G 2W1 Canada

ISBN: (纸本)3540309357

In this paper, we study the global routing problem in VLSI design and the multicast routing problem in communication networks. First we propose new and realistic models for both problems. In the global routing problem in VLSI design, we are given a lattice graph and subsets of the vertex set. The goal is to generate trees spanning these vertices in the subsets to minimize a linear combination of overall wirelength (edge length) and the number of bends of trees with respect to edge capacity constraints. In the multicast routing problem in communication networks, a graph is given to represent the network, together with subsets of the vertex set. We are required to find trees to span the given subsets and the overall edge length is minimized with respect to capacity constraints. Both problems are APX-hard. We present the integer linear programming (LP) formulation of both problems and solve the LP relaxations by the fast approximation algorithms for min-max resource-sharing problems in [K. Jansen, H. Zhang, approximation algorithms for general packing problems and their application to the multicast congestion problem, Math. Programming, to appear, doi: 10.1007/s10107-007-0106-8] (which is a generalization of the approximation algorithm proposed by Grigoriadis and Khachiyan [Coordination complexity of parallel price-directive decomposition, Math. Oper. Res. 2 (1996) 321-340]). For the global routing problem, we investigate the particular property of lattice graphs and propose a combinatorial technique to overcome the hardness due to the bend-dependent vertex cost. Finally, we develop asymptotic approximation algorithms for both problems with ratios depending on the best known approximation ratio for the minimum Steiner tree problem. They are the first known theoretical approximation bound results for the problems of minimizing the total costs (including both the edge and the bend costs) while spanning all given subsets of vertices. (C) 2008 Elsevier B.V. All rights rese

关键词： approximation algorithm routing VLSI design communication networks

来源：评论

学校读者我要写书评

暂无评论

Energy Efficient Multicast Routing for Discrete Power Levels in Ad Hoc Sensor Networks

Energy Efficient Multicast Routing for Discrete Power Levels...

引用

4th International Conference on Wireless Communications, Networking and Mobile Computing

作者： Li, Deying Zhu, Qinghua Li, Zheng Renmin Univ China MOE Key Lab Data Engn & Knowledge Engn Beijing 100872 Peoples R China Renmin Univ China Sch Informat Beijing 100872 Peoples R China

ISBN: (纸本)9781424421077

In this paper, we discuss the energy efficient multicast problem for discrete power levels in ad hoe sensor wireless networks. The problem of our concern is: given n nodes and each node v has l(v) transmission power levels and a multicast request (s, D), how to find a multicast tree rooted at s and spanning all destinations in D such that the total energy cost of the multicast tree is minimized. This problem is NP-hard. We propose a NWM_DST algorithm which has a theoretical guaranteed approximation performance ratio, and two efficient heuristics MNJT and g-D-MIP for multicast tree problem. Simulation results have shown efficiency of our proposed algorithms.

关键词： wireless sensor network energy efficiency approximation algorithm multicast routing

来源：评论

学校读者我要写书评

暂无评论

Lower-Bounded Facility Location

Lower-Bounded Facility Location

引用

19th ACM-SIAM Symposium on Discrete algorithms

作者： Svitkina, Zoya Dartmouth Coll Dept Comp Sci Hanover NH 03755 USA

ISBN: (纸本)9780898716474

We study the lower-bounded facility location problem, which generalizes the classical uncapacitated facility location problem in that it comes with lower bound constraints for the number of clients assigned to a facility in the case that this facility is opened. Tins problem was introduced independently in the papers by Karger and Minkoff [12] and by Guha, Meyerson, and Munagala [7], both of which give bicriteria approximation algorithms for it. These bicriteria algorithms come within a constant factor of the optimal solution cost, but they also violate the lower bound constraints by a constant factor. Our result in this paper is the first true approximation algorithm for the lower-bounded facility location problem, which respects the lower bound constraints and achieves a constant approximation ratio for the objective function. The main technical idea for the design of the algorithm is a reduction to the capacitated facility location problem, which has known constant-factor approximation algorithms.

关键词： approximation algorithm Facility location

来源：评论

学校读者我要写书评

暂无评论

On minimum m-connected k-dominating set problem in unit disc graphs

On minimum <i>m</i>-connected <i>k</i>-dominating set proble...

引用

1st International Conference on Combinatorial Optimization and Applications

作者： Shang, Weiping Yao, Frances Wan, Pengjun Hu, Xiaodong Chinese Acad Sci Inst Appl Math Beijing Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China IIT Dept Comp Sci Chicago IL 60616 USA

Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a subset S subset of V of minimal size such that every vertex in V \ S is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation algorithms with constant performance ratios for m <= 2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m.

关键词： k-dominating set m-connectivity unit disc graph approximation algorithm wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

The Problem of Placing Mobility Anchor Points in Wireless Mesh Networks

The Problem of Placing Mobility Anchor Points in Wireless Me...

引用

6th ACM International Workshop on Mobility Management and Wireless Access (MobiWac 2007)

作者： Wu, Lei Landfeldt, Bjorn Univ Sydney USYD SIT Sydney NSW Australia

ISBN: (纸本)9781605580555

Hierarchical mobility management schemes such as HMIP and cellular-IP have been shown to be effective in providing low latency handoff in mobile networks. In this paper, we investigate the suitability of hierarchical mobility management schemes in Wireless Mesh Networks (WMN) and find that they are not directly suitable since MWNs have graph based topologies rather than tree based topologies. Because of this, there exist no natural locations for Mobility Anchor Points (MAP) sub that sub domains can be formed. In this paper, we present a scheme for finding the optimized placement of MAPs in WMNs, We validate our solution with experiments and argue that with optimized placement of MAPs, HMIP is applicable on WMNs and is able to give a close to optimal packet loss rate and handoff latency which is comparable to the performance of HMIP in fixed networks.

关键词： Wireless Mesh network approximation algorithm Mobility Management HMIP

来源：评论

学校读者我要写书评

暂无评论

A Performance Guaranteed Distributed Multicast algorithm for Long-Lived Directional Communications in WANETs

引用

15th International Conference on High Performance Computing (HiPC 2008)

作者： Guo, Song Guo, Minyi Leung, Victor Univ Aizu Sch Engn & Comp Sci Fukushima 9658580 Japan Univ British Columbia Dept Elect & Comp Engn Vancouver BC V6T 1Z4 Canada

ISBN: (纸本)9783540898931

We consider the lifetime optimization problem for multicasting in wireless ad hoc networks, in which each node is equipped with a directional antenna and hits limited energy supplies. In this paper, we propose a new distributed algorithm, whose performance in terms of providing long-lived multicast tree is guaranteed by our theoretical analysis. We prove that its approximation ratio is bounded by a finite number. In particular, the derived upper bound in a closed form shows that the algorithm call achieve global optimal in some cases. The real performance of this new proposed algorithm is also evaluated using Simulation studies and the experimental results show that it outperforms other distributed algorithms.

关键词： Wireless Ad Hoc Network Multicast Directional Antenna Energy Efficiency approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：