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

Minimize the Maximum Duty in Multi-interface Networks

algorithmICA 2012年第1-2期63卷 274-295页

作者： D'Angelo, Gianlorenzo Di Stefano, Gabriele Navarra, Alfredo Univ Aquila Dept Elect & Informat Engn I-67100 Laquila Italy Univ Perugia Dept Math & Comp Sci I-06123 Perugia Italy

We consider devices equipped with multiple wired or wireless interfaces. By switching of various interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost. In this paper, we consider two basic networking problems in the field of multi-interface networks. The first one, known as the Coverage problem, requires to establish the connections defined by a network. The second one, known as Connectivity problem, requires to guarantee a connecting path between any pair of nodes of a network. Both are subject to the constraint of keeping as low as possible the maximum cost set of active interfaces at each single node. We study the problems of minimizing the maximum cost set of active interfaces among the nodes of the network in order to cover all the edges in the first case, or to ensure connectivity in the second case. We prove that the Coverage problem is NP-hard for any fixed Delta a parts per thousand yen5 and ka parts per thousand yen16, with Delta being the maximum degree, and k being the number of different interfaces among the network. We also show that, unless P=NP, the problem cannot be approximated within a factor of eta ln I", for a certain constant eta. We then provide a general approximation algorithm which guarantees a factor of O((1+b)ln I"), with b being a parameter depending on the topology of the input graph. Interestingly, b can be bounded by a constant for many graph classes. Other approximation and exact algorithms for special cases are presented. Concerning the Connectivity problem, we prove that it is NP-hard for any fixed Delta a parts per thousand yen3 and ka parts per thousand yen10. Also for this problem, the inapproximability result holds, that is, unless P=NP, the problem cannot be approximated within a factor of eta ln I", for a certain constant eta. We then provide approximation and exact

关键词： Multi-interface network Energy saving Computational complexity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Assignment Problem in Content Distribution Networks: Unsplittable Hard-Capacitated Facility Location

引用

ACM TRANSACTIONS ON algorithmS 2012年第3期8卷 1–19页

作者： Bateni, Mohammadhossein Hajiaghayi, Mohammadtaghi Princeton Univ Princeton NJ 08544 USA AT&T Labs Res Florham Pk NJ 07932 USA

In a Content Distribution Network (CDN), there are m servers storing the data;each of them has a specific bandwidth. All the requests from a particular client should be assigned to one server because of the routing protocol used. The goal is to minimize the total cost of these assignments-cost of each is proportional to the distance between the client and the server as well as the request size-while the load on each server is kept below its bandwidth limit. When each server also has a setup cost, this is an unsplittable hard-capacitated facility location problem. As much attention as facility location problems have received, there has been no nontrivial approximation algorithm when we have hard capacities (i.e., there can only be one copy of each facility whose capacity cannot be violated) and demands are unsplittable (i.e., all the demand from a client has to be assigned to a single facility). We observe it is NP-hard to approximate the cost to within any bounded factor in this case. Thus, for an arbitrary constant epsilon > 0, we relax the capacities to a 1 + epsilon factor. For the case where capacities are almost uniform, we give a bicriteria O(log n, 1 + epsilon)-approximation algorithm for general metrics and a (1 + epsilon, 1 + epsilon)-approximation algorithm for tree metrics. A bicriteria (alpha, beta)-approximation algorithm produces a solution of cost at most alpha times the optimum, while violating the capacities by no more than a beta factor. We can get the same guarantees for nonuniform capacities if we allow quasipolynomial running time. In our algorithm, some clients guess the facility they are assigned to, and facilities decide the size of the clients they serve. A straightforward approach results in exponential running time. When costs do not satisfy metricity, we show that a 1.5 violation of capacities is necessary to obtain any approximation. It is worth noting that our results generalize bin packing (zero connection costs and facility costs equa

关键词： algorithms Theory approximation algorithm PTAS network facility location

来源：评论

学校读者我要写书评

暂无评论

Sell or Hold: A simple two-stage stochastic combinatorial optimization problem

引用

OPERATIONS RESEARCH LETTERS 2012年第2期40卷 69-73页

作者： He, Qie Ahmed, Shabbir Nemhauser, George L. Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA

The sell or hold problem (SHP) is to sell k out of n indivisible assets over two stages, with known first-stage prices and random second-stage prices, to maximize the total expected revenue. We show that SHP is NP-hard when the second-stage prices are realized as a finite set of scenarios. We show that SUP is polynomially solvable when the number of scenarios in the second stage is constant. A max{1/2, k /n} - approximation algorithm is presented for the scenario-based SHP. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Stochastic programming Integer programming Submodular maximization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Some Fundamental Results on Base Station Movement Problem for Wireless Sensor Networks

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2012年第4期20卷 1054-1067页

作者： Shi, Yi Hou, Y. Thomas Virginia Polytech Inst & State Univ Bradley Dept Elect & Comp Engn Blacksburg VA 24061 USA

The benefits of using a mobile base station to prolong sensor network lifetime have been well recognized. However, due to the complexity of the problem (time-dependent network topology and traffic routing), theoretical performance limits and provably optimal algorithms remain difficult to develop. This paper fills this important gap by contributing some theoretical results regarding the optimal movement of a mobile base station. Our main result hinges upon two key intermediate results. In the first result, we show that a time-dependent joint base station movement and flow routing problem can be transformed into a location-dependent problem. In the second result, we show that, for (1 - epsilon) optimality, the infinite possible locations for base station movement can be reduced to a finite set of locations via several constructive steps [i.e., discretization of energy cost through a geometric sequence, division of a disk into a finite number of subareas, and representation of each subarea with a fictitious cost point (FCP)]. Subsequently, for each FCP, we can obtain the optimal sojourn time for the base station (as well as the corresponding location-dependent flow routing) via a simple linear program. We prove that the proposed solution can guarantee the achieved network lifetime is at least (1 - epsilon) of the maximum (unknown) network lifetime, where epsilon can be made arbitrarily small depending on the required precision.

关键词： approximation algorithm lifetime mobile base station optimization sensor networks theory

来源：评论

学校读者我要写书评

暂无评论

Dispersion in Disks

引用

THEORY OF COMPUTING SYSTEMS 2012年第2期51卷 125-142页

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

We present three new approximation algorithms with improved constant ratios for selecting points in disks such that the minimum pairwise distance among the points is maximized. (1) A very simple (log )-time algorithm with ratio 0.511 for disjoint unit disks. (2) An LP-based algorithm with ratio 0.707 for disjoint disks of arbitrary radii that uses a linear number of variables and constraints, and runs in polynomial time. (3) A hybrid algorithm with ratio either 0.4487 or 0.4674 for (not necessarily disjoint) unit disks that uses an algorithm of Cabello in combination with either the simple (log )-time algorithm or the LP-based algorithm. The LP algorithm can be extended for disjoint balls of arbitrary radii in a"e , for any (fixed) dimension , while preserving the features of the planar algorithm. The algorithm introduces a novel technique which combines linear programming and projections for approximating Euclidean distances. The previous best approximation ratio for dispersion in disjoint disks, even when all disks have the same radius, was 1/2. Our results give a positive answer to an open question raised by Cabello, who asked whether the ratio 1/2 could be improved.

关键词： Dispersion problem Linear programming approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Elimination Graphs

引用

ACM TRANSACTIONS ON algorithmS 2012年第2期8卷 1–23页

作者： Ye, Yuli Borodin, Allan Univ Toronto Dept Comp Sci Toronto ON M5S 1A1 Canada

In this article we study graphs with inductive neighborhood properties. Let P be a graph property, a graph G = (V, E) with n vertices is said to have an inductive neighborhood property with respect to P if there is an ordering of vertices v(1), ... , v(n) such that the property P holds on the induced subgraph G[N(v(i)) boolean AND V-i], where N(v(i)) is the neighborhood of v(i) and V-i = {v(i), ... , v(n)}. It turns out that if we take P as a graph with maximum independent set size no greater than k, then this definition gives a natural generalization of both chordal graphs and (k + 1)-claw-free graphs. We refer to such graphs as inductive k-independent graphs. We study properties of such families of graphs, and we show that several natural classes of graphs are inductive k-independent for small k. In particular, any intersection graph of translates of a convex object in a two dimensional plane is an inductive 3-independent graph;furthermore, any planar graph is an inductive 3-independent graph. For any fixed constant k, we develop simple, polynomial time approximation algorithms for inductive k-independent graphs with respect to several well-studied NP-complete problems. Our generalized formulation unifies and extends several previously known results.

关键词： Graph class structure property approximation algorithm independent set greedy algorithm local ratio time complexity

来源：评论

学校读者我要写书评

暂无评论

An Oblivious Spanning Tree for Single-Sink Buy-at-Bulk in Low Doubling-Dimension Graphs

引用

IEEE TRANSACTIONS ON COMPUTERS 2012年第5期61卷 700-712页

作者： Srinivasagopalan, Srivathsan Busch, Costas Iyengar, S. S. Louisiana State Univ Dept Comp Sci Baton Rouge LA 70803 USA

We consider the problem of constructing a single spanning tree for the single-sink buy-at-bulk network design problem for doubling-dimension graphs. We compute a spanning tree to route a set of demands along a graph G to or from a designated sink node. The demands could be aggregated at (or symmetrically distributed to) intermediate edges where the fusion cost is specified by a nonnegative concave function f. We describe a novel approach for developing an oblivious spanning tree in the sense that it is independent of the number and location of data sources (or demands) and cost function at the edges. We present a deterministic, polynomial-time algorithm for constructing a spanning tree in low doubling-dimension graphs that guarantees a log(3) D-approximation over the optimal cost, where D is the diameter of the graph G. With a constant fusion-cost function, our spanning tree gives an O(log(3) D)-approximation for every Steiner tree that includes the sink. We also provide a Omega(log n) lower bound for any oblivious tree in low doubling-dimension graphs. To our knowledge, this is the first paper to propose a single spanning tree solution to the single-sink buy-at-bulk network design problem (as opposed to multiple overlay trees).

关键词： Spanning tree buy-at-bulk network design approximation algorithm doubling-dimension graph data fusion data structure

来源：评论

学校读者我要写书评

暂无评论

NONNEGATIVE POLYNOMIAL OPTIMIZATION OVER UNIT SPHERES AND CONVEX PROGRAMMING RELAXATIONS

引用

SIAM JOURNAL ON OPTIMIZATION 2012年第3期22卷 987-1008页

作者： Zhou, Guanglu Caccetta, Louis Teo, Kok Lay Wu, Soon-Yi Curtin Univ Technol Dept Math & Stat Perth WA Australia Natl Cheng Kung Univ Inst Appl Math Tainan 70101 Taiwan

We consider approximation algorithms for nonnegative polynomial optimization over unit spheres. Such optimization models have wide applications, e. g., in signal and image processing, high order statistics, and computer vision. Since polynomial functions are nonconvex, the problems under consideration are all NP-hard. In this paper, based on convex polynomial optimization relaxations, we propose polynomial-time approximation algorithms with new approximation bounds. Numerical results are reported to show the effectiveness of the proposed approximation algorithms.

关键词： nonnegative polynomial optimization convex optimization relaxation approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Complexity of distance paired-domination problem in graphs

引用

THEORETICAL COMPUTER SCIENCE 2012年 459卷 89-99页

作者： Chang, Gerard J. Panda, B. S. Pradhan, D. Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India Natl Taiwan Univ Dept Math Taipei 10617 Taiwan Natl Taiwan Univ Taida Inst Math Sci Taipei 10617 Taiwan Natl Ctr Theoret Sci Taipei Off Taipei Taiwan Indian Inst Technol Dept Math Comp Sci & Applicat Grp New Delhi 110016 India

Suppose G = (V, E) is a simple graph and k is a fixed positive integer. A subset D subset of V is a distance k-dominating set of G if for every u is an element of V. there exists a vertex v is an element of D such that d(G)(u, v) <= k, where d(G)(u, v) is the distance between u and v in G. A set D subset of V is a distance k-paired-dominating set of G if D is a distance k-dominating set and the induced subgraph G[D] contains a perfect matching. Given a graph G = (V, E) and a fixed integer k > 0, the MIN DISTANCE k-PAIRED-DOM SET problem is to find a minimum cardinality distance k-paired-dominating set of G. In this paper, we show that the decision version of MIN DISTANCE k-PAIRED-DOM SET iS NP-complete for undirected path graphs. This strengthens the complexity of decision version Of MIN DISTANCE k-PAIRED-DOM SET problem in chordal graphs. We show that for a given graph G, unless NP subset of DTIME (n(0)((log) (log) (n)) MIN DISTANCE k-PAIRED-Dom SET problem cannot be approximated within a factor of (1 -epsilon ) In n for any epsilon > 0, where n is the number of vertices in G. We also show that MIN DISTANCE k-PAIRED-DOM SET problem is APX-complete for graphs with degree bounded by 3. On the positive side, we present a linear time algorithm to compute the minimum cardinality of a distance k-paired-dominating set of a strongly chordal graph G if a strong elimination ordering of G is provided. We show that for a given graph G, MIN DISTANCE k-PAIRED-DOM SET problem can be approximated with an approximation factor of 1 + In 2 + k . In(Delta(G)), where Delta(G) denotes the maximum degree of G. (C) 2012 Elsevier B.V All rights reserved.

关键词： Distance k-dominating set Distance k-paired-dominating set Strongly chordal graph Undirected path graph NP-complete approximation algorithm APX-complete

来源：评论

学校读者我要写书评

暂无评论

"Almost stable" matchings in the Roommates problem with bounded preference lists

引用

THEORETICAL COMPUTER SCIENCE 2012年 432卷 10-20页

作者： Biro, Peter Manlove, David F. McDermid, Eric J. Univ Glasgow Sch Comp Sci Glasgow Lanark Scotland Hungarian Acad Sci Inst Econ Budapest Hungary 21st Century Technol Inc Austin TX 78730 USA

An instance of the classical Stable Roommates problem need not admit a stable matching. Previous work has considered the problem of finding a matching that is "as stable as possible", i.e., admits the minimum number of blocking pairs. It is known that this problem is NP-hard and not approximable within n(1/2-epsilon), for any epsilon > 0, unless P = NP, where n is the number of agents in a given instance. In this paper, we extend the study to the Stable Roommates problem with Incomplete lists. In particular, we consider the case that the lengths of the lists are bounded by some integer d. We show that, even if d = 3, there is some c > 1 such that the problem of finding a matching with the minimum number of blocking pairs is not approximable within c unless P = NP. On the other hand, we show that the problem is solvable in polynomial time ford <= 2, and we give a (2d - 3)-approximation algorithm for fixed d >= 3. If the given lists satisfy an additional condition (namely the absence of a so-called elitist odd party - a structure that is unlikely to exist in general), the performance guarantee improves to 2d - 4. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Stable Roommates problem Blocking pairs APX-hardness Polynomial-time algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：