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

11th International Symposium and Workshops on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt)

作者： Gorain, Barun Mandal, Partha Sarathi Indian Inst Technol Guwahati Dept Math Gauhati 781039 India

ISBN: (纸本)9781612848242

Sweep coverage term is recently introduced for coverage in wireless sensors networks. The criteria for sweep coverage is different from the traditional coverage problem where a continus monitoring with sensor nodes is required. But in sweep coverage, periodic monitoring is sufficient with a small number of mobile sensor nodes. Finding minimum number of mobile sensor nodes with a constant velocity to guarantee sweep coverage is NP-hard and it cannot be approximated within a factor of 2 [11]. In this paper we have proposed a 2-approximation algorithm for solving the sweep coverage for a given set of points of interest (PoI). The best known approximation factor is 3 for this problem. [11]. When all PoI are static sensor noes, we have proposed a distributed approximation algorithm with number of mobile nodes and their positions. We have introduced sweep coverage for a given area of interest (AoI) and proved that the problem is NP-complete. A 2 root 2-approximation algorithm is proposed in order to solve the problem for a square region. A generalized version of the area sweep coverage problem for an arbitrary bounded region is also investigated in this paper.

关键词： Coverage approximation algorithm Mobile Sensor MST Euler tour TSP Wireless Networks

来源：评论

学校读者我要写书评

暂无评论

Systems of Distant Representatives in Euclidean Space

Systems of Distant Representatives in Euclidean Space

引用

29th Annual Symposium on Computational Geometry (SoCG)

作者： Dumitrescu, Adrian Jiang, Minghui Univ Wisconsin Dept Comp Sci Milwaukee WI 53201 USA Utah State Univ Dept Comp Sci Logan UT 84322 USA

ISBN: (纸本)9781450320313

Given a finite family of sets, Hall's classical marriage theorem provides a necessary and sufficient condition for the existence of a system of distinct representatives for the sets in the family. Here we extend this result to a geometric setting: given a finite family of objects in the Euclidean space (e.g., convex bodies), we highlight a sufficient condition for the existence of a system of distinct representatives for the objects that are also distant from each other. For a wide variety of geometric objects, this sufficient condition is also necessary in an asymptotic sense (i.e., apart from constant factors, the inequalities are best possible). Our methods are constructive and lead to efficient algorithms for computing such representatives.

关键词： Systems of distinct representatives Lebesgue measure lattice packing lattice covering bipartite matching approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Parallel algorithm for 2D Square Packing 14

A Parallel Algorithm for 2D Square Packing

引用

14th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT)

作者： Zhao, Xiaofan Shen, Hong Beijing Jiaotong Univ Sch Comp & Informat Technol Beijing Peoples R China Univ Adelaide Sch Comp Sci Adelaide SA 5005 Australia

ISBN: (纸本)9781479924189

We focus on the parallelization of two-dimensional square packing problem. In square packing problem, a list of square items need to be packed into a minimum number of unit square bins. All square items have side length smaller than or equal to 1 which is also the side length of each unit square bin. The total area of items that has been packed into one bin cannot exceed 1. Using the idea of harmonic, some squares can be put into the same bin without exceeding the bin limitation of side length 1. We try to concurrently pack all the corresponding squares into one bin by a parallel systerm of computation processing. A 9/4-worst case asymptotic error bound algorithm with time complexity Theta(n) is showed. Let OPT(I) and A(I) denote, respectively, the cost of an optimal solution and the cost produced by an approximation algorithm A for an instance I of the square packing problem. The best upper bound of on-line square packing to date is 2.1439 proved by Han et al. [23] by using complexity weighting functions. However the upper bound of our parallel algorithm is a litter worse than Han's algorithm, the analysis of our algorithm is more simple and the time complexity is improved. Han's algorithm needs O(nlogn) time, while our method only needs Theta(n) time.

关键词： parallel bin packing two-dimensional square packing upper bound approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Multiple Research Problems Based on Graph and Network Analysis

Multiple Research Problems Based on Graph and Network Analys...

引用

3rd International Conference on Consumer Electronics, Communications and Networks (CECNet)

作者： Xu, Yonglin North Western Minor Univ Math & Comp Coll Lanzhou Gansu Peoples R China

ISBN: (纸本)9781479928606

Dijkstra algorithm, under different constraints, starting from Zhengzhou, research visits to capital cities and municipalities in the country after he returned to the starting point of the optimal path of Zhengzhou. and use approximation algorithms to find approximate optimal solution. The path of the weighted graph problem definition of a balanced group to measure the degree of grouping of the balance.

关键词： best circuit problems Hamilton circuit weighted graph approximation algorithm balanced degrees

来源：评论

学校读者我要写书评

暂无评论

Mining Discrete Patterns via Binary Matrix Factorization

Mining Discrete Patterns via Binary Matrix Factorization

引用

IEEE 13th International Conference on Data Mining (ICDM)

作者： Jiang, Peng Heath, Michael T. Univ Illinois Dept Comp Sci Urbana IL 61801 USA

ISBN: (纸本)9780769551098

In general, binary matrix factorization (BMF) refers to the problem of finding two binary matrices of low rank such that the difference between their matrix product and a given binary matrix is minimal. BMF is an important tool in mining discrete patterns for high-dimensional data. One approximate matrix factor finds the dominant patterns, and the other shows how the original patterns are represented by the dominant ones. The problem of determining the exact optimal solution is NP-hard. We show that BMF is closely related with k-means clustering and propose a clustering approach for BMF We prove that our approach has approximation ratio of 2. We further propose a randomized clustering algorithm that chooses k cluster centroids randomly based on preassigned probabilities to each point. The randomized clustering algorithm works well for large k. We experimentally demonstrate the nice theoretical properties of BMF on applications in pattern extraction and association rule mining.

关键词： Binary matrix factorization k-means clustering approximation algorithm pattern extraction association rule mining

来源：评论

学校读者我要写书评

暂无评论

An Estimation of Distribution algorithm for Steiner Tree Problem

An Estimation of Distribution Algorithm for Steiner Tree Pro...

引用

15th IEEE International Conference on High Performance Computing and Communications (HPCC) /11th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing (EUC)

作者： Wang, Yaqing Wang, Hua Kong, Guohong Shandong Univ Sch Comp Sci & Technol Jinan 250100 Shandong Peoples R China

ISBN: (纸本)9780769550886

As one of the most well-known combinatorial optimization problems, Steiner tree problem is widely applied to optimization in transportation design, biological engineering, and communication networks. It has been proved to be NP complete, though. To solve this problem, researchers have provided many classic solutions. This paper proposes a new method of solving Steiner tree problem by using estimation of distribution algorithms (EDA). The basic idea is to initialize randomly n trees which contain the source node and the destination nodes. Some elites are selected by the selection operator. The algorithm then constructs a probabilistic model which attempts to estimate the probability distribution of the selected elites. Once the model is constructed, new trees are generated by sampling the distribution encoded by this model. These new trees are then incorporated back into the old population, possibly replacing it entirely. The process is repeated until some termination criteria are met. The algorithm constantly evolves trees to obtain a better solution tree with EDA ideas. This method leads to better performance, reduced time complexity, and optimized solution. Simulation results also show that the algorithm has better performance in searching and converging.

关键词： Steiner Tree estimation distribution algorithm approximation algorithm intelligence optimization probabilistic model

来源：评论

学校读者我要写书评

暂无评论

Cuts and partitions in graphs/trees with applications

Cuts and partitions in graphs/trees with applications

引用

作者： Fan, Jia-Hao Texas A&M University

学位级别：Ph.D.

Both the maximum agreement forest problem and the multicut on trees problem are NP-hard, thus cannot be solved efficiently if P ≠ NP. The maximum agreement forest problem was motivated in the study of evolution trees in bioinformatics, in which we are given two leaf-labeled trees and are asked to find a maximum forest that is a subgraph of both trees. The multicuton trees problem has applications in networks, in which we are given a forest and a set of pairs of termianls and are asked to find a cut that separates all pairs of terminals. We develop combinatorial and algorithmic techniques that lead to improved parameterized algorithms, approximation algorithms, and kernelization algorithms for these problems. For the maximum agreement forest problem, we proceed from the bottommost level of trees and extend solutions to whole trees. With this technique, we show that the maximum agreement forest problem is fixed-parameterized tractable in general trees, resolving an open problem in this area. We also provide the first constant ratio approximation algorithm for the problem in general trees. For the multicut on trees problem, we take a new look at the problem through the eyes of vertex cover problem. This connection allows us to develop an kernelization algorithm for the problem, which gives an upper bound of O(k3) on the kernel size, significantly improving the previous best upper bound O( k6). We further exploit this connection to give a parameterized algorithm for the problem that runs in time O* (1.62k), thus improving the previous best algorithm of running time O*(2k). In the protein complex prediction problem, which comes directly from the study of bioinformatics, we are given a protein-protein interaction network, and are asked to find dense regions in this graph. We formulate this problem as a graph clustering problem and develop an algorithm to refine the results for identifying protein complexes. We test our algorithm on yeast protein- protein interaction netwo

关键词： parameterized algorithm approximation algorithm polynomial kernel bioinformatics maximum agreement forest multicut on trees protein complex prediction Thesis

来源：评论

学校读者我要写书评

暂无评论

Approximating the k-Splittable Capacitated Network Design Problem

引用

39th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)

作者： Morsy, Ehab Nanyang Technol Univ Div Math Sci Singapore 637371 Singapore Suez Canal Univ Dept Math Ismailia 22541 Egypt

ISBN: (纸本)9783642358432

We consider the k-splittable capacitated network design problem (kSCND) in a graph G = (V, E) with edge weight w(e) >= 0, e is an element of E. We are given a vertex s is an element of V designated as a sink, a cable capacity lambda > 0, and a source set S subset of V with demand q(v) >= 0, v is an element of S. For any edge e is an element of E, we are allowed to install an integer number h(e) of copies of e. The kSCND asks to simultaneously send demand q(v) from each source v is an element of S along at most k paths to the sink s. A set of such paths can pass through a single copy of an edge in G as long as the total demand along the paths does not exceed the cable capacity lambda. The objective is to find a set P of paths of G that minimizes the installing cost Sigma(e is an element of Eh)(e)w(e). In this paper, we propose a ((k + 1)/ k + rho(ST))-approximation algorithm to the kSCND, where rho(ST) is any approximation ratio achievable for the Steiner tree problem.

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

来源：评论

学校读者我要写书评

暂无评论

On the low-dimensional Steiner minimum tree problem in Hamming metric

On the low-dimensional Steiner minimum tree problem in Hammi...

引用

8th Meeting on Theory and Applications of Models of Computation (TAMC)

作者： Althaus, Ernst Kupilas, Joschka Naujoks, Rouven Johannes Gutenberg Univ Mainz Inst Informat D-55128 Mainz Germany Max Planck Inst Informat D-66123 Saarbrucken Germany

While it is known that the d-dimensional Steiner minimum tree problem in Hamming metric is NP-complete if d is part of the input, it is an open question whether this also holds for fixed dimensions. In this paper, this question is answered by showing that the Steiner minimum tree problem in Hamming metric is already NP-complete in 3 dimensions. Furthermore, we show that, the minimum spanning tree gives a 2 - 2/d approximation on the Steiner minimum tree for d >= 2. Using this result, we analyse the so-called k-LCA and A(k) approximation algorithms and show improved approximation guarantees for low dimensions. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Steiner minimum tree Hamming metric Steiner ratio approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm for minimizing total latency in machine scheduling with deliveries

引用

DISCRETE OPTIMIZATION 2008年第1期5卷 97-107页

作者： Levin, Asaf Penn, Michal Hebrew Univ Jerusalem Dept Stat IL-91905 Jerusalem Israel Technion Israel Inst Technol Fac Ind Engn & Management IL-32000 Haifa Israel

We study the problem Of MINIMIZING TOTAL LATENCY IN MACHINE SCHEDULING WITH DELIVERIES, which is defined as follows. There is a set of n jobs to be processed by a single machine at a plant, where job J(i) is associated with its processing time and a customer i located at location i to which the job is to be delivered. In addition, there is a single uncapacitated delivery vehicle available. All jobs (vehicle) are available for processing (delivery) at time 0. Our aim is to determine the sequence in which the jobs should be processed in the plant, the departure times of the vehicle from the plant, and the routing of the vehicle, so as to minimize the total latency (job delivery time). We present a 6e similar to 16.309691-approximation algorithm for the problem. (C) 2007 Elsevier B.V. All rights reserved.

关键词： minimum latency scheduling approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：