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

DISTRIBUTED COMPUTING 2010年第4期22卷 235-248页

作者： Halldorsson, Magnus M. Halpern, Joseph Y. Li, Li Erran Mirrokni, Vahab S. Reykjavik Univ Sch Comp Sci IS-101 Reykjavik Iceland Cornell Univ Dept Comp Sci Ithaca NY 14853 USA Bell Labs Alcatel Lucent Ctr Networking Res Murray Hill NJ 07974 USA Google Res Theory Grp New York NY USA

Efficient spectrum-sharing mechanisms are crucial to alleviate the bandwidth limitation in wireless networks. In this paper, we consider the following question: can free spectrum be shared efficiently? We study this problem in the context of 802.11 or WiFi networks. Each access point (AP) in a WiFi network must be assigned a channel for it to service users. There are only finitely many possible channels that can be assigned. Moreover, neighboring access points must use different channels so as to avoid interference. Currently these channels are assigned by administrators who carefully consider channel conflicts and network loads. Channel conflicts among APs operated by different entities are currently resolved in an ad hoc manner (i.e., not in a coordinated way) or not resolved at all. We view the channel assignment problem as a game, where the players are the service providers and APs are acquired sequentially. We consider the price of anarchy of this game, which is the ratio between the total coverage of the APs in the worst Nash equilibrium of the game and what the total coverage of the APs would be if the channel assignment were done optimally by a central authority. We provide bounds on the price of anarchy depending on assumptions on the underlying network and the type of bargaining allowed between service providers. The key tool in the analysis is the identification of the Nash equilibria with the solutions to a maximal coloring problem in an appropriate graph. We relate the price of anarchy of these games to the approximation factor of local optimization algorithms for the maximum k-colorable subgraph problem. We also study the speed of convergence in these games.

关键词： Game theory Nash equilibrium Price of anarchy Graph coloring approximation algorithm Unit disk graph

来源：评论

学校读者我要写书评

暂无评论

Disc Covering Problem with Application to Digital Halftoning

引用

THEORY OF COMPUTING SYSTEMS 2010年第2期46卷 157-173页

作者： Asano, Tetsuo Brass, Peter Sasahara, Shinji JAIST Sch Informat Sci Tatsunokuchi Ishikawa 9231292 Japan CUNY City Coll Dept Comp Sci New York NY 10031 USA Fuji Xerox Co Ltd Kanagawa 2590157 Japan

This paper considers the following geometric optimization problem: Input is a matrix R=(r (ij) ). Each entry r (ij) represents a radius of a disc with its center at (i,j) in the plane. We want to choose discs in such a way that the total area covered by exactly one disc is maximized. This problem is closely related to digital halftoning, a technique to convert a continuous-tone image into a binary image for printing. An exact algorithm is given for the one-dimensional version of the problem while approximation algorithms are given for the two-dimensional one. The approximation algorithms are verified to be satisfactory in practice through experiments in applications to digital halftoning.

关键词： approximation algorithm Computational geometry Digital halftoning Voronoi diagram

来源：评论

学校读者我要写书评

暂无评论

Minimizing the total weighted completion time in the relocation problem

引用

JOURNAL OF SCHEDULING 2010年第2期13卷 123-129页

作者： Kononov, Alexander V. Lin, Bertrand M. T. Natl Chiao Tung Univ Inst Informat Management Dept Informat & Finance Management Hsinchu 300 Taiwan Sobolev Inst Math Novosibirsk Russia Novosibirsk State Univ Novosibirsk 630090 Russia

This paper studies the minimization of total weighted completion time in the relocation problem on a single machine. The relocation problem, formulated from an area redevelopment project, can be treated as a resource-constrained scheduling problem. In this paper, we show four special cases to be NP-hard in the strong sense. Problem equivalence between the unit-weighted case and the UET (unit-execution-time) case is established. For two further restricted special cases, we present a polynomial time approximation algorithm and show its performance ratio to be 2.

关键词： Relocation problem Resource-constrained scheduling NP-hardness approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Connected facility location via random facility sampling and core detouring

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2010年第8期76卷 709-726页

作者： Eisenbrand, Friedrich Grandoni, Fabrizio Rothvoss, Thomas Schafer, Guido Ecole Polytech Fed Lausanne Inst Math CH-1015 Lausanne Switzerland Univ Roma Tor Vergata Dipartimento Informat Sistemi & Prod I-00133 Rome Italy Ctr Wiskunde & Informat NL-1090 GB Amsterdam Netherlands

We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the facilities serving sampled clients in the approximate solution. Via a novel analytical tool, which we term core detouring, we show that this approach significantly improves over the previously best known approximation ratios for several NP-hard network design problems. For example, we reduce the approximation ratio for the connected facility location problem from 8.55 to 4.00 and for the single-sink rent-or-buy problem from 3.55 to 2.92. The mentioned results can be derandomized at the expense of a slightly worse approximation ratio. The versatility of our framework is demonstrated by devising improved approximation algorithms also for other related problems. (C) 2010 Elsevier Inc. All rights reserved.

关键词： Connected facility location approximation algorithm Randomized algorithm Network design

来源：评论

学校读者我要写书评

暂无评论

Most balanced minimum cuts

引用

DISCRETE APPLIED MATHEMATICS 2010年第4期158卷 261-276页

作者： Bonsma, Paul Tech Univ Berlin Inst Math D-10623 Berlin Germany

We consider the problem of finding most balanced cuts among minimum st-edge cuts and minimum st-vertex cuts, for given vertices s and t, according to different balance criteria. For edge cuts |S, (S) over bar| we seek to maximize mini{|S|, |(S) over bar|}. For vertex cuts C of G we consider the objectives of (i) maximizing min{|S|, |T|}, where {S, T} is a partition of V(G)\C with s is an element of S, t is an element of T and |S, T| = aleph, (ii) minimizing the order of the largest component of G - C, and (iii) maximizing the order of the smallest component of G - C. All of these problems are NP-hard. We give a PTAS for the edge cut variant and for (i). These results also hold for directed graphs. We give a 2-approximation for (ii), and show that no non-trivial approximation exists for (iii) unless P = NP. To prove these results we show that we can partition the vertices of G, and define a partial order on the subsets of this partition, such that ideals of the partial order correspond bijectively to minimum st-cuts of G. This shows that the problems are closely related to Uniform Partially Ordered Knapsack (UPOK), a variant of POK where element utilities are equal to element weights. Our algorithm is also a PTAS for special types of UPOK instances. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Balanced cut Partially ordered knapsack approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Fingerprint Clustering with Bounded Number of Missing Values

引用

algorithmICA 2010年第2期58卷 282-303页

作者： Bonizzoni, Paola Della Vedova, Gianluca Dondi, Riccardo Mauri, Giancarlo Univ Milano Bicocca Dip Stat Milan Italy Univ Bergamo Dipartimento Sci Linguaggi Comunicaz & Studi Cult Bergamo Italy Univ Milano Bicocca DISCo Milan Italy

The problem of clustering fingerprint vectors with missing values is an interesting problem in Computational Biology that has been proposed in Figueroa et al. (J. Comput. Biol. 11(5):887-901, 2004). In this paper we show some improvements in closing the gaps between the known lower bounds and upper bounds on the approximability of variants of the biological problem. Moreover, we have studied two additional variants of the original problem proposed in Figueroa et al. (Proc. 11th Computing: The Australasian Theory Symposium (CATS), CRPIT, vol. 41, pp. 57-60, 2005). We prove that all such problems are APX-hard even when each fingerprint contains only two unknown positions and we present a greedy algorithm that has constant approximation factors for these variants. Despite the hardness of these restricted versions of the problem, we show that the general clustering problem on an unbounded number of missing values such that they occur for every fixed position of an input vector in at most one fingerprint is polynomial time solvable.

关键词： Clustering approximation algorithm Fingerprint vectors

来源：评论

学校读者我要写书评

暂无评论

Connected vertex covers in dense graphs

引用

THEORETICAL COMPUTER SCIENCE 2010年第26-28期411卷 2581-2590页

作者： Cardinal, Jean Levy, Eythan Univ Libre Bruxelles Dept Informat B-1050 Brussels Belgium

We consider the variant of the minimum vertex cover problem in which we require that the cover induces a connected subgraph. We give new approximation results for this problem in dense graphs, in which either the minimum or the average degree is linear. In particular, we prove tight parameterized upper bounds on the approximation returned by Savage's algorithm, and extend a vertex cover algorithm from Kaminski and Zelikovsky to the connected case. The new algorithm approximates the minimum connected vertex cover problem within a factor strictly less than 2 on all dense graphs. All these results are shown to be tight. Finally, we introduce the price of connectivity for the vertex cover problem, defined as the worst-case ratio between the sizes of a minimum connected vertex cover and a minimum vertex cover. We prove that the price of connectivity is bounded by 2/(1 + epsilon) in graphs with average degree epsilon n, and give a family of near-tight examples. (C) 2010 Elsevier B.V. All rights reserved.

关键词： approximation algorithm Vertex cover Connected vertex cover Dense graph

来源：评论

学校读者我要写书评

暂无评论

Parallel physics-inspired waterflow particle mechanics algorithm for load rebalancing

引用

COMPUTER NETWORKS 2010年第11期54卷 1767-1777页

作者： Feng, Xiang Lau, Francis C. M. E China Univ Sci & Technol Dept Comp Sci Shanghai 200237 Peoples R China Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

The Load Rebalancing Problem (LRP) that reassigns tasks to processors so as to minimize the maximum load arises in the context of dynamic load balancing. Many applications such as on Web based environment, parallel computing on clusters can be stated as LRP. Solving LRP successfully would allow us to utilize resources better and achieve better performance. However LRP has been proven to be NP-hard, thus generating the exact solutions in tractable amount of time becomes infeasible when the problems become large. We present a new nature-inspired approximation algorithm based on the Waterflow Particle Mechanics (W-PM) model to compute in parallel approximate efficient solutions for LRPs. Just like other Nature-inspired algorithms (NAs) drawing from observations of physical processes that occur in nature, the W-PM algorithm is inspired by kinematics and dynamics of waterflow. The W-PM algorithm maps the classical LRP to the flow of water flows in channels by corresponding mathematical model in which all water flows flow according to certain defined rules until reaching a stable state. By anti-mapping the stable state, the solution to LRP can be obtained. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Load rebalancing approximation algorithm Nature-inspired algorithm Waterflow particle mechanics model Distributed and parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Kinetic Facility Location

引用

algorithmICA 2010年第3期57卷 562-584页

作者： Degener, Bastian Gehweiler, Joachim Lammersen, Christiane Univ Bonn Comp Sci Dept 1 D-53117 Bonn Germany Univ Gesamthsch Paderborn Int Grad Sch Dynam Intelligent Syst D-33095 Paderborn Germany Univ Gesamthsch Paderborn Dept Comp Sci Heinz Nixdorf Inst D-33095 Paderborn Germany

We present a deterministic kinetic data structure for the facility location problem that maintains a subset of the moving points as facilities such that, at any point of time, the accumulated cost for the whole point set is at most a constant factor larger than the optimal cost. In our scenario, each point can change its status between client and facility and moves continuously along a known trajectory in a d-dimensional Euclidean space, where d is a constant. Our kinetic data structure requires O(n(log(d)(n)+ log(nR))) space in total, where R := max(pi is an element of P) f(i).max(pi is an element of P)d(i)/min(pi is an element of P) f(i).min(pi is an element of P) d(i), P = {p(1), p(2), ... , p(n)} is the set of given points, and f(i), d(i) are the maintenance cost and the demand of a point pi, respectively. In case that each trajectory can be described by a bounded degree polynomial, we process O(n(2) log(2)(nR)) events, each requiring O(log(d+1)(n).log(nR)) time and O(log(nR)) status changes.

关键词： Facility location Kinetic data structure approximation algorithm Deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimum average routing path clustering problem in multi-hop 2-D underwater sensor networks

引用

OPTIMIZATION LETTERS 2010年第3期4卷 383-392页

作者： Kim, Donghyun Wang, Wei Ding, Ling Lim, Jihwan Oh, Heekuck Wu, Weili Univ Texas Dallas Dept Comp Sci Richardson TX 75083 USA Xi An Jiao Tong Univ Dept Math Xian 710049 Peoples R China Hanyang Univ Dept Comp Sci & Engn Ansan 425791 Gyeonggi South Korea

In this paper, we introduce a new clustering problem in underwater sensor networks, namely minimum average routing path clustering problem (MARPCP). To deal with the high complexity of MARPCP, we relax it to a special case of minimum weight dominating set problem (MWDSP). We show an existing algorithm for MWDSP can produce an approximate solution for MARPCP. Also, we design a constant factor approximation algorithm for MARPCP, which is much faster than the first method.

关键词： approximation algorithm Graph theory Wireless network clustering Underwater sensor networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：