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

A PTAS FOR MINIMUM d-HOP UNDERWATER SINK PLACEMENT PROBLEM IN 2-D UNDERWATER SENSOR NETWORKS

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS 2009年第2期1卷 283-289页

作者： Wang, Wei Kim, Donghyun Sohaee, Nassim Ma, Changcun Wu, Weili Xi An Jiao Tong Univ Dept Math Xian 710049 Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75083 USA Tsinghua Univ Dept Comp Sci Beijing 100084 Peoples R China

The multiple UnderWater Sink (UW-Sink) architecture is introduced to resolve the scalability problem in USNs. To maximize the benefit of this architecture, the UW-Sinks should be located carefully. Previously, we proposed Minimum d-Hop UW-Sink Placement Problem (MdHUWSPP) for time-sensitive applications, whose objective is minimizing the number of UW-Sinks which d-hop dominate a given USN. In this paper, we present a PTAS for MdHUWSPP. We introduce an algorithm to partition an input graph representing the USN, find local optimum solutions, and return the union of the local solutions. Later, we use this algorithm with the shifting technique to have a PTAS for MdHUWSPP.

关键词： polynomial time approximation scheme underwater sensor networks network center placement problem

来源：评论

学校读者我要写书评

暂无评论

On PTAS for the Geometric Maximum Connected k-Factor Problem 1

引用

10th International Conference on Optimization and Applications (OPTIMA)

作者： Gimadi, Edward Rykov, Ivan Tsidulko, Oxana Sobolev Inst Math 4 Acad Koptyug Ave Novosibirsk 630090 Russia Novosibirsk State Univ Dept Mech & Math 1 Pirogova St Novosibirsk 630090 Russia

ISBN: (数字)9783030386030

ISBN: (纸本)9783030386030;9783030386023

We consider the Connected k-factor problem (k-CFP): given a complete edge-weighted n-vertex graph, the goal is to find a connected k-regular spanning subgraph of maximum or minimum total weight. The problem is called geometric, if the vertices of a graph correspond to a set of points in a normed space Rd and the weight of an edge is the distance between its endpoints. The k-CFP is a natural generalization of the well-known Traveling Salesman Problem, which is equivalent to the 2-CFP. In this paper we complement the known (1- 1/k(2))-approximation algorithm for the maximum k-CFP from [Baburin et al., 2007] with an approximation algorithm for the geometric k-CFP, that guarantees a relative error epsilon = O ( (k/n)(1/(d+2))). Together these two algorithms form an asymptotically optimal algorithm for the geometric k-CFP with an arbitrary value of k in an arbitrary normed space of fixed dimension d. Finally, the asymptotically optimal algorithm can be easily transformed into a PTAS for the considered geometric problem.

关键词： Asymptotically optimal algorithm polynomial time approximation scheme Connected k-factor problem Normed space NP-hard problem

来源：评论

学校读者我要写书评

暂无评论

A PTAS for the sparsest 2-spanner of 4-connected planar triangulations

引用

Journal of Discrete Algorithms 2003年第1期1卷 67-76页

作者： Duckworth, William Wormald, Nicholas C. Zito, Michele Department of Mathematics and Statistics University of Melbourne Parkville VIC 3052 Australia Department of Computer Science University of Liverpool Liverpool L69 7ZF United Kingdom

A t-spanner of an undirected, unweighted graph G is a spanning subgraph S of G with the added property that for every pair of vertices in G, the distance between them in S is at most t times the distance between them in G. We are interested in finding a sparsest t-spanner, i.e., a t-spanner with the minimum number of edges. In the general setting, this problem is known to be NP-hard for all t ≥ 2. For t ≥ 5, the problem remains NP-hard for planar graphs, whereas for t ∈ {2, 3, 4}, the complexity of this problem on planar graphs is still unknown. In this paper we present a polynomial time approximation scheme for the problem of finding a sparsest 2-spanner of a 4-connected planar triangulation. © 2003 Elsevier B.V. All rights reserved.

关键词： 2-spanner 4-connected Planar polynomial time approximation scheme Triangulation

来源：评论

学校读者我要写书评

暂无评论

Local Search Yields a PTAS for k-Means in Doubling Metrics 57

Local Search Yields a PTAS for k-Means in Doubling Me...

引用

57th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Friggstad, Zachary Rezapour, Mohsen Salavatipour, Mohammad R. Univ Alberta Dept Comp Sci Edmonton AB T6G 2M7 Canada

ISBN: (纸本)9781509039333

The most well known and ubiquitous clustering problem encountered in nearly every branch of science is undoubtedly k-MEANS: given a set of data points and a parameter k, select k centres and partition the data points into k clusters around these centres so that the sum of squares of distances of the points to their cluster centre is minimized. Typically these data points lie in Euclidean space R-d for some d >= 2. k-MEANS and the first algorithms for it were introduced in the 1950's. Over the last six decades, hundreds of papers have studied this problem and different algorithms have been proposed for it. The most commonly used algorithm in practice is known as Lloyd-Forgy, which is also referred to as "the" k-MEANS algorithm, and various extensions of it often work very well in practice. However, they may produce solutions whose cost is arbitrarily large compared to the optimum solution. Kanungo et al. [2004] analyzed a very simple local search heuristic to get a polynomial-time algorithm with approximation ratio 9+epsilon for any fixed epsilon > 0 for k-MEANS in Euclidean space. Finding an algorithm with a better worstcase approximation guarantee has remained one of the biggest open questions in this area, in particular whether one can get a true PTAS for fixed dimension Euclidean space. We settle this problem by showing that a simple local search algorithm provides a PTAS for k-MEANS for R-d for any fixed d. More precisely, for any error parameter epsilon > 0, the local search algorithm that considers swaps of up to rho = d(O(d)) . epsilon(-O(d/epsilon)) centres at a time will produce a solution using exactly k centres whose cost is at most a (1+epsilon)-factor greater than the optimum solution. Our analysis extends very easily to the more general settings where we want to minimize the sum of q'th powers of the distances between data points and their cluster centres (instead of sum of squares of distances as in k-MEANS) for any fixed q >= 1 and where the metric m

关键词： clustering k-means approximation Euclidean polynomial time approximation scheme doubling metric

来源：评论

学校读者我要写书评

暂无评论

polynomial approximation schemeS FOR THE MAX-MIN ALLOCATION PROBLEM UNDER A GRADE OF SERVICE PROVISION

引用

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS 2009年第3期1卷 355-368页

作者： Li, Jianping Li, Weidong Li, Jianbo Yunnan Univ Dept Math Kunming 650091 Peoples R China Kunming Univ Sci & Technol Sch Management & Econ Kunming 650031 Peoples R China

The max-min allocation problem under a grade of service provision is defined in the following model: given a set M of m parallel machines and a set J of n jobs, where machines and jobs are all entitled to different levels of grade of service (GoS), each job J(j). J has its processing time p(j) and it can only be allocated to a machine M-i whose GoS level is no more than the GoS level the job J(j) has. The goal is to allocate all jobs to m machines to maximize the minimum machine load among these m machines, where the machine load of Mi is the sum of the processing time of jobs executed on Mi. The best known approximation algorithm [4] to solve this problem produces an allocation in which the minimum machine completion time is at least Omega (log log log m/log log m) of the optimal value. In this paper, we respectively present four approximation schemes to solve this problem and its two special versions: (1) a polynomial time approximation scheme (PTAS) with a running time O(mn (O)(1\epsilon(2))) for the general version, where epsilon > 0;(2) a PTAS and a fully polynomial time pproximation scheme (FPTAS) with the running time O(n) for the version where the number m of machines is fixed;(3) a PTAS with the running time O(n) for the version where the number of GoS levels is bounded by k.

关键词： Scheduling allocation grade of service polynomial time approximation scheme fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Efficient PTAS for the Euclidean Capacitated Vehicle Routing Problem with Non-uniform Non-splittable Demand 8th

Efficient PTAS for the Euclidean Capacitated Vehicle Routing...

引用

8th International Conference on Analysis of Images, Social Networks, and Texts (AIST)

作者： Khachay, Michael Ogorodnikov, Yuri Krasovsky Inst Math & Mech Ekaterinburg Russia Ural Fed Univ Ekaterinburg Russia Omsk State Tech Univ Omsk Russia

ISBN: (纸本)9783030373344;9783030373337

The Capacitated Vehicle Routing Problem (CVRP) is the well-known combinatorial optimization problem having numerous relevant applications in operations research. As known, CVRP is strongly NP-hard even in the Euclidean plane, APX-hard for an arbitrary metric, and can be approximated in polynomial time with any accuracy in the Euclidean spaces of any fixed dimension. In particular, for the several special cases of the planar Euclidean CVRP there are known polynomial time approximation schemes (PTAS) stemming from the seminal papers by M. Haimovich, A. Rinnooy Kan and S. Arora. Although, these results appear to be promising and make a solid contribution to the field of algorithmic analysis of routing problems, all of them are restricted to the special case of the CVRP, where all customers have splittable or even unit demand, which seems to be far from the practice. In this paper, to the best of our knowledge, we propose the first Efficient polynomial time approximation scheme (EPTAS) for this problem in the case of non-uniform non-splittable demand.

关键词： Capacitated Vehicle Routing Problem Non-splittable demand polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Delay-Constrained Throughput Maximization in UAV-Assisted VANETs 1

引用

13th International Conference on Wireless Algorithms, Systems, and Applications (WASA)

作者： Fan, Xiying Huang, Chuanhe Chen, Xi Wen, Shaojie Fu, Bin Wuhan Univ Comp Sch Wuhan 430072 Peoples R China Wuhan Univ Collaborat Innovat Ctr Geospatial Technol Wuhan 430072 Peoples R China Univ Texas Rio Grande Valley Dept Comp Sci Edinburg TX 78539 USA

ISBN: (数字)9783319942681

ISBN: (纸本)9783319942681;9783319942674

Efficient data dissemination in vehicular ad hoc networks (VANETs) is a challenging issue due to the high mobility of vehicles. We consider a novel mobile relaying technique by employing unmanned aerial vehicles (UAVs) to assist VANETs when the communication infrastructure is not available or network connectivity is poor. A throughput maximization problem with delay constraint is formulated to achieve high network throughput and guarantee real-time data dissemination. We reduce the graph knapsack problem to the throughput maximization problem, which is proved NP-hard. A polynomial time approximation scheme is proposed to solve the problem. Theoretical analysis that includes time complexity and approximation ratio of the algorithm is presented. The evaluation demonstrates the effectiveness of the proposed algorithm.

关键词： VANETs Data dissemination UAVs Throughput maximization polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

approximation Algorithms for a Two-Phase Knapsack Problem 1

引用

24th International Computing and Combinatorics Conference (COCOON)

作者： Nip, Kameng Wang, Zhenbo Sun Yat Sen Univ Sch Math Zhuhai Zhuhai Peoples R China Tsinghua Univ Dept Math Sci Beijing Peoples R China

ISBN: (数字)9783319947761

ISBN: (纸本)9783319947761;9783319947754

We consider a natural generalization of the knapsack problem and the multiple knapsack problem, which has two phases of packing decisions. In this problem, we have a set of items, several small knapsacks called boxes, and a large knapsack called container. Each item has a size and profit, each box has a size and the container has a capacity. The first phase is to select some items to pack into the boxes, and the second phase is to select the boxes (each includes some packed items) to pack into the container. The total profit of the problem is determined by the items that are selected and packed into the container within some packed box, and the objective is to maximize the total profit. This problem is motivated by various practical applications, e.g., in logistics. It is a generalization of the multiple knapsack problem, and hence is strongly NP-hard. We mainly propose three approximation algorithms for it. Particularly, the first one is a 1/4-approximation algorithm based on its linear programming relaxation;the second one is based on applying the algorithms for the multiple knapsack problem and the knapsack problem, and has an approximation ratio 1/3- epsilon for any small enough epsilon > 0. We finally provide a polynomial time approximation scheme for this problem.

关键词： Knapsack Multiple knapsack approximation algorithms polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

The Complexity of Channel Scheduling in Multi-Radio Multi-Channel Wireless Networks

The Complexity of Channel Scheduling in Multi-Radio Multi-Ch...

引用

IEEE INFOCOM Conference 2009

作者： Cheng, Wei Cheng, Xiuzhen Znati, Taieb Lu, Xicheng Lu, Zexin George Washington Univ Washington DC 20052 USA Univ Pittsburgh Comp Sci Pittsburgh PA 15260 USA Natl Univ Defense Technol Comp Sci Changsha 410073 Hunan Peoples R China

ISBN: (纸本)9781424435128

The complexity of channel scheduling in Multi-Radio Multi-Channel (MR-MC) wireless networks is an open research topic. This problem asks for the set of edges that can support maximum amount of simultaneous traffic over orthogonal channels under a certain interference model. There exist two major interference models for channel scheduling, with one under the physical distance constraint, and one under the hop distance constraint. The complexity of channel scheduling under these two interference models serves as the foundation for many problems related to network throughput maximization. However, channel scheduling was proved to be NP-Hard only under the hop distance constraint for SR-SC wireless networks. In this paper, we fill the void by proving that channel scheduling is NP-Hard under both models in MR-MC wireless networks. In addition, we propose a polynomial-time approximation scheme (PTAS) framework that is applicable to channel scheduling under both interference models in MR-MC wireless networks. Furthermore, we conduct a comparison study on the two interference models and identify conditions under which these two models are equivalent for channel scheduling.

关键词： Complexity Channel Scheduling Multi-Radio Multi-Channel Wireless Networks Maximum weight channel scheduling NP-Hard polynomial time approximation scheme PTAS

来源：评论

学校读者我要写书评

暂无评论

On the k-closest substring and k-consensus pattern problems

On the k-closest substring and k-consensus pat...

引用

15th Annual Symposium on Combinatorial Pattern Matching

作者： Jiao, YS Xu, JY Li, M Chinese Acad Sci Bioinformat Lab Comp Technol Inst Beijing Peoples R China

ISBN: (纸本)354022341X

Given a set S = {s(1), s(2), ..., s(n)} of strings each of length m, and an integer L, we study the following two problems. k-CLOSEST SUBSTRING problem: find k center strings c(1), c(2), ..., c(k) of length L minimizing d such that for each s(j) is an element of S, there is a length-L substring t(j) (closest substring) of s(j) with min(1less than or equal toiless than or equal tok) d(c(i), t(j)) less than or equal to d. We give a PTAS for this problem, for k = O(1). k-CONSENSUS PATTERN problem: find k median strings c(1), c(2), ..., c(k) of length L and a substring tj (consensus pattern) of length L from each s(j) minimizing the total cost w = Sigma(j=1)(n) min(1less than or equal toiless than or equal tok) d(c(i), t(j)). We give a PTAS for this problem, for k = O(1). Our results improve recent results of [10] and [16] both of which depended on the random linear transformation technique in [16]. As for general k case, we give an alternative and direct proof of the NP-hardness of (2-epsilon)-approximation of the HAMMING RADIUS k-CLUSTERING problem, a special case of the k-CLOSEST SUBSTRING problem restricted to L = m.

关键词： k-center problems closest string and substrings consensus pattern polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：