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

Unicast and Broadcast Throughput Maximization in Amplify-and-Forward Relay Networks

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2012年第6期61卷 2768-2776页

作者： Li, Peng Guo, Song Xiang, Yong Jin, Hai Univ Aizu Sch Comp Sci & Engn Aizu Wakamatsu Fukushima 9658580 Japan Deakin Univ Sch Informat Technol Burwood Vic 3125 Australia Huazhong Univ Sci & Technol Serv Comp Technol & Syst Lab Cluster & Grid Comp Lab Sch Comp Sci & Technol Wuhan 430074 Peoples R China

Cooperative communication (CC) offers an efficient and low-cost way to achieve spatial diversity by forming a virtual antenna array among single-antenna nodes that cooperatively share their antennas. It has been well recognized that the selection of relay nodes plays a critical role in the performance of CC. Most existing relay selection strategies focus on optimizing the outage probability or energy consumption. To fill in the vacancy of research on throughput improvement via CC, we study the relay selection problem with the objective of optimizing the throughput in this paper. For unicast, it is a P problem, and an optimal relay selection algorithm is provided with a correctness proof. For broadcast, we show the challenge of relay selection by proving it nonprobabilistic hard (NP-hard). A greedy heuristic algorithm is proposed to effectively choose a set of relay nodes that maximize the broadcast throughput. Simulation results show that the proposed algorithms can achieve high throughput under various network settings.

关键词： approximation algorithm cooperative communication throughput maximization wireless relay network

来源：评论

学校读者我要写书评

暂无评论

A Deterministic Reduction for the Gap Minimum Distance Problem

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2012年第11期58卷 6935-6941页

作者： Cheng, Qi Wan, Daqing Univ Oklahoma Sch Comp Sci Norman OK 73019 USA Univ Calif Irvine Dept Math Irvine CA 92697 USA

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 be NP-complete by Vardy. The gap version of the problem was shown to be NP-hard for any constant factor under a randomized reduction in an earlier work. 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 time 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 given 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 the projection at the first s coordinates sends the codewords in the ball surjectively 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.

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

来源：评论

学校读者我要写书评

暂无评论

Linear programming based approximation algorithms for feedback set problems in bipartite tournaments

引用

THEORETICAL COMPUTER SCIENCE 2011年第23期412卷 2556-2561页

作者： van Zuylen, Anke Tsinghua Univ Inst Theoret Comp Sci Beijing 100084 Peoples R China

We consider the feedback vertex set and feedback arc set problems on bipartite tournaments. We improve on recent results by giving a 2-approximation algorithm for the feedback vertex set problem. We show that this result is the best that we can attain when using optimal solutions to a certain linear program as a lower bound on the optimal value. For the feedback arc set problem on bipartite tournaments, we show that a recent 4-approximation algorithm proposed by Gupta (2008) [8] is incorrect. We give an alternative 4-approximation algorithm based on an algorithm for the feedback arc set on (non-bipartite) tournaments given by van Zuylen and Williamson (2009) [14]. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Feedback vertex set Feedback arc set Bipartite tournament approximation algorithm Linear programming

来源：评论

学校读者我要写书评

暂无评论

On Maximizing Delay-Constrained Coverage of Urban Vehicular Networks

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2012年第4期30卷 804-817页

作者： Zhu, Yanmin Bao, Youchen Li, Bo Shanghai Jiao Tong Univ Dept Comp Sci & Engn Shanghai Peoples R China Shanghai Key Lab Scalable Comp & Syst Shanghai Peoples R China Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Kowloon Hong Kong Peoples R China

The success of a real-time sensing application with a vehicular network highly depends on the spatiotemporal coverage of sensing data that can be collected from the vehicular network. Deploying broadband wireless base stations is an effective way to collect vehicular sensing data and the deployment of base stations has a great impact on delay-constrained coverage. This paper considers the critical problem of base stations for maximizing delay-constrained coverage of an urban area achieved by the vehicular network. This is particularly challenging. We theoretically prove that the optimal deployment of base stations is NP-hard even when the future vehicular traces are assumed as a priori. In a realistic setting, however, the future vehicular traces cannot be known in advance. Therefore, the challenge is to incorporate high vehicle mobility and compute the base station deployment for maximizing the expected delay-constrained coverage. By mining a large dataset of real vehicular GPS traces, we show that there is strong regularity with vehicle mobility. With this important observation, we formulate a new objective of maximizing the expected sensing coverage. This takes random vehicle mobility into account and exploits the regularity in vehicle mobility. We develop greedy algorithms for base station deployment. The achieved sensing coverage of the proposed algorithm is guaranteed to be larger than (1 - 1/e) of the theoretical optimum. We have performed extensive simulations based on the real vehicular GPS trace dataset and conclusive results show that our algorithms achieve near optimal coverage of the urban area and significantly outperform alternative algorithms.

关键词： wireless vehicular networks broadband wireless base stations optimal deployment delay-constrained coverage approximation algorithm greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

Strong and weak edges of a graph and linkages with the vertex cover problem

引用

DISCRETE APPLIED MATHEMATICS 2012年第3期160卷 197-203页

作者： Han, Qiaoming Punnen, Abraham P. Simon Fraser Univ Dept Math Surrey BC V3T 5X3 Canada Zhejiang Univ Finance & Econ Sch Math & Stat Hangzhou 310018 Zhejiang Peoples R China

In this paper we show that the problem of identifying an edge (i,j) of a graph G such that there exists an optimal vertex cover S of G containing exactly one of the vertices i and j is NP-hard. Such an edge is called a weak edge. We then develop a polynomial time approximation algorithm for the vertex cover problem with performance guarantee 2 - 1/1+sigma, where sigma is an upper bound on a measure related to a weak edge of a graph. A related problem of identifying an edge (i, j) such that there exists an optimal vertex cover containing both vertices i and j is also shown to be NP-hard. Further, we discuss a new relaxation of the vertex cover problem which is used in our approximation algorithm to obtain smaller values of sigma. We also obtain linear programming representations of the vertex cover problem on special graphs. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Vertex cover problem approximation algorithm LP-relaxation Weak edge reduction NP-complete problems

来源：评论

学校读者我要写书评

暂无评论

A Novel Association Control Strategy for Supporting Multiple Multicast Sessions in WLANs

引用

IEEE COMMUNICATIONS LETTERS 2012年第12期16卷 1933-1936页

作者： Song, Jian Chin, Kwan-Wu Univ Wollongong Sch Elect Comp & Telecommun Engn Wollongong NSW 2522 Australia

Multicast is an important service relied upon by many applications in Wireless Local Area Networks (WLANs), which unfortunately is limited by the subscribing station with the lowest data rate. A key approach to address this problem is to employ an association control strategy to ensure stations are organized in a manner that optimizes a given objective. To this end, this paper studies the NP-hard, Multiple Multicast Sessions (MMS) problem. It proposes a novel greedy algorithm that aims to minimize the average APs load. Simulation results show that our algorithm reduces the average APs load by up to 70.4% as compared to prior approaches.

关键词： WLANs multiple multicasts sessions approximation algorithm association control

来源：评论

学校读者我要写书评

暂无评论

Analysis of an approximate greedy algorithm for the maximum edge clique partitioning problem

引用

DISCRETE OPTIMIZATION 2012年第3期9卷 205-208页

作者： Punnen, Abraham P. Zhang, Ruonan Simon Fraser Univ Surrey Dept Math Surrey BC V3T 0A3 Canada

In this note, we show that if the maximum clique problem can be solved by a polynomial time delta-approximation algorithm, then the maximum edge clique partitioning problem (Max-ECP) can be solved by a polynomial time 2(p delta-1)/p-1 approximation algorithm for any fixed integer p >= 2. This improves the best known bound on the performance ratio of an approximation algorithm for Max-ECP problem and also corrects an error in an earlier work on the topic. (c) 2012 Elsevier B.V. All rights reserved.

关键词： Maximum clique Clique partition approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimum-Perimeter Intersecting Polygons

引用

algorithmICA 2012年第3期63卷 602-615页

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

Given a set S of segments in the plane, a polygon P is an intersecting polygon of S if every segment in S intersects the interior or the boundary of P. The problem MPIP of computing a minimum-perimeter intersecting polygon of a given set of n segments in the plane was first considered by Rappaport in 1995. This problem is not known to be polynomial, nor it is known to be NP-hard. Rappaport (Int. J. Comput. Geom. Appl. 5:243-265, 1995) gave an exponential-time exact algorithm for MPIP. Hassanzadeh and Rappaport (Proceedings of the 23rd International Workshop on algorithms and Data Structures, LNCS, vol. 5664, pp. 363-374, 2009) gave a polynomial-time approximation algorithm with ratio pi/2 approximate to 1.57. In this paper, we present two improved approximation algorithms for MPIP: a 1.28-approximation algorithm by linear programming, and a polynomial-time approximation scheme by discretization and enumeration. Our algorithms can be generalized for computing an approximate minimum-perimeter intersecting polygon of a set of convex polygons in the plane. From the other direction, we show that computing a minimum-perimeter intersecting polygon of a set of (not necessarily convex) simple polygons is NP-hard.

关键词： Convex polygon approximation algorithm Linear programming NP-hardness

来源：评论

学校读者我要写书评

暂无评论

A linear time algorithm for 7-coloring triangle-free hexagonal graphs

引用

INFORMATION PROCESSING LETTERS 2012年第14-15期112卷 567-571页

作者： Sparl, Petra Witkowski, Rafal Zerovnik, Janez Inst Math Phys & Mech Ljubljana Slovenia Univ Maribor Fac Org Sci SI-4000 Kranj Slovenia Adam Mickiewicz Univ Fac Math & Comp Sci Poznan Poland Univ Ljubljana Fac Mech Engn SI-1000 Ljubljana Slovenia

Given a graph G and p is an element of N, a proper n-[p]coloring is a mapping f : V (G) -> 2((1....,n)) such that vertical bar f(v)vertical bar = p for any vertex v is an element of V (G) and f(v) boolean AND (u) = (sic) for any pair of adjacent vertices u and v. An n-[p]coloring is a special case of a multicoloring. Finding a multicoloring of induced subgraphs of the triangular lattice (called hexagonal graphs) has important applications in cellular networks. In this article we provide an algorithm to find a 7-[3]coloring of triangle-free hexagonal graphs in linear time, without using the fourcolor theorem, which solves the open problem stated by Sau. Snarl and Zerovnik (2011) and improves the result of Sudeep and Vishwanathan (2005), who proved the existence of a 14-[6]coloring. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Graph algorithm approximation algorithm Multicoloring Frequency planning Hexagonal graph

来源：评论

学校读者我要写书评

暂无评论

Pricing Loss Leaders Can be Hard

引用

Journal of Computer Science & Technology 2012年第4期27卷 718-726页

作者：吴奕 IBM Almaden Research Center

Consider the problem of pricing n items under an unlimited supply with m single minded buyers, each of which is interested in at most k of the items. The goal is to price each item with profit margin p1,p2,... ,pn so as to maximize the overall profit. There is an O（k）-approximation algorithm by Balcan and Blum when the price on each item must be above its margin cost; i.e., each pi 〉 0. We investigate the above problem when the seller is allowed to price some of the items below their margin cost. It was shown by Balcan et al. that by pricing some of the items below cost, the seller could possibly increase the maximum profit by /2（logn） times. These items sold at low prices to stimulate other profitable sales are usually called ＂loss leader＂. It is unclear what kind of approximation guarantees are achievable when some of the items can be priced below cost. Understanding this question is posed as an open problem by Balcan and Blum. In this paper, we give a strong negative result for the problem of pricing loss leaders . We prove that assuming the Unique Games Conjecture （UGC）, there is no constant approximation algorithm for item pricing with prices below cost allowed even when each customer is interested in at most three items. Conceptually, our result indicates that although it is possible to make more money by selling some items below their margin cost, it can be computationally intractable to do so.

关键词： complexity theory game theory approximation algorithm Unique Games Conjecture

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：