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

An aptas for generalized cost variable-sized bin packing

SIAM JOURNAL ON COMPUTING 2008年第1期38卷 411-428页

作者： Epstein, Leah Levin, Asaf Univ Haifa Dept Math IL-31905 Haifa Israel Hebrew Univ Jerusalem Dept Stat IL-91905 Jerusalem Israel

Bin packing is a well-known problem which has a large number of applications. Classical bin packing is a simple model in which all bins are identical. In the bin packing problem with variable-sized bins, we are given a supply of a variety of sizes. This latter model assumes, however, that the cost of a bin is always defined to be its exact size. In this paper we study the more general problem where an available bin size is associated with a fixed cost, which may be smaller or larger than its size. The costs of different bin sizes are unrelated. This generalized problem has various applications in storage and scheduling. In order to generalize previous work, we design new rounding and allocation methods. Our main result is an asymptotic polynomial time approximation scheme for the generalized problem.

关键词： worst case analysis approximation algorithm bin packing

来源：评论

学校读者我要写书评

暂无评论

APPROXIMATE INTEGER DECOMPOSITIONS FOR UNDIRECTED NETWORK DESIGN PROBLEMS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2008年第1期23卷 163-177页

作者： Chekuri, Chandra Shepherd, F. Bruce Univ Illinois Dept Comp Sci Urbana IL 61801 USA McGill Univ Montreal PQ H3A 2K6 Canada

A well-known theorem of Nash-Williams and Tutte gives a necessary and sufficient condition for the existence of k edge-disjoint spanning trees in an undirected graph. A corollary of this theorem is that every 2k-edge-connected graph has k edge-disjoint spanning trees. We show that the splitting-off theorem of Mader in undirected graphs implies a generalization of this to finding k edge-disjoint Steiner forests in Eulerian graphs. This leads to new 2-approximation rounding algorithms for certain constrained 0-1 forest problems considered by Goemans and Williamson. These algorithms also produce approximate integer decompositions of fractional solutions. We then discuss open problems and outlets for this approach to the more general class of 0-1 skew supermodular network design problems.

关键词： network design supermodular function integer decomposition approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On the complexity and algorithm of grooming regular traffic in WDM optical networks

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2008年第6期68卷 877-886页

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

In SONET/WDM networks, a high-speed wavelength channel is Usually shared by Multiple low-rate traffic demands to make efficient use of the wavelength capacity. The multiplexing is known as traffic grooming and performed by SONET Add-Drop Multiplexers (SADM). The maximum number of low-rate traffic demands that can be multiplexed into one wavelength channel is called grooming factor. Since SADMs are expensive, a key optimization goal of traffic grooming is to minimize the total number of SADMs in order to satisfy a given set of traffic demands. As an important communication traffic pattern, all-to-all traffic has been widely studied for the traffic grooming problem. In this paper, we study the regular traffic pattern, which is considered as a generalization of the all-to-all traffic pattern. We focus on the Unidirectional Path-Switched Ring (UPSR) networks. We prove that the traffic grooming problem is NP-hard for the regular traffic pattern in UPSR networks, and show that the problem does not admit a Fully Polynomial Time approximation Scheme (FPTAS). We further prove that the problem remains NP-hard even if the grooming factor is any fixed value chosen from a subset of integers. We also propose a performance guaranteed algorithm to minimize the total number of required SADMs, and show that the algorithm achieves a better upper bound than previous algorithms. Extensive simulations are conducted, and the empirical results validate that our algorithm outperforms the previous ones in most cases. In addition, our algorithm always uses the minimum number of wavelengths, which are precious resources as well in optical networks. (c) 2008 Elsevier Inc. All rights reserved.

关键词： traffic grooming SONET/WDM networks graph partition NP-completeness approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Growth rate of switched homogeneous systems

引用

AUTOMATICA 2008年第11期44卷 2857-2862页

作者： Tuna, S. Emre Middle E Tech Univ Dept Elect & Elect Engn TR-06531 Ankara Turkey

We consider discrete-time homogeneous systems under arbitrary switching and study their growth rate, the analogue of joint spectral radius for switched linear systems. We show that a system is asymptotically stable if and only if its growth rate is less than unity. We also provide an approximation algorithm to compute growth rate with arbitrary accuracy. (C) 2008 Elsevier Ltd. All rights reserved.

关键词： Homogeneity Switched system Growth rate Joint spectral radius approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximating the spanning star forest problem and its application to genomic sequence alignment

引用

SIAM JOURNAL ON COMPUTING 2008年第3期38卷 946-962页

作者： Nguyen, C. Thach Shen, Jian Hou, Minmei Sheng, Li Miller, Webb Zhang, Louxin Univ Washington Dept Comp Sci & Engn Seattle WA 98195 USA SW Texas State Univ Dept Math San Marcos TX 78666 USA No Illinois Univ Dept Comp Sci De Kalb IL 60115 USA Drexel Univ Dept Math Philadelphia PA 19104 USA Penn State Univ Dept Biol University Pk PA 16802 USA Penn State Univ Dept Comp Sci & Engn University Pk PA 16802 USA Natl Univ Singapore Dept Math Singapore 117543 Singapore

This paper studies the algorithmic issues of the spanning star forest problem. We prove the following results: (1) There is a polynomial-time approximation scheme for planar graphs;(2) there is a polynomial-time 3/5-approximation algorithm for graphs;(3) it is NP-hard to approximate the problem within ratio 259/260+epsilon for graphs;(4) there is a linear-time algorithm to compute the maximum star forest of a weighted tree;(5) there is a polynomial-time 1/2-approximation algorithm for weighted graphs. We also show how to apply this spanning star forest model to aligning multiple genomic sequences over a tandem duplication region.

关键词： dominating set spanning star forest approximation algorithm genomic sequence alignment

来源：评论

学校读者我要写书评

暂无评论

Approximating a vehicle scheduling problem with time windows and handling times

引用

THEORETICAL COMPUTER SCIENCE 2008年第1-3期393卷 133-146页

作者： Nagamochi, Hiroshi Ohnishi, Takaharu Kyoto Univ Dept Appl Math & Phys Kyoto 6068501 Japan

In this paper, we study a problem of finding a vehicle scheduling to process a set of n jobs which are located in an asymmetric metric space. Each job j has a positive handling time h(j), a time window [r(j), d(j)], and a benefit b(j). We consider the following two problems: MAX-VSP asks to find a schedule for a single vehicle to process a subset of jobs with the maximum benefit;and MIN-VSP asks to find a schedule to process all given jobs with the minimum number of vehicles. We first give an O(rho n(3+gamma)) time algorithm that delivers a 2-approximate solution to MAX-VSP, where rho = max(j,j)'(d(j) - r(j))/h(j') and gamma is the maximum number of jobs that can be processed by the vehicle after processing a job j and before visiting the processed job j again by deadline d(j). We then present an O(rho n(4+gamma)) time algorithm that delivers a 2H (n) -approximate solution to MIN-VSP, where H(n) is the nth harmonic number. (C) 2008 Elsevier B.V. All rights reserved.

关键词： approximation algorithm digraphs dynamic programming graphs NP-hard VSP

来源：评论

学校读者我要写书评

暂无评论

Approximating k-cuts using network strength as a lagrangean relaxation

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2008年第1期186卷 77-90页

作者： Ravi, R. Sinha, Arnitabh Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA Univ Michigan Ross Sch Business Ann Arbor MI 48109 USA

Given an undirected, edge-weighted connected graph, the k-cut problem is to partition the vertex set into k non-empty connected components so as to minimize the total weight of edges whose end points are in different components. We present a combinatorial polynomial-time 2-approximation algorithm for the k-cut problem. We use a Lagrangean relaxation (also suggested by Barahona [F. Barahona, On the k-cut problem, Operations Research Letters 26 (2000) 99105]) to reduce the problem to the attack problem, for which a polynomial time algorithm was provided by Cunningham [W. Cunningham, Optimal attack and reinforcement of a network, Journal of the ACM 32(3) (1985) 549-561]. We prove several structural results of the relaxation, and use these results to develop an approximation algorithm. We provide analytical comparisons of our algorithm and lower bound with two others: Saran and Vazirani (H. Saran, V. Vazirani, Finding k-cuts within twice the optimal, SIAM Journal of Computing 24(1) (1995) 101-108] and Naor and Rabani [J. Naor, Y. Rabani, Tree packing and approximating k-cuts. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete algorithms, 2001, pp. 26-27]. We also provide computational results comparing the performance of our algorithm on random graphs with respect to the lower bound provided by the attack problem as well as an alternate 2-approximation algorithm provided by Saran and Vazirani [Cited above]. (c) 2007 Elsevier B.V. All rights reserved.

关键词： combinatorial optimization graph theory approximation algorithm lagrangean relaxation

来源：评论

学校读者我要写书评

暂无评论

On the inapproximability of the exemplar conserved interval distance problem of genomes

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2008年第2期15卷 201-221页

作者： Chen, Zhixiang Fowler, Richard H. Fu, Bin Zhu, Binhai Univ Texas Pan Amer Dept Comp Sci Edinburg TX 78541 USA Montana State Univ Dept Comp Sci Bozeman MT 59717 USA

In this paper we present two main results about the inapproximability of the exemplar conserved interval distance problem of genomes. First, we prove that it is NP-complete to decide whether the exemplar conserved interval distance between any two genomes is zero or not. This result implies that the exemplar conserved interval distance problem does not admit any approximation in polynomial time, unless P=NP. In fact, this result holds, even when every gene appears in each of the given genomes at most three times. Second, we strengthen the first result under a weaker definition of approximation, called weak approximation. We show that the exemplar conserved interval distance problem does not admit any weak approximation within a super-linear factor of 2/7m(1.5), where m is the maximal length of the given genomes. We also investigate polynomial time algorithms for solving the exemplar conserved interval distance problem when certain constrains are given. We prove that the zero exemplar conserved interval distance problem of two genomes is decidable in polynomial time when one genome is O(log n)-spanned. We also prove that one can solve the constant-sized exemplar conserved interval distance problem in polynomial time, provided that one genome is trivial.

关键词： genome rearrangement exemplar conserved interval distance approximation algorithm inapproximability weak approximation

来源：评论

学校读者我要写书评

暂无评论

Average-case performance analysis of online non-clairvoyant scheduling of parallel tasks with precedence constraints

引用

COMPUTER JOURNAL 2008年第2期51卷 216-226页

作者： Li, Keqin SUNY Albany Dept Comp Sci New Paltz NY 12561 USA

We evaluate the average-case performance of three approximation algorithms for online non-clairvoyant scheduling of parallel tasks with precedence constraints. We show that for a class of wide task graphs, when task sizes are uniformly distributed in the range [1...C], the online non-clairvoyant scheduling algorithm LL-SIMPLE has an asymptotic average-case performance bound of M/(M - (3 - (1 + 1/C)(C+1))C - 1), where M is the number of processors. For uniform probability distributions of task sizes, we present numerical and simulation data to demonstrate the accuracy of our general asymptotic average-case performance bound. We also report extensive experimental results on the average-case performance of online non-clairvoyant scheduling algorithms LL-GREEDY and LS. algorithm LL-GREEDY has better performance than LL-SIMPLE using an improved algorithm to schedule independent tasks in the same level. algorithm LS produces even better schedules due to a break of boundaries among levels.

关键词： approximation algorithm average-case performance ratio non-clairvoyant scheduling online scheduling parallel task precedence constraint probabilistic analysis simulation worst case performance ratio

来源：评论

学校读者我要写书评

暂无评论

An improved lower bound for approximating minimum GCD multiplier in l_∞ norm (GCDM_∞)

引用

THEORETICAL COMPUTER SCIENCE 2008年第1-3期396卷 1-9页

作者： Chen, WenBin Meng, Jiangtao Yin, Dengpan Nanjing Univ Aeronaut & Astronaut Dept Comp Sci Nanjing 210016 Peoples R China AM Coll Baton Rouge LA USA

In this paper, we study the inapproximability of the following NP-complete number theoretic optimization problems introduced by Rossner and Seifert [C. Rossner, J.P. Seifert, The complexity of approximate optima for greatest common divisor computations, in: Proceedings of the 2nd International algorithmic Number Theory Symposium, ANTS-II, 1996, pp. 307-322]: Given n numbers a(1),..., a(n) epsilon Z, find an l(infinity)-minimum GCD multiplier for a(1),..., a(n), i.e., a vector x epsilon Z(n) with minimum max 1 <= i <= n |x(i)| satisfying Sigma(n)(i=1) x(i)a(i) = gcd(a1,...,a(n)). We show that assuming P not equal NP, it is NP-hard to approximate the Minimum GCD Multiplier in l(infinity) norm (GCDMc(infinity)) within a factor n(c/log log n) for some constant c > 0 where n is the dimension of the given vector. This improves on the best previous result. The best result so far gave 2((logn)1-epsilon) factor hardness by Rossner and Seifert [C. Rossner, J.P. Seifert, The complexity of approximate optima for greatest common divisor computations, in: Proceedings of the 2nd international algorithmic Number Theory Symposium, ANTS-II, 1996, pp. 307-322], where epsilon > 0 is an arbitrarily small constant. (C) 2007 Elsevier B.V. All rights reserved.

关键词： approximation algorithm computational complexity GCD NP-hard number theoretic problems probabilistically checkable proofs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：