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

4th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Li, Deying Li, Zheng Ma, Wenkai Chen, Hong Renmin Univ China Key Lab Data Engn & Knowledge Engn MOE Sch Informat Beijing Peoples R China

ISBN: (纸本)9783642174605

One approach to guarantee the performance of underwater acoustic sensor networks is to deploy multiple Surface-level Gateways (SGs) at the surface. This paper addresses the connected (or survivable) Constrained Surface-level Gateway Placement (C-SGP) problem for 3-D underwater acoustic sensor networks. Given a set of candidate locations where SGs can be placed, our objective is to place minimum number of SGs at a subset of candidate locations such that it is connected (or 2-connected) from any USN to the base station. We propose a polynomial time approximation algorithm for the connected C-SGP problem and survivable C-SGP problem, respectively. Simulations are conducted to verify our algorithms' efficiency.

关键词： Underwater sensor networks Surface-level gateway placement Connectivity Survivability approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

AN IMPROVED LINE-SEPARABLE algorithm FOR DISCRETE UNIT DISK COVER

引用

DISCRETE MATHEMATICS algorithmS AND APPLICATIONS 2010年第1期2卷 77-87页

作者： Claude, Francisco Das, Gautam K. Dorrigiv, Reza Durocher, Stephane Fraser, Robert Lopez-Ortiz, Alejandro Nickerson, Bradford G. Salinger, Alejandro Univ Waterloo David R Cheriton Sch Comp Sci 200 Univ Ave West Waterloo ON N2L 3G1 Canada Univ New Brunswick Fac Comp Sci Fredericton NB E3B 5A3 Canada Univ Manitoba Dept Comp Sci EITC E2 445 Winnipeg MB R3T 2N2 Canada

Given a set D of m unit disks and a set P of n points in the plane, the discrete unit disk cover problem is to select a minimum cardinality subset D' subset of D to cover P. This problem is NP-hard [14] and the best previous practical solution is a 38-approximation algorithm by Carmi et al. [5]. We first consider the line-separable discrete unit disk cover problem (the set of disk centers can be separated from the set of points by a line) for which we present an O(n( log n + m))-time algorithm that finds an exact solution. Combining our line-separable algorithm with techniques from the algorithm of Carmi et al. [5] results in an O(m(2)n(4)) time 22-approximate solution to the discrete unit disk cover problem.

关键词： Discrete unit disk cover approximation algorithm disk stabbing

来源：评论

学校读者我要写书评

暂无评论

On Metric Clustering to Minimize the Sum of Radii

引用

11th Scandinavian Workshop on algorithm Theory (SWAT 2008)

作者： Gibson, Matt Kanade, Gaurav Krohn, Erik Pirwani, Imran A. Varadarajan, Kasturi Univ Iowa Dept Comp Sci Iowa City IA 52242 USA Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

ISBN: (纸本)3540699007

Given an n-point metric (P,d) and an integer k > 0, we consider the problem of covering P by k balls so as to minimize the sum of the radii of the balls. We present a randomized algorithm that runs in n (O(log na <...log Delta)) time and returns with high probability the optimal solution. Here, Delta is the ratio between the maximum and minimum interpoint distances in the metric space. We also show that the problem is NP-hard, even in metrics induced by weighted planar graphs and in metrics of constant doubling dimension.

关键词： Clustering Polynomial time approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

引用

26th Annual Symposium on Computational Geometry

作者： Agarwal, Pankaj K. Aronov, Boris van Kreveld, Marc Loeffler, Maarten Silveira, Rodrigo I. Duke Univ Dept Comp Sci Durham NC 27706 USA

ISBN: (纸本)9781450300162

We study the problem of computing the similarity between two piecewise-linear bivariate functions defined over a common domain, where the surfaces they define in 3D-polyhedral terrains-can be transformed vertically by a linear transformation of the third coordinate (scaling and translation). We present a randomized algorithm that minimizes the maximum vertical distance between the graphs of the two functions, over all linear transformations of one of the terrains, in O(n(4/3) polylog n) expected time, where n is the total number of vertices in the graphs of the two functions. We also study the computation of similarity between two univariate or bivariate functions by minimizing the area or volume between their graphs. For univariate functions we give a (1 + epsilon)-approximation algorithm for minimizing the area that runs in O(n/root epsilon) time, for any fixed epsilon > 0. The (1 + epsilon)-approximation algorithm for the bivariate version, where volume is minimized, runs in O(n/epsilon(2)) time, for any fixed epsilon > 0, provided the two functions are defined over the same triangulation of their domain.

关键词： piecewise-linear function polyhedral terrain similarity approximation algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Capacitated Confluent Flows: Complexity and algorithms

Capacitated Confluent Flows: Complexity and Algorithms

引用

7th International Conference on algorithms and Complexity

作者： Dressler, Daniel Strehler, Martin TU Berlin Inst Math MA 5-2Str 17 Juni 136 D-10623 Berlin Germany Brandenburg Tech Univ Cottbus Math Inst D-03013 Cottbus Germany

ISBN: (纸本)9783642130724

A flow on a directed network is said to be confluent if the flow uses at most one on arc at each node. Confluent flows arise naturally from destination-based routing. We study the Maximum Confluent Flow Problem (MAXCONF) with a single commodity but multiple sources and sinks. Unlike previous results, we consider heterogeneous arc capacities. The supplies and demands of the sources and sinks can also be bounded. We give a pseudo-polynomial time algorithm and an FPTAS for graphs with constant treewidth. Somewhat surprisingly, MAXCONF is NP-hard even On trees, so these algorithms are, in a sense, best possible. We also show that it is NP-complete to approximate MAXCONF better than 3/2 on general graphs.

关键词： approximation algorithm confluent flow network flow routing treewidth

来源：评论

学校读者我要写书评

暂无评论

Supporting Multi-Missions In Wireless Sensor Networks

Supporting Multi-Missions In Wireless Sensor Networks

引用

作者： Liu, Changlei PennState University Libraries

学位级别：Doctor of Philosophy

The recent advances in sensing devices, embedded computing and wireless communication technology has sparked the emergence of the wireless sensor networks. However, most of the sensor networksnowadays only target for a single mission, and may not be cost effective from the resource management point of view. Therefore, in this dissertation, we focus on the design of multi-mission sensor network which is envisioned to support multiple applications of diverse requirements with a single *** support multiple missions, several challenges naturally arise. The first challenge comes from the fact that the missions or the mission requirements may change over time. Therefore, the network needs to be enriched with the adaptation capability to explicitly handle the mission switch. Second, since sensor network has limitedresources, e.g., energy, sensing, bandwidth, etc, these resources have to be shared by the multiple missions. An efficient resource allocation scheme, therefore, should maximize the total profit by taking account into all the mission requirements. Third, since mission-driven sensor network is usually deployed in the harsh, unattended, dynamic environment, it is important to monitor the sensor status, based on which decisions about the mission switch can be made. While more challenges can be listed here, in thisdissertation, we primarily focus on these three aspects, namely, mission switch, resource allocation, and network monitoring. Each of the aspects is examined under different contexts within an integrated framework, and briefly summarized in the ***, we study the mission switch in a surveillance application. As mission switches, e.g., the network is commanded to last for alonger time, some sensors may have to sleep longer during each duty cycle. Then the original sensor deployment may not be able to satisfy the coverage and lifetime requirements at the same time, and the coverage may need to be traded for network lifetime. To deal with thi

关键词： sensor network multi-mission wireless approximation algorithm coverage landmine monitoring

来源：评论

学校读者我要写书评

暂无评论

Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem

引用

DISCRETE APPLIED MATHEMATICS 2006年第16期154卷 2402-2410页

作者： Miyata, Keizo Masuyama, Shigeru Nakayama, Shin-ichi Zhao, Liang Toyohashi Univ Technol Toyohashi Aichi 4418580 Japan Univ Tokushima Fac Integrated Arts & Sci Tokushima 7708502 Japan Utsunomiya Univ Fac Engn Dept Informat Sci Utsunomiya Tochigi 3218585 Japan

The minimum vertex ranking spanning tree problem (MVRST) is to find a spanning tree of G whose vertex ranking is minimum. In this paper, we show that MVRST is NP-hard. To prove this, we polynomially reduce the 3-dimensional matching problem to MVRST. Moreover, we present a ([D-s/2] + 1)/([log(2)(D-s + 1)] + 1)-approximation algorithm for MVRST where D-s is the minimum diameter of spanning trees of G. (c) 2006 Elsevier B.V. All rights reserved.

关键词： vertex ranking spanning tree graph theory NP-hard computational complexity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A 2-approximation algorithm for the network substitution problem

引用

OPERATIONS RESEARCH LETTERS 2006年第1期34卷 94-96页

作者： Pisaruk, NN Belarusian State Univ Fac Appl Math & Informat Minsk 220088 BELARUS

The network substitution problem is to substitute an existing network for a new network so that to minimize the cost of exploiting the existing network during the period when the new network is being constructed. We show that this problem is NP-hard, and propose a 2-approximation algorithm for solving it. (c) 2005 Elsevier B.V. All rights reserved.

关键词： network scheduling complexity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A (1-1/e)-approximation algorithm for the generalized assignment problem

引用

OPERATIONS RESEARCH LETTERS 2006年第3期34卷 283-288页

作者： Nutov, Z Beniaminy, I Yuster, R Open Univ Israel Dept Comp Sci IL-43107 Raanana Israel ClickSoftware Technol IL-69710 Tel Aviv Israel Univ Haifa Dept Math IL-31905 Haifa Israel

We give a (1-1/e)-approximation algorithm for the may-profit generalized assignment problem (Max-GAP) with fixed profits when the profit (but not necessarily the size) of every item is independent from the bin it is assigned to. The previously best-known approximation ratio for this problem was 1/2. (c) 2005 Elsevier B.V. All rights reserved.

关键词： generalized assignment approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A greedy approximation algorithm for the group Steiner problem

引用

DISCRETE APPLIED MATHEMATICS 2006年第1期154卷 15-34页

作者： Chekuri, C Even, G Kortsarz, G Lucent Bell Labs Murray Hill NJ USA Tel Aviv Univ Dept Elect Engn IL-69978 Tel Aviv Israel Rutgers State Univ Dept Comp Sci Camden NJ 08102 USA

In the group Steiner problem we are given an edge-weighted graph G = (V, E, w) and in subsets of vertices {g(i)}(i=1)(m). Each subset gi is called a group and the vertices in boolean OR(i)g(i) are called terminals. It is required to find a minimum weight tree that contains at least one terminal from every group. We present a poly-logarithmic ratio approximation for this problem when the input graph is a tree. Our algorithm is a recursive greedy algorithm adapted from the greedy algorithm for the directed Steiner tree problem [Approximating the weight of shallow Steiner trees, Discrete Appl. Math. 93 (1999) 265-285, approximation algorithms for directed Steiner problems, J. algorithms 33 (1999) 73-91]. This is in contrast to earlier algorithms that are based on rounding a linear programming based relaxation for the problem [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259, On directed Steiner trees, Proceedings of SODA, 2002, pp. 59-63]. We answer in positive a question posed in [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259] on whether there exist good approximation algorithms for the group Steiner problem that are not based on rounding linear programs. For every fixed constant epsilon > 0, our algorithm gives an O((log Sigma(i)vertical bar g(i)vertical bar)(1+epsilon) center dot log m) approximation in polynomial time. approximation algorithms for trees can be extended to arbitrary undirected graphs by probabilistically approximating the graph by a tree. This results in an additional multiplicative factor of O(log vertical bar V vertical bar) in the approximation ratio, where vertical bar V vertical bar is the number of vertices in the graph. The approximation ratio of our algorithm on trees is slightly worse than the ratio

关键词： group Steiner problem tree combinatorial greedy approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：