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

Approximating the Maximum Internal Spanning Tree problem

THEORETICAL COMPUTER SCIENCE 2009年第50期410卷 5273-5284页

作者： Salamon, Gabor Budapest Univ Technol & Econ Dept Comp Sci & Informat Theory H-1117 Budapest Hungary

Given an undirected connected graph G we consider the problem of finding a spanning tree of G which has a maximum number of internal (non-leaf) vertices among all spanning trees of G. This problem, called MAXIMUM INTERNAL SPANNING TREE problem, is clearly NP-hard since it is a generalization of the HAMILTONIAN PATH problem. From the optimization point of view the MAXIMUM INTERNAL SPANNING TREE problem is equivalent to the MINIMUM LEAF SPANNING TREE problem. However, the two problems have different approximability properties. Lu and Ravi proved that the latter has no constant factor approximation - unless P = NP -, while Salamon and Wiener gave a linear-time 2-approximation algorithm for the MAXIMUM INTERNAL SPANNING TREE problem. In this paper, we improve this approximation ratio by giving an O(vertical bar V(G)vertical bar(4))-time 7/4-approximation algorithm for graphs without pendant vertices. Our approach is based on the successive execution of local improvement steps. We use a linear programming formulation and a primal-dual technique to prove the approximation ratio. We also investigate the vertex-weighted case, that is to find a spanning tree of a vertex-weighted graph G in which the weight sum of internal vertices is maximal among all spanning trees of G. For this problem we present a (2 Delta(G) - 3)-approximation algorithm, where Delta(G) is the maximum vertex-degree of G. A slight modification of this algorithm ensures a 2-approximation whenever the input graph is claw-free. Both algorithms run in O(vertical bar V(G)vertical bar(4)) time for graphs with no pendant vertices. (C) 2009 Elsevier B.V. All rights reserved.

关键词： approximation algorithm Spanning tree leaves Hamiltonian path

来源：评论

学校读者我要写书评

暂无评论

Network Design with Edge-Connectivity and Degree Constraints

引用

THEORY OF COMPUTING SYSTEMS 2009年第3期45卷 512-532页

作者： Fukunaga, Takuro Nagamochi, Hiroshi Kyoto Univ Dept Appl Math & Phys Grad Sch Informat Kyoto 606 Japan

We consider the following network design problem;Given a vertex set V with a metric cost c on V, an integer ka parts per thousand yen1, and a degree specification b, find a minimum cost k-edge-connected multigraph on V under the constraint that the degree of each vertex vaV is equal to b(v). This problem generalizes metric TSP. In this paper, we show that the problem admits a rho-approximation algorithm if b(v)a parts per thousand yen2, vaV, where rho=2.5 if k is even, and rho=2.5+1.5/k if k is odd. We also prove that the digraph version of this problem admits a 2.5-approximation algorithm and discuss some generalization of metric TSP.

关键词： approximation algorithm Degree constraint Edge-connectivity (m, n)-VRP TSP Vehicle routing problem

来源：评论

学校读者我要写书评

暂无评论

A note on graph balancing problems with restrictions

引用

INFORMATION PROCESSING LETTERS 2009年第1期110卷 24-29页

作者： Lee, Kangbok Leung, Joseph Y. -T Pinedo, Michael L. New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA NYU Stern Sch Business Dept Informat Operat & Management Sci New York NY 10012 USA

We consider the graph balancing problem of providing orientations to edges in an undirected multi-graph to minimize the maximum load. We first obtain an FPTAS when the multi-graph is restricted to a tree. We also obtain some additional results for other restricted cases by showing equivalencies with related combinatorial problems. (C) 2009 Elsevier B.V. All rights reserved.

关键词： approximation algorithm Combinatorial problems Computational complexity Graph balancing Parallel machines scheduling Eligibility constraints Fully polynomial time approximation scheme (FPTAS)

来源：评论

学校读者我要写书评

暂无评论

Selecting highly optimal architectural feature sets with Filtered Cartesian Flattening

引用

JOURNAL OF SYSTEMS AND SOFTWARE 2009年第8期82卷 1268-1284页

作者： White, Jules Dougherty, Brian Schmidt, Douglas C. Vanderbilt Univ Dept Elect Engn & Comp Sci Nashville TN 37235 USA

Feature modeling is a common method used to capture the variability in a configurable application. A key challenge developers face when using a feature model is determining how to select a set of features for a variant that simultaneously satisfy a series of resource constraints. This paper presents an approximation technique for selecting highly optimal feature sets while adhering to resource limits. The paper provides the following contributions to configuring application variants from feature models: (I) we provide a polynomial time approximation algorithm for selecting a highly optimal set of features that adheres to a set of resource constraints, (2) we show how this algorithm can incorporate complex configuration constraints;and (3) we present empirical results showing that the approximation algorithm can be used to derive feature sets that are more than 90%+ optimal. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Feature modeling Optimization Resource constraints approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimum-Energy All-to-All Multicasting in Wireless Ad Hoc Networks

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2009年第11期8卷 5490-5499页

作者： Liang, Weifa Brent, Richard Xu, Yinlong Wang, Qingshan Australian Natl Univ Sch Comp Sci Canberra ACT 0200 Australia Australian Natl Univ Inst Math Sci Canberra ACT 0200 Australia Univ Sci & Technol China Sch Comp Sci & Technol Hefei 230027 Anhui Peoples R China

A wireless ad hoc network consists of mobile nodes that are powered by batteries. The limited battery lifetime imposes a severe constraint on the network performance, energy conservation in such a network thus is of paramount importance, and energy efficient operations are critical to prolong the lifetime of the network. All-to-all multicasting is one fundamental operation in wireless ad hoc networks, in this paper we focus on the design of energy efficient routing algorithms for this operation. Specifically, we consider the following minimum-energy all-to-all multicasting problem. Given an all-to-all multicast session consisting of a set of terminal nodes in a wireless ad hoc network, where the transmission power of each node is either fixed or adjustable, assume that each terminal node has a message to share with each other, the problem is to build a shared multicast tree spanning all terminal nodes such that the total energy consumption of realizing the all-to-all multicast session by the tree is minimized. We first show that this problem is NP-Complete. We then devise approximation algorithms with guaranteed approximation ratios. We also provide a distributed implementation of the proposed algorithm. We finally conduct experiments by simulations to evaluate the performance of the proposed algorithm. The experimental results demonstrate that the proposed algorithm significantly outperforms all the other known algorithms.

关键词： Wireless ad hoc networks approximation algorithm routing algorithms energy conservation energy consumption optimization all-to-all multicasting

来源：评论

学校读者我要写书评

暂无评论

Analyzing scheduling with transient failures

引用

INFORMATION PROCESSING LETTERS 2009年第11期109卷 539-542页

作者： Saule, Erik Trystram, Denis Grenoble Univ LIG Montbonnot St Martin France

Two core scheduling problems with replication, namely, a chain of tasks which is the simplest precedence constraint on heterogeneous processors and independent tasks on identical processors, are discussed. In the first model, the communication times are neglected, that is, the result of task i is available on all processors right after the completion of i. The failure occurrences on processor j follows a Poisson's process of parameter λj, the failure rate of j. Thus, the probability of success of the execution of i on processor j is P(i, j) = e^-λjpij. The independent tasks on identical processors expression leads to a pseudo-polynomial optimal algorithm of time complexity in O(Cnm) that provides how many time each task should be replicated. The expression of the reliability does not really change, the only difference is that Vi, Vj, P(i, j) = P(i) since the failure rate of all the processors are homogeneous.

关键词： Fault tolerance Scheduling Multi-objective optimization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimizing SONET Add-Drop Multiplexers in Optical UPSR Networks Using the Minimum Number of Wavelengths

引用

NETWORKS 2009年第3期53卷 276-286页

作者： Wang, Yong Gu, Qian-Ping Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada

In SONET/WDM optical networks, a high-speed wavelength channel is usually shared by multiplexed low-rate network traffic demands. The multiplexing is known as traffic grooming and carried out by SONET Add-Drop Multiplexers (SADM). The maximum number of low-rate traffic demands that can be multiplexed into one wavelength is called the grooming factor. Because SADMs are expensive network devices, a key optimization problem in optical network design is to groom a given set of low-rate traffic demands such that the number of required SADMs is minimized. This optimization problem is challenging and NP-hard even for Unidirectional Path-Switched Ring networks with unitary duplex traffic demands. In this article, we propose two linear-time approximation algorithms for this NP-hard problem based on a novel graph partitioning approach. Both algorithms achieve better worst case performance than the previous algorithms. We also show that the upper bounds obtained by our algorithms are very close to the lower bounds for some instances. In addition, both of our algorithms use the minimum number of wavelengths, which are precious resources as well in optical networks. (C) 2008 Wiley Periodicals, Inc. NETWORKS, Vol. 53(3), 276-286 2009

关键词： traffic grooming SONET/WDM network approximation algorithm graph partitioning

来源：评论

学校读者我要写书评

暂无评论

Nonconvex piecewise linear knapsack problems

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2009年第1期192卷 56-68页

作者： Kameshwaran, S. Narahari, Y. Indian Inst Sci Dept Comp Sci & Automat Elect Commerce Lab Bangalore 560012 Karnataka India Indian Sch Business Ctr Global Logist & Mfg Strategies Hyderabad 500032 Andhra Pradesh India

This paper considers the minimization version of a class of nonconvex knapsack problems with piecewise linear cost structure. The items to be included in the knapsack have a divisible quantity and a cost function. An item can be included partially ill the given quantity range and the cost is a nonconvex piecewise linear function of quantity. Given a demand, the optimization problem is to choose an optimal quantity for each item such that the demand is satisfied and the total cost is minimized. This problem and its close variants are encountered in manufacturing planning, supply chain design, volume discount procurement auctions, and many other contemporary applications. Two separate mixed integer linear programming formulations of this problem are proposed and are compared with existing formulations. Motivated by different scenarios in which the problem is useful, the following algorithms are developed: (1) a fast polynomial time, near-optimal heuristic using convex envelopes;(2) exact pseudo-polynomial time dynamic programming algorithms;(3) a 2-approximation algorithm;and (4) a fully polynomial time approximation scheme. A comprehensive test suite is developed to generate representative problem instances with different characteristics. Extensive computational experiments show that the proposed formulations and algorithms are faster than the existing techniques. (C) 2007 Elsevier B.V. All rights reserved.

关键词： Piecewise linear knapsack problem Precedence constrained knapsack problem Multiple choice knapsack problem Linear relaxation Dynamic programming Convex envelope approximation algorithm Fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

An edge-reduction algorithm for the vertex cover problem

引用

OPERATIONS RESEARCH LETTERS 2009年第3期37卷 181-186页

作者： Han, Qiaoming Punnen, Abraham P. Ye, Yinyu Simon Fraser Univ Dept Math Surrey BC V3T 5X3 Canada Zhejiang Univ Finance & Econ Sch Math & Stat Hangzhou 310018 Zhejiang Peoples R China Stanford Univ Dept Management Sci & Engn Sch Engn Stanford CA 94305 USA

An approximation algorithm for the vertex cover problem is proposed with performance ratio on special graphs. On an arbitrary graph, the algorithm guarantees a vertex cover S-1 such that vertical bar S-1 vertical bar <= 3/2 vertical bar S*vertical bar + xi where S* is an optimal cover and xi an error bound identified. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Vertex cover problem approximation algorithm LP-relaxation

来源：评论

学校读者我要写书评

暂无评论

algorithm design for a class of base station location problems in sensor networks

引用

WIRELESS NETWORKS 2009年第1期15卷 21-38页

作者： Shi, Yi Hou, Y. Thomas Efrat, Alon Virginia Tech Bradley Dept Elect & Comp Engn Blacksburg VA 24061 USA Univ Arizona Dept Comp Sci Tucson AZ 85721 USA

Base station placement has significant impact on sensor network performance. Despite its significance, results on this problem remain limited, particularly theoretical results that can provide performance guarantee. This paper proposes a set of procedure to design (1- epsilon) approximation algorithms for base station placement problems under any desired small error bound epsilon > 0. It offers a general framework to transform infinite search space to a finite-element search space with performance guarantee. We apply this procedure to solve two practical problems. In the first problem where the objective is to maximize network lifetime, an approximation algorithm designed through this procedure offers 1/epsilon(2) complexity reduction when compared to a state-of-the-art algorithm. This represents the best known result to this problem. In the second problem, we apply the design procedure to address base station placement problem when the optimization objective is to maximize network capacity. Our (1- epsilon) approximation algorithm is the first theoretical result on this problem.

关键词： Base station placement Network lifetime Network capacity Wireless sensor networks approximation algorithm Complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：