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

4th International Conference on Fun with algorithms

作者： Iwama, Kazuo Miyano, Eiji Ono, Hirotaka Kyushu Univ Dept Comp Sci & Commun Engn Fukuoka 8190395 Japan Kyoto Univ Sch Informat Kyoto 6068501 Japan Kyushu Inst Technol Dept Syst Design & Informat Fukuoka 8208502 Japan

ISBN: (纸本)9783540729136

A spreadsheet, especially MS Excel, is probably one of the most popular software applications for personal-computer users and gives us convenient and user-friendly tools for drawing tables. Using spreadsheets, we often wish to draw several vertical and horizontal black lines on selective gridlines to enhance the readability of our spreadsheet. Such situations we frequently encounter are formulated as the Border Drawing Problem (BDP). Given a layout of black line segments, we study how to draw it efficiently from an algorithmic view point, by using a set of border styles and investigate its complexity. (i) We first define a formal model based on MS Excel, under which the drawability and the efficiency of border styles are discussed, and then (ii) show that unfortunately the problem is NP-hard for the set of the Excel border styles and for any reasonable subset of the styles. Moreover, in order to provide potentially more efficient drawing, (iii) we propose a new compact set of border styles and show a necessary and sufficient condition of its drawability.

关键词： algorithm Combinatorial optimization Spreadsheet NP-hardness approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal Monitoring in Multi-Channel Multi-Radio Wireless Mesh Networks

Optimal Monitoring in Multi-Channel Multi-Radio Wireless Mes...

引用

10th ACM International Symposium on Mobile Ad Hoc Networking and Computing

作者： Shin, Dong-Hoon Bagchi, Saurabh Purdue Univ Sch Elect & Comp Engn Dependable Comp Syst Lab W Lafayette IN 47907 USA

ISBN: (纸本)9781605585314

Wireless mesh networks (WMN) are finding increasing usage in city-wide deployments for providing network connectivity. Mesh routers in WMNs typically use multiple wireless channels to enhance the spatial-reuse of frequency bands, often with multiple radios per node. Due to the cooperative nature of WMNs, they are susceptible to many attacks that cannot be defeated by using traditional cryptographic mechanisms of authentication or encryption alone. A solution approach commonly used for defending against such attacks is behavior-based detection in which some nodes overhear communication in their neighborhood to determine if the behavior by a neighbor is legitimate. It, has been proposed to use specialized monitoring nodes deployed strategically throughout the network for performing such detection. The problem that arises is where to deploy these monitoring nodes, how to minimize their number, and which channels to tune their radios to, such that the maximum part of the network can be covered. This problem has been solved for single channel networks by a greedy approximation algorithm since the exact solution is NP-hard. The greedy algorithm achieves the best performance, in terms of the worst case, possible among all polynomial-time algorithms provided that P not equal NP. In this paper, we solve the problem for multi-channel multi-radio WMNs. The intuitive extension of the greedy algorithm destroys the property of best performance. Instead, we formulate the problem as an integer linear program, solve its linear program relaxation, and then use two rounding techniques that we develop by adapting existing rounding schemes. We thereby present two approximation algorithms. The first, computationally-light algorithm, called probabilistic rounding algorithm gives an expected best performance in the worst case. The second, called deterministic rounding algorithm achieves the best worst-case performance in a deterministic manner. To evaluate how the three algorithms perform

关键词： Wireless Mesh Networks Multi-Channel Multi-Radio Wireless Networks Security Monitoring approximation algorithm LP Rounding

来源：评论

学校读者我要写书评

暂无评论

A Generalized Multi-organization Scheduling on Unrelated Parallel Machines

A Generalized Multi-organization Scheduling on Unrelated Par...

引用

10th International Conference on Parallel and Distributed Computing, Applications and Technologies

作者： Ooshita, Fukuhito Izumi, Tomoko Izumi, Taisuke Osaka Univ Grad Sch Informat Sci & Technol 1-5 Yamadaoka Suita Osaka 5650871 Japan Ritsumeikan Univ Coll Informat Sci & Engn Shiga 5258577 Japan Nagoya Inst Technol Grad Sch Engn Nagoya Aichi 4668555 Japan

ISBN: (纸本)9781424452910

We consider the parallel computing environment where m organizations provide machines and several jobs to be executed. While cooperation of organizations is required to minimize the global makespan, each organization also expects the faster completion of its own jobs primarily and thus it is not necessarily cooperative. To handle the situations, we formulate the alpha-cooperative multi-organization scheduling problem (alpha-MOSP), where alpha >= 1 is a parameter representing the degree of cooperativeness. alpha-MOSP minimizes the makespan under the cooperation constraint that each organization does not allow the completion time of its own jobs to be delayed alpha times of that in the case where those jobs are executed by itself. In this paper, we aim to reveal the relation between the makespan and the degree of cooperativeness. First, we investigate the relation between alpha and the quality of the global makespan. For alpha = 1 (i.e., each organization never sacrifices its completion time), we show an instance where the cooperation constraint degrades the optimal makespan by m times. In contrast, for alpha > 1, we can construct an algorithm transforming any unconstrained schedule to one satisfying the cooperation constraint. This algorithm bounds the degradation ratio by alpha/(alpha - 1), which implies that weak cooperation improves the makespan dramatically. Second, we study the complexity of alpha-MOSP. We show its strongly NP-hardness and inapproximability for the approximation factor less than max{(alpha 1)/alpha,3/2}. We also show the hardness of transformation: Even if an optimal schedule under no cooperation constraint is given, no polynomial-time algorithm finds an optimal schedule for a-MOSP. This result is a witness for inexistence of general polynomial-time transformation algorithms that preserve the approximation ratio.

关键词： heterogeneous parallel computing environments scheduling algorithm approximation algorithm computation complexity

来源：评论

学校读者我要写书评

暂无评论

MINIMUM CONNECTED r-HOP k-DOMINATING SET IN WIRELESS NETWORKS

引用

DISCRETE MATHEMATICS algorithmS AND APPLICATIONS 2009年第1期1卷 45-57页

作者： Li, Deying Liu, Lin Yang, Huiqiang Renmin Univ China MOE Key Lab Data Engn & Knowledge Engn Beijing Peoples R China Renmin Univ China Sch Informat Beijing Peoples R China

In this paper, we study the connected r-hop k-dominating set problem in wireless networks. We propose two algorithms for the problem. We prove that algorithm I for UDG has (2r + 1)(3) approximate ratio for k <= (2r + 1)(2) and (2r + 1)(( 2r + 1)(2) + 1)-approximate ratio for k > (2r + 1) (2). And algorithm II for any undirected graph has ( 2r + 1) ln(Delta(r)) approximation ratio, where Delta(r) is the largest cardinality among all r-hop neighborhoods in the network. The simulation results show that our algorithms are efficient.

关键词： r-hop dominating r-hop k-dominating set connected r-hop k-dominating set approximation algorithm wireless networks

来源：评论

学校读者我要写书评

暂无评论

Workload-Driven Compressed Skycube Queries in Wireless Applications

Workload-Driven Compressed Skycube Queries in Wireless Appli...

引用

4th International Conference on Wireless algorithms, Systems, and Applications

作者： Fang, Zheng Wang, Jie Zhang, Donghui Univ Massachusetts Dept Comp Sci Lowell MA 01854 USA Northeastern Univ Coll Comp & Informat Sci Boston MA 02115 USA

ISBN: (纸本)9783642034169

Compressed skycubes provide an efficient mechanism for skyline queries that are useful for wireless applications, where the size of a compressed skycube is often much smaller than that of the original skycube. However, even with compression, the entire compressed skycube may still be too large to be placed in the main memory of a wireless device. To overcome this obstacle we introduce the concept of workload-driven subspace compressed skycubes to meet the needs of an expected query profile. While it is NP-hard to find the best set of subspace compressed skycubes within the given memory constraint to serve the largest possible number of queries, we devise a polynomial-time approximation algorithms with a proven approximation guarantee. Our simulation results show that the approximation algorithm produces feasible solutions in reasonable amount of time with approximation ratios close to 1.

关键词： Compressed skycube approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Integral Estimation from Point Cloud in d-Dimensional Space: A Geometric View

Integral Estimation from Point Cloud in d-Dimensional Space:...

引用

25th Annual Symposium on Computational Geometry

作者： Luo, Chuanjiang Sun, Jian Wang, Yusu Ohio State Univ Dept Comp Sci & Engn Columbus OH 43210 USA

ISBN: (纸本)9781605585017

Integration over a domain, such as a Euclidean space or a Riemannian manifold, is a fundamental problem across scientific fields. Many times, the underlying domain is only accessible through a discrete approximation, such as a set of points sampled from it, and it is crucial to be able to estimate integral in such discrete settings. In this paper, we study the problem of estimating the integral of a function defined over a k-submanifold embedded in R-d. from its function values at a set of sample points. Previously, such estimation is usually obtained in a statistical setting, where input data is typically assumed to be drawn from certain probabilistic distribution. Our paper is the first to consider this important problem of estimating integral from point clouds data (PCD) under the more general non-statistical setting, and provide certain theoretical guarantees. Our approaches consider the problem from a geometric point of view. Specifically, we estimate the integral by computing a weighted sum, and propose two weighting schemes: the Voronoi and the Principal Eigenvector schemes. The running time of both methods depends mostly on the intrinsic dimension of the underlying manifold, instead of on the ambient dimensions. We show that the estimation based on the Voronoi scheme converges to the true integral under the so-called (epsilon, delta)-sampling condition with explicit error bound presented. This is the first result of this sort for estimating integral from general PCD. For the Principal Eigenvector scheme, although no theoretical guarantee is established, we present its connection to the Heat diffusion operator, and illustrate justifications behind its construction. Experimental results show that both new methods consistently produce more accurate integral estimations than common statistical methods under various sampling conditions.

关键词： Laplace-Beltrami operator approximation algorithm Point cloud data Data analysis

来源：评论

学校读者我要写书评

暂无评论

Minimum Energy Broadcast Routing in Ad Hoc and Sensor Networks with Directional Antennas

Minimum Energy Broadcast Routing in Ad Hoc and Sensor Networ...

引用

3rd International Conference on Combinatorial Optimization and Applications (COCOA 2009)

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

ISBN: (纸本)9783642020254

In this paper we discuss minimum energy broadcast routing with directional antennas in ad hoc and sensor networks. We assume that the network consists of sensor nodes whose antennas are Switched beam directional antennas. The problem of our concern is: given a set V with n nodes and each node nu(i) has l(i) transmission directions (i.e. the antenna sectors) and a broadcast request sourced at s, how to find a broadcast tree rooted at s and spanning all nodes in V such that the total energy is minimized. This problem involves with the choice of transmitting nodes and their transmission directions, which is NP-hard. We propose a vertical bar V vertical bar-approximation algorithm and one heuristic for the problem. Extensive simulations have demonstrated the efficiency of our algorithms.

关键词： ad hoc and sensor networks energy efficient broadcast directional antenna approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

PTAS for Geometric Hitting Set Problems via Local Search

PTAS for Geometric Hitting Set Problems via Local Search

引用

25th Annual Symposium on Computational Geometry

作者： Mustafa, Nabil H. Ray, Saurabh Lahore Univ Management Sci Lahore Pakistan

ISBN: (纸本)9781605585017

We consider the problem of computing minimum geometric hitting sets in which, given a set of geometric objects and a set of points, the goal is to compute the smallest subset of points that hit all geometric objects. The problem is known to be strongly NP-hard even for simple geometric objects like unit disks in the plane. Therefore, unless P=NP, it is not possible to get Fully Polynomial Time approximation algorithms (FPTAS) for such problems. We give the first PTAS for this problem when the geometric objects are half-spaces in R-3 and when they are an r-admissible set regions in the plane (this includes pseudo-disks as they are 2-admissible). Quite surprisingly, our algorithm is a very simple local search algorithm which iterates over local improvements only.

关键词： Hitting Sets Epsilon Nets Local Search approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Deterministic Reduction for the Gap Minimum Distance Problem

A Deterministic Reduction for the Gap Minimum Distance Probl...

引用

41st Annual ACM Symposium on Theory of Computing

作者： Cheng, Qi Wan, Daqing Univ Oklahoma Sch Comp Sci Norman OK 73019 USA

ISBN: (纸本)9781605586137

Determining the minimum distance of a linear code is one of the most important problems in algorithmic coding theory. The exact version of the problem was shown to the NP-complete in [14]. In [8], the gap version of the problem was shown to be NP-hard for any constant factor under a randomized reduction. It was shown in the same paper that the minimum distance problem is not approximable in randomized polynomial time to the factor 2(log1-epsilon n) unless NP subset of RTIME(2(polylog(n))). In this paper, we derandomize the reduction and thus prove that there is no deterministic polynomial time algorithm to approximate the minimum distance to any constant factor unless P = NP. We also prove that the minimum distance is not approximable in deterministic polynomial tome to the factor 2(log1-epsilon) n unless NP subset of DTIME (2(polylog(n))). As the main technical contribution, for any constant 2/3 < rho < 1, we present a deterministic algorithm that give a positive integer s, runs in time poly(s) and constructs a code C of length poly(s) with an explicit Hamming ball of radius rho d(C) such that a projection at some s coordinates sends the codewords in the ball subjectively onto a linear subspace of dimension s, where d(C) denotes the minimum distance of C. The codes are obtained by concatenating Reed-Solomon codes with Hadamard codes.

关键词： Coding theory NP-complete approximation algorithm minimum distance problem

来源：评论

学校读者我要写书评

暂无评论

Distance Constrained Facility Location Problem

Distance Constrained Facility Location Problem

引用

IITA International Conference on Services Science, Management and Engineering

作者： Weng, Kerui China Univ Geosci Sch Econ & Management Wuhan 430074 Peoples R China

ISBN: (纸本)9780769537290

The distance constrained facility location problem (DCFLP) seeks to the optimal way of locating facilities to minimize total costs (opening costs plus routing costs), while satisfying all the clients could be serviced by facilities within given distance. The paper first proposes a mixed 0-1 integer programming model for the DCFLP Then, we present a Inn+1 approximation algorithm to solve the problem. We also extend the model and algorithm to the distance constrained hub location problem which obtains a 21nn+1-approximation algorithm.

关键词： facility location service distance approximation algorithm hub location

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：