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

21st Annual Symposium on Computational Geometry

作者： Ahn, Hee-Kap Cheong, Otfried Park, Chong-Dae Shin, Chan-Su Vigneron, Antoine Korea Adv Inst Sci & Technol Div Comp Sci Taejon 305701 South Korea Sejong Univ Dept Comp Sci & Engn Seoul South Korea Hankuk Univ Foreign Studies Sch Elect & Inform Engn Yongin South Korea INRA Unite Math & Informat Appl Jouy En Josas France

Given two compact convex sets P and Q in the plane, we compute an image of P under a rigid motion that approximately maximizes the overlap with Q. More precisely, for any epsilon > 0, we compute a rigid motion such that the area of overlap is at least 1-epsilon times the maximum possible overlap. Our algorithm uses O(1/epsilon) extreme point and line intersection queries on P and Q, plus O((1/epsilon(2)) log(1/epsilon)) running time. If only translations are allowed, the extra running time reduces to O((1/epsilon) log(1/epsilon)). If P and Q are convex polygons with n vertices in total that are given in an array or balanced tree, the total running time is O((1/epsilon) log n + (1/epsilon(2)) log(1/epsilon)) for rigid motions and O((1/epsilon) log n + (1/epsilon) log(1/epsilon)) for translations. (c) 2006 Elsevier B.V. All rights reserved.

关键词： approximation algorithm sublinear algorithm convex shape geometric pattern matching

来源：评论

学校读者我要写书评

暂无评论

algorithms for minimum m-connected k-dominating set problem

引用

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 Peoples R China Illinois Inst Technol Dept Comp Sci Chicago IL USA

ISBN: (纸本)9783540735557

In wireless sensor networks, virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem and perform some other tasks such as area monitoring. Previous work in this area has mainly focused on how to set up a small virtual backbone for high efficiency, which is modelled as the minimum Connected Dominating Set (CDS) problem. In this paper we consider how to establish a small virtual backbone to balance efficiency and fault tolerance. This problem can be formalized as the minimum m-connected k-dominating set problem, which is a general version of minimum CDS problem with m = 1 and k = 1. In this paper we will propose some approximation algorithms for this problem that beat the current best performance ratios.

关键词： connected dominating set approximation algorithm k-vertex connectivity wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

Packing and covering δ-hyperbolic spaces by balls

引用

10th Int Workshop on approximation algorithms for Combinatorial Optimization Problems/11th Int Workshop on Randomization and Computation

作者： Chepoi, Victor Estellon, Bertrand Univ Aix Marseille 2 Fac Sci Luminy Lab Informat Fondamentale Marseille F-13288 Marseille 9 France

ISBN: (纸本)9783540742074

We consider the problem of covering and packing subsets of delta-hyperbolic metric spaces and graphs by balls. These spaces, defined via a combinatorial Gromov condition, have recently become of interest in several domains of computer science. Specifically, given a subset S of a delta-hyperbolic graph G and a positive number R, let gamma(S, R) be the minimum number of balls of radius R covering S. It is known that computing 7(S, R) or approximating this number within a constant factor is hard even for 2-hyperbolic graphs. In this paper, using a primal-dual approach, we show how to construct in polynomial time a covering of S with at most gamma(S, R) balls of (slightly larger) radius R + delta. This result is established in the general framework of delta-hyperbolic geodesic metric spaces and is extended to some other set families derived from balls. The covering algorithm is used to design better approximation algorithms for the augmentation problem with diameter constraints and for the k-center problem in delta-hyperbolic graphs.

关键词： covering packing ball metric space approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximating generalized multicut on trees

引用

3rd Conference on Computability in Europe (CiE 2007)

作者： Zhang, Peng Chinese Acad Sci Inst Software State Key Lab Comp Sci Beijing 100080 Peoples R China

ISBN: (纸本)9783540730002

Given a tree T with costs on edges and a collection of terminal sets X = {S-1, S-2,..., S-l}, the generalized Multicut problem asks to find a set of edges on T whose removal cuts every terminal set in X, such that the total cost of the edges is minimized. The standard version of the problem can be approximately solved by reducing it to the classical Multicut on trees problem. For the prize-collecting version of the problem, we give a primal-dual 3-approximation algorithm and a randomized 2.55-approximation algorithm (the latter can be derandomized). For the k-version of the problem, we show an interesting relation between the problem and the Densest k-Subgraph problem, implying that approximating the k-version of the problem within O(n(1/6-epsilon)) for some small 6 > 0 is hard. We also give a min {2(l - k + 1), k}-approximation algorithm for the k-version of the problem via a nonuniform approach.

关键词： generalized multicut tree approximation algorithm combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Approximating the crossing number of toroidal graphs

引用

18th International Symposium on algorithms and Computations (ISAAC 2007)

作者： Hlineny, Petr Salazar, Gelasio Tech Univ Ostrava FEI 17 Listopadu 15 Ostrava 70833 Czech Republic Masaryk Univ Fac Informat Brno 60200 Czech Republic Univ Autonoma San Luis Potosi Inst Fis San Luis Potosi 78000 Mexico

ISBN: (纸本)9783540771180

CROSSING NUMBER is one of the most challenging algorithmic problems in topological graph theory, with applications to graph drawing and VLSI layout. No polynomial time constant approximation algorithm is known for this NP-complete problem. We prove that a natural approach to planar drawing of toroidal graphs (used already by Pach and Toth in [21]) gives a polynomial time constant approximation algorithm for the crossing number of toroidal graphs' with bounded degree. In this proof we present a new "grid" theorem on toroidal graphs.

关键词： crossing number approximation algorithm toroidal graph edge-width toroidal grid

来源：评论

学校读者我要写书评

暂无评论

Approximating capacitated tree-routings in networks

Approximating capacitated tree-routings in networks

引用

4th International Conference on Theory and Applications of Models of Computation

作者： Morsy, Ehab Nagamochi, Hiroshi Kyoto Univ Dept Appl Math & Phys Kyoto 6068501 Japan Yoshida Honmachi Kyoto 6068501 Japan

ISBN: (纸本)9783540725039

The capacitated tree-routing problem (CTR) in a graph G = (V, E) consists of an edge weight function w : E -> R+, a sink s is an element of V, a terminal set M subset of V with a demand function q : M -> R+, a routing capacity k > 0, and an integer edge capacity lambda >= 1. The CTR asks to find a partition M = {Z(1), Z(2), . . ., Z(l)} of M and a set T = {T-1, T-2, . . ., T-l} of trees of G such that each T-i spans Z(i) boolean OR {s} and satisfies Sigma(v is an element of Zi) q(v) <= k. A subset of trees in T can pass through a single copy of an edge e is an element of E as long as the number of these trees does not exceed the edge capacity lambda;any integer number of copies of e are allowed to be installed, where the cost of installing a copy of e is w(e). The objective is to find a solution (M, T) that minimizes the installing cost Sigma(e is an element of E) [vertical bar{T is an element of T vertical bar T contains e}vertical bar/lambda]w(e). In this paper, we propose a (2 + rho(ST))-approximation algorithm to the CTR, where rho(ST) is any approximation ratio achievable for the Steiner tree problem.

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

来源：评论

学校读者我要写书评

暂无评论

algorithms for the m-coverage problem and k-connected m-coverage problem in wireless sensor networks

Algorithms for the m-coverage problem and k-connected m-cove...

引用

IFIP International Conference on Network and Parallel Computing

作者： Li, Deying Cao, Jiannong Liu, Dongsheng Yu, Ying Sun, Hui Renmin Univ China Sch Informat Beijing 100872 Peoples R China Key Lab Data Engn & Knowledge Engn MOE Beijing Peoples R China Hong Kong Polytech Univ Dept Comp Hong Kong Hong Kong Peoples R China Univ Sci & Technol Beijing Sch Informat Engn Beijing Peoples R China

ISBN: (纸本)9783540747833

An important issue in deploying a wireless sensor network (WSN) is to provide target coverage with high energy efficiency and fault-tolerance. In this paper, we study the problem of constructing energy-efficient and fault-tolerant target coverage with the minimal number of active nodes which form an m-coverage for targets and a k-connected communication subgraph. We propose two heuristic algorithms for m-coverage problem, and get the performance ratio of one heuristic. Then two heuristic algorithms are further proposed to solve the k-connected m-coverage problem. The simulation results demonstrate the desired efficiency of the proposed algorithms.

关键词： k-connected m-coverage sensor networks approximation algorithm energy-efficient

来源：评论

学校读者我要写书评

暂无评论

Unbiased Matrix Rounding

引用

Electronic Notes in Discrete Mathematics 2007年 28卷 41-46页

作者： Friedrich, Tobias Doerr, Benjamin Klein, Christian Osbild, Ralf Max-Planck-Institut für Informatik Saarbrücken Germany Max-Planck-Institut für Informatik Saarbrücken Germany

We show several ways to round a real matrix to an integer one such that the rounding errors in all rows and columns as well as the whole matrix are less than one. This is a classical problem with applications in many fields, in particular, statistics. We improve earlier solutions of different authors in two ways. For rounding matrices of size m × n, we reduce the runtime from O ((m n)²) to O (m n log (m n)). Second, our roundings also have a rounding error of less than one in all initial intervals of rows and columns. Consequently, arbitrary intervals have an error of at most two. This is particularly useful in the statistics application of controlled rounding. The same result can be obtained via (dependent) randomized rounding. This has the additional advantage that the rounding is unbiased, that is, for all entries y_{i j} of our rounding, we have E (y_{i j}) = x_{i j}, where x_{i j} is the corresponding entry of the input matrix. © 2007 Elsevier B.V. All rights reserved.

关键词： approximation algorithm Controlled rounding Linear discrepancy Rounding

来源：评论

学校读者我要写书评

暂无评论

Maximizing throughput for traffic grooming with limited grooming resources

Maximizing throughput for traffic grooming with limited groo...

引用

IEEE Global Telecommunications Conference (GLOBECOM 07)

作者： Wang, Yong Gu, Qian-Ping Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada

ISBN: (纸本)9781424410422

In SONET/WDM networks, low-rate traffic demands are usually multiplexed to share a high-speed wavelength channel. The multiplexing/de-multiplexing is known as traffic grooming and performed by SONET Add-Drop Multiplexers (SADM). The grooming factor, denoted by k, is the maximum number of low-rate traffic demands that can be multiplexed into one wavelength channel. SADMs are expensive and thus a critical optimization problem for traffic grooming is to maximize the number of accommodated traffic demands subject to a given number of SADMs. In this paper, we focus on the Unidirectional Path-Switched Ring (UPSR) networks with unitary duplex traffic demands. We assume that each network node is equipped with a limited number L of SADMs, and our objective is to maximize the throughput for a given set of traffic demands. We prove the NP-hardness of this Maximum Throughput traffic grooming problem, and propose a (k +1)-approximation algorithm. Extensive simulations are conducted to validate the performance of the algorithm. We also study the case that the given set of traffic demands is the all-to-all set. We propose an algorithm which accommodates at least nL[root k]/2 traffic demands, and prove that an optimal solution can accommodate at most nL[root k]/root 2 traffic demands for the all-to-all set on a UPSR network of n nodes. The solution of our algorithm is at most a constant factor (about root 2) away from the optimal solution.

关键词： traffic grooming SONET/WDM networks graph partition NP-complete approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Call control and routing in SONET rings

引用

1st International Conference on Combinatorics, algorithms, Probabilistic and Experimental Methodologies

作者： Chen, Shuqiang Fang, Qizhi Ocean Univ China Dept Math Qingdao 266071 Peoples R China

ISBN: (纸本)9783540744498

In this paper, we provide a polynomial-time approximation algorithm for Call Control and Routing problems in SONET rings. In this problem, we are given a SONET ring and a set of calls, each of which is described by a source-destination pair of nodes together with an integer specifying the call demand, the aim is to devise a routing scheme such that the total demand transmitted is maximum subject to the bandwidth restriction. We first give an NP-hardness proof for this problem. Then a polynomial-time approximation algorithm is provided. When d(max) <= 1/Kd* (where K > 2 is a constant, d* is the available bandwidth of the ring and d(max) is the largest call demand among all the calls), the algorithm outputs a routing scheme with total demand transmitted at least as (1 - 7/2K+3) times the optimum.

关键词： SONET ring call routing MP-hard approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：