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

1st International Conference on Networks and Communications

作者： Ghosh, Sasthi C. Whitaker, Roger M. Allen, Stuart M. Hurley, Steve Indian Stat Inst Bangalore Ctr 8th MileMysore Rd Bangalore 560059 Karnataka India Cardiff Univ Sch Comp Sci Cardiff Wales

ISBN: (纸本)9781424453641

Cell planning requires transmission site selection and configuration. Because this is an NP-hard problem, approximate solutions have to be found when problem instances are large. As such bounds on optimal solutions have to be determined. This is particularly challenging for CDMA-based systems such as 3G because coverage, load and interference are dependent variables. In this paper we first formulate and derive bounds on maximum achievable service coverage ratio subject to the available resources. We then exploit a load approximation algorithm, which substantially reduce computational complexity for down-link formulations of the problem while ensuring that no cell is overloaded. The simulation results show that our approximation algorithm can achieve good coverage accuracy in comparison to the obtained bounds using much lesser computational time at the cost of slightly higher power requirement.

关键词： Cell planning network evaluation power control approximation algorithm UMTS CDMA

来源：评论

学校读者我要写书评

暂无评论

On Hierarchical Diameter-Clustering and the Supplier Problem

引用

THEORY OF COMPUTING SYSTEMS 2009年第3期45卷 497-511页

作者： Das, Aparna Kenyon-Mathieu, Claire Brown Univ Providence RI 02918 USA

Given a data set in a metric space, we study the problem of hierarchical clustering to minimize the maximum cluster diameter, and the hierarchical k-supplier problem with customers arriving online. We prove that two previously known algorithms for hierarchical clustering, one (offline) due to Dasgupta and Long and the other (online) due to Charikar, Chekuri, Feder and Motwani, output essentially the same result when points are considered in the same order. We show that the analyses of both algorithms are tight and exhibit a new lower bound for hierarchical clustering. Finally we present the first constant factor approximation algorithm for the online hierarchical k-supplier problem.

关键词： Hierarchical clustering approximation algorithm Online algorithm

来源：评论

学校读者我要写书评

暂无评论

First-Fit Scheduling for Beaconing in Multihop Wireless Networks

First-Fit Scheduling for Beaconing in Multihop Wireless Netw...

引用

2010 Proceedings IEEE INFOCOM

作者： Peng-Jun Wan Zhu Wang Hongwei Du Scott C.-H. Huang Zhiyuan Wan Department of Computer Science Illinois Institute of Technology Department of Computer Science City University of Hong Kong

ISBN: (纸本)9781424458363

Beaconing is a primitive communication task in which every node locally broadcasts a packet to all its neighbors within a fixed distance. Assume that all communications proceed in synchronous time-slots and each node can transmit at most one fixed-size packet in each time-slot. The problem Minimum-latency beaconing schedule (MLBS) in multihop wireless networks seeks a shortest schedule for beaconing subject to the interference constraint. MLBS has been intensively studied since the mid-1980s, but all assume the protocol interference model with uniform interference radii. In this paper, we first present a constant-approximation algorithm for MLBS under the protocol interference model with arbitrary interference radii. Then, we develop a constant-approximation algorithm for MLBS under the physical interference model. Both approximation algorithms have efficient implementations in a greedy first-fit manner.

关键词： Beaconing schedule protocol interference physical interference approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved Absolute approximation Ratios for Two-Dimensional Packing Problems

Improved Absolute Approximation Ratios for Two-Dimensional P...

引用

12th International Workshop on approximation algorithms for Combinatorial Optimization Problems/13th International Workshop on Randomization and Computation

作者： Harren, Rolf van Stee, Rol MPII D-66123 Saarbrucken Germany

ISBN: (纸本)9783642036842

We consider the two-dimensional bin packing and strip packing problem, where a list. of rectangles has to be packed into a minimal number of rectangular bins of a strip of minimal height, respectively. All packings have to be non-overlapping and orthogonal. i.e., axis-parallel. Our algorithm for strip packing has an absolute approximation ratio of 1.9396 and is the first, algorithm to break the approximation ratio of 2 which was established more than a decade ago. Moreover we present, a polynomial time approximation scheme (PTAS) For strip packing where rotations by 90 degrees are permitted and an algorithm for two-dimensional bin packing with an absolute worst-case ratio of 2, which is optimal provided P not equal NP.

关键词： two-dimensional bin packing strip packing rectangle packing approximation algorithm absolute worst-case ratio

来源：评论

学校读者我要写书评

暂无评论

Approximate Capacity Subregions of Uniform Multihop Wireless Networks

Approximate Capacity Subregions of Uniform Multihop Wireless...

引用

2010 Proceedings IEEE INFOCOM

作者： Peng-Jun Wan Lixin Wang Ai Huang Minming Li Frances Yao Department of Computer Science Illinois Institute of Technology Department of Computer Science City University of Hong Kong

ISBN: (纸本)9781424458363

The capacity region of multihop wireless network is involved in many capacity optimization problems. However, the membership of the capacity region is NP-complete in general, and hence the direct application of capacity region is quite limited. As a compromise, we often substitute the capacity region with a polynomial approximate capacity subregion. In this paper, we construct polynomial mu-approximate capacity subregions of multihop wireless network under either 802.11 interference model or protocol interference model in which all nodes have uniform communication radii normalized to one and uniform interference radii rho >= 1. The approximation factor mu decreases with rho in general and is smaller than the best-known ones in the literature. For example, mu velence 3 when rho >= 2.2907 under the 802.11 interference model or when rho >= 4.2462 under the protocol interference model. Our construction exploits a nature of the wireless interference called strip-wise transitivity of independence discovered in this paper and utilize the independence polytopes of cocomparability graphs in a spatial-divide-conquer manner. We also apply these polynomial mu-approximate capacity subregions to compute mu-approximate solutions for maximum (concurrent).

关键词： Capacity region maximum (concurrent) multi-flows approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Finding the longest common subsequence for multiple biological sequences by ant colony optimization

引用

COMPUTERS & OPERATIONS RESEARCH 2009年第1期36卷 73-91页

作者： Shyu, Shyong Jian Tsai, Chun-Yuan Taipei Municipal Univ Educ Dept Comp Sci Taipei 100 Taiwan Ming Chuan Univ Dept Comp Sci & Informat Engn Tao Yuan 333 Taiwan

Finding the longest common subsequence (LCS) for a set of n (an arbitrary n > 2) sequences is an Np-hard problem. It is an essential operation for a wide range of applications in the areas of computational biology, pattern recognition, string editing and data compression, to name a few. In this paper, we design a novel ant colony optimization (ACO) algorithm to find the approximate solution to the LCS problem for multiple biological sequences. The performances of our ACO algorithm, the known expansion algorithm [Bonizzoni P, Vedova GD, Mauri G. Experimenting an approximation algorithm for the LCS. Discrete Applied Mathematics 200 1;110: 13-24] and best next for maximal available symbol algorithm [Huang KS, Yang CB, Tseng KT. Fast algorithms for finding the common subsequence of multiple sequences. In: Proceedings of international computer symposium;2004. p. 90-95] were tested and compared by using various sets of DNA and protein sequences. The experimental results demonstrate the effectiveness and efficiency of the proposed ACO algorithm in dealing with the LCS problem for multiple biological sequences. (C) 2007 Elsevier Ltd. All rights reserved.

关键词： Longest common subsequence Ant colony optimization Meta-heuristics approximation algorithm Biological sequence

来源：评论

学校读者我要写书评

暂无评论

Data Gathering Schedule for Minimal Aggregation Time in Wireless Sensor Networks

引用

INTERNATIONAL JOURNAL OF DISTRIBUTED SENSOR NETWORKS 2009年第4期5卷 321-337页

作者： Chen, Xujin Hu, Xiaodong Zhu, Jianming Chinese Acad Sci Inst Appl Math Beijing 100080 Peoples R China

Data aggregation promises a new paradigm for gathering data via collaboration among wireless sensors deployed over a large geographical region. Many real-time applications impose stringent delay requirements and ask for time-efficient schedules of data gathering in which data sensed at sensors are aggregated at intermediate sensors along the way towards the data sink. The Minimal Aggregation Time (MAT) problem is to find the schedule that routes data appropriately and has the shortest time for all requested data to be aggregated and sent to the data sink. In this article we consider the MAT problem with collision-free transmission where a sensor can not receive any data if more than one sensors within its transmission range send data at the same time. We first prove that the MAT problem is NP-hard even if all sensors are deployed on a grid. We then propose a ( - 1)-approximation algorithms for the MAT problem, where is the maximum number of sensors within the transmission range of any sensor. By exploiting the geometric nature of wireless sensor networks, we obtain some better theoretical results for some special cases. We also simulate the proposed algorithm. The numerical results show that our algorithm has much better performance in practice than the theoretically proved guarantees and outperforms other existing algorithms.

关键词： Wireless Sensor Networks Data Aggregations Convergecast Collision-free Transmission Unit Disk Graphs approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Stochastic Mixed Integer Nonlinear Programming Using Rank Filter and Ordinal Optimization

引用

AICHE JOURNAL 2009年第11期55卷 2873-2882页

作者： Wen, Chengtao Ydstie, B. Erik Ma, Xiaoyan Carnegie Mellon Univ Dept Chem Engn Pittsburgh PA 15213 USA Carnegie Mellon Univ Heinz Coll Pittsburgh PA 15213 USA

A rank filter algorithm is developed to cope with the computational-difficulty in solving stochastic mixed integer nonlinear programming (SMINLP) problems. The proposed approximation method estimates the expected performance values, whose relative rankforms a subset of good solutions with high probability. Suboptimal solutions are obtained by searching the subset using the accurate performances. High-computational efficiency is achieved, because the accurate performance is limited to a small subset of the search space. Three benchmark problems show that the rank filter algorithm can reduce computational expense by several orders of magnitude without signify icant loss of precision. The rank filter algorithm presents an efficient approach for solving the large-scale SMINLP problems that are nonconvex, highly combinatorial, and strongly nonlinear. (C) 2009 American Institute of Chemical Engineers AIChE J, 55: 2873-2882, 2009

关键词： stochastic programming MINLP optimization rank filter algorithm ordinal optimization approximation algorithm process system synthesis

来源：评论

学校读者我要写书评

暂无评论

Transporting Jobs Through a Two-Machine Open Shop

引用

NAVAL RESEARCH LOGISTICS 2009年第1期56卷 1-18页

作者： Lushchakova, Irina N. Soper, Alan J. Strusevich, Vitaly A. Belarusian State Univ Informat & Radioelect Minsk 220027 BELARUS Univ Greenwich Sch Comp & Math Sci Old Royal Naval Coll London SE10 9LS England

We consider the two-machine open shop scheduling problem in which the jobs are brought to the system by a single transporter and moved between the processing machines by the same transporter. The purpose is to split the jobs into batches and to find the sequence of moves of the transporter so that the time by which the completed jobs are collected together on board the transporter is minimal. We present a 7/5-approximation algorithm. (C) 2008 Wiley Periodicals, Inc. Naval Research Logistics 56: 1-18, 2009

关键词： scheduling with transportation open shop approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Power Assignment for Symmetric Communication in Wireless Sensor Networks

引用

INTERNATIONAL JOURNAL OF DISTRIBUTED SENSOR NETWORKS 2009年第2期5卷 185-200页

作者： Park, Joongseok Sahni, Sartaj Univ Florida Gainesville FL 32611 USA

We show that two incremental power heuristics for power assignment in a wireless sensor network have an approximation ratio 2. Enhancements to these heuristics are proposed. It is shown that these enhancements do not reduce the approximation ratio of the considered incremental power heuristics. However, experiments conducted by us indicate that the proposed enhancements reduce the power cost of the assignment on average. Further, the two-edge switch enhancements reduce the power-cost reduction (relative to using minimum cost spanning trees) that is, on average, twice as much as obtainable from any of the heuristics proposed earlier.

关键词： Power Assignment Symmetric Connectivity Wireless Sensor Networks approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：