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

Scheduling jobs under increasing linear machine maintenance time

JOURNAL OF SCHEDULING 2010年第4期13卷 443-449页

作者： Xu, Dehua Yin, Yunqiang Li, Hongxing Beijing Normal Univ Sch Math Sci Beijing 100875 Peoples R China

Although scheduling problems with machine availability have attracted many researchers' attention, most of the past studies are mainly focused on one or several prefixed machine maintenance activities. In this research, we assume that the time needed to perform one maintenance activity is an increasing linear function of the total processing time of the jobs that are processed after the machine's last maintenance activity. We consider two scheduling problems with such maintenance requirement in this paper. The first problem is a parallel machine scheduling problem where the length of the time interval between any two consecutive maintenance activities is between two given positive numbers. The objective is to minimize the maintenance makespan, i.e., the completion time of the last finished maintenance. The second problem is a single machine scheduling problem where the length of the time interval between any two consecutive maintenance activities is fixed and the objective is to minimize the makespan, i.e., the completion time of the last finished job. We propose two approximation algorithms for the considered problems and analyze their performances.

关键词： Scheduling Maintenance Linear function approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Satisfactory graph partition, variants, and generalizations

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2010年第2期206卷 271-280页

作者： Bazgan, Cristina Tuza, Zsolt Vanderpooten, Daniel Univ Paris 09 LAMSADE F-75775 Paris 16 France Hungarian Acad Sci Inst Comp & Automat H-1111 Budapest Hungary Univ Pannonia Dept Comp Sci & Syst Technol H-8200 Veszprem Hungary

The SATISFACTORY PARTITION problem asks for deciding if a given graph has a partition of its vertex set into two nonempty parts such that each vertex has at least as many neighbors in its part as in the other part. This problem was introduced by Gerber and Kobler [M. Gerber, D. Kobler, algorithmic approach to the satisfactory graph partitioning problem, European Journal of Operational Research 125 (2000) 283-291] and studied further by other authors. In this paper we first review some applications and related problems. Then, we survey structural, complexity, and approximation results obtained for SATISFACTORY PARTITION and for some of its variants and generalizations. A list of open questions concludes this survey. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization Complexity theory Vertex partition Degree constraints approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

New results on optimizing rooted triplets consistency

引用

DISCRETE APPLIED MATHEMATICS 2010年第11期158卷 1136-1147页

作者： Byrka, Jaroslaw Guillemot, Sylvain Jansson, Jesper Ochanomizu Univ Bunkyo Ku Tokyo 1128610 Japan Univ Paris Est Inst Gaspard Monge F-77454 Champs Sur Marne Marne La Vallee France Ctr Wiskunde & Informat NL-1098 SJ Amsterdam Netherlands Eindhoven Univ Technol NL-5600 MB Eindhoven Netherlands

A set of phylogenetic trees with overlapping leaf sets is consistent if it can be merged without conflicts into a supertree. In this paper, we study the polynomial-time approximability of two related optimization problems called the maximum rooted triplets consistency problem (MAxRTC) and the minimum rooted triplets inconsistency problem (MINRTI) in which the input is a set R of rooted triplets, and where the objectives are to find a largest cardinality subset of R which is consistent and a smallest cardinality subset of R whose removal from R results in a consistent set, respectively. We first show that a simple modification to Wu's Best-Pair-Merge-First heuristic Wu (2004) [38] results in a bottom-up-based 3-approximation algorithm for MAxRTC. We then demonstrate how any approximation algorithm for MINRTI could be used to approximate MAxRTC, and thus obtain the first polynomial-time approximation algorithm for MAxRTC with approximation ratio less than 3. Next, we prove that for a set of rooted triplets generated under a uniform random model, the maximum fraction of triplets which can be consistent with any phylogenetic tree is approximately one third. We then provide a deterministic construction of a triplet set having a similar property which is subsequently used to prove that both MAxRTC and MINRTI are NP-hard even if restricted to minimally dense instances. Finally, we prove that unless P = NP, MINRTI cannot be approximated within a ratio of c . ln n for some constant c > 0 in polynomial time, where n denotes the cardinality of the leaf label set of R. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Phylogenetic tree Rooted triplet Supertree approximation algorithm Pseudorandomness Hardness of approximation

来源：评论

学校读者我要写书评

暂无评论

Center-oriented algorithms for the minimum energy broad and multicast problem in wireless ad hoc networks

引用

ELECTRONIC COMMERCE RESEARCH AND APPLICATIONS 2010年第3期9卷 228-236页

作者： Bauer, Joanna Altinkemer, Kemal Haugland, Dag Univ Bergen Dept Informat N-5020 Bergen Norway Purdue Univ Krannert Sch Management W Lafayette IN 47907 USA

Quickly finding low-energy multicast routings is vital for a wireless system's energy efficiency. Therefore, key aspects of heuristics for the minimum energy multicast problem (MEMP) are low time complexity (measured in the numbers |V| and |A| of networking devices and their possible power assignments, respectively) and low deviation from the optimal energy consumption. Following a center-oriented approach, we develop the STSuS and STESuS algorithms (time complexity O(|V|(2)) and O(|V|(2) log |V|), respectively), and analyze their performance in numerical simulations. They deviate from the optimal energy consumption by only approximate to 11% and approximate to 7.5%, respectively, and thereby outperform the well-known MIP (O(|V|(2)), approximate to 22% deviation) and many other algorithms significantly. (C) 2009 Elsevier B. V. All rights reserved.

关键词： Wireless ad hoc network Minimum energy multicast problem approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On dual power assignment optimization for biconnectivity

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2010年第2期19卷 174-183页

作者： Wang, Chen Willson, James Park, Myung-Ah Farago, Andras Wu, Weili Tsinghua Univ Beijing 100084 Peoples R China

Topology control is an important technology of wireless ad hoc networks to achieve energy efficiency and fault tolerance. In this paper, we study the dual power assignment problem for 2-edge connectivity and 2-vertex connectivity in the symmetric graphical model which is a combinatorial optimization problem from topology control technology. The problem is arisen from the following origin. In a wireless ad hoc network where each node can switch its transmission power between high-level and low-level, how can we establish a fault-tolerantly connected network topology in the most energy-efficient way? Specifically, the objective is to minimize the number of nodes assigned with high power and yet achieve 2-edge connectivity or 2-vertex connectivity. We addressed these optimization problems (2-edge connectivity and 2-vertex connectivity version) under the general graph model in (Wang et al. in Theor. Comput. Sci., 2008). In this paper, we propose a novel approximation algorithm, called Candidate Set Filtering algorithm, to compute nearly-optimal solutions. Specifically, our algorithm can achieve 3.67-approximation ratio for both 2-edge connectivity and 2-vertex connectivity, which improves the existing 4-approximation algorithms for these two cases.

关键词： Dual power assignment Biconnectivity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Covering a laminar family by leaf to leaf links

引用

DISCRETE APPLIED MATHEMATICS 2010年第13期158卷 1424-1432页

作者： Maduel, Yael Nutov, Zeev Open Univ Israel Raanana Israel

The Tree Augmentation Problem (TAP) is: given a tree T = (V, epsilon) and a set E of edges (called links) on V disjoint to epsilon, find a minimum-size edge-subset F subset of E such that T + F is 2-edge-connected. TAP is equivalent to the problem of finding a minimum-size edge-cover F subset of E of a laminar set-family. We consider the restriction, denoted LL-TAP, of TAP to instances when every link in E connects two leaves of T. The best approximation ratio for TAP is 3/2, obtained by Even et al. (2001, 2009, 2008)[3-5], and no better ratio was known for LL-TAP. All the previous approximation algorithms that achieve a ratio better than 2 for TAP, or even for LL-TAP, have been quite involved. For LL-TAP we obtain the following approximation ratios: 17/12 for general trees, 11/8 for trees of height 3, and 4/3 for trees of height 2. We also give a very simple 3/2-approximation algorithm (for general trees) and prove that it computes a solution of size at most min { 3/2t, 5/3t* }, where t is the minimum size of an edge-cover of the leaves, and t* is the optimal value of the natural LP-relaxation for the problem of covering the leaf edges only. This provides the first evidence that the integrality gap of a natural LP-relaxation for LL-TAP is less than 2. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Edge-connectivity approximation algorithm Laminar family Edge-cover

来源：评论

学校读者我要写书评

暂无评论

AFPTAS RESULTS FOR COMMON VARIANTS OF BIN PACKING: A NEW METHOD FOR HANDLING THE SMALL ITEMS

引用

SIAM JOURNAL ON OPTIMIZATION 2010年第6期20卷 3121-3145页

作者： Epstein, Leah Levin, Asaf Univ Haifa Dept Math IL-31905 Haifa Israel Technion Israel Inst Technol Fac Ind Engn & Management IL-32000 Haifa Israel

We consider two well-known natural variants of bin packing and show that these packing problems admit asymptotic fully polynomial time approximation schemes (AFPTASs). In bin packing problems, a set of one-dimensional items of size at most 1 is to be assigned (packed) to subsets of sum at most 1 (bins). It has been known for a while that the most basic problem admits an AFPTAS. In this paper, we develop new methods that allow us to extend this result to other variants of bin packing consisting of a family of two-parameter bin packing problems. We demonstrate the use of our methods by designing AFPTASs for the following problems. The first problem is bin packing with cardinality constraints, where a parameter k is given such that a bin may contain up to k items. The goal is to minimize the number of bins used. The second problem is bin packing with rejection, where every item has a rejection penalty associated with it. An item needs to be either packed to a bin or rejected, and the goal is to minimize the number of bins used and the total rejection penalty of unpacked items. This resolves the complexity of two important variants of the bin packing problem. Our approximation schemes use a novel method for packing the small items. This new method is the core of the improved running times of our schemes over the running times of the previous results, which are only asymptotic polynomial time approximation schemes.

关键词： worst case analysis approximation algorithm bin packing

来源：评论

学校读者我要写书评

暂无评论

MAXIMUM AREA INDEPENDENT SETS IN DISK INTERSECTION GRAPHS

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2010年第2期20卷 105-118页

作者： Bereg, Sergey Dumitrescu, Adrian Jiang, Minghui Utah State Univ Dept Comp Sci Logan UT 84322 USA Univ Texas Dallas Dept Comp Sci Richardson TX 75083 USA Univ Wisconsin Dept Comp Sci Milwaukee WI 53201 USA

Maximum Independent Set (MIS) and its relative Maximum Weight Independent Set (MWIS) are well-known problems in combinatorial optimization;they are NP-hard even in the geometric setting of unit disk graphs. In this paper, we study the Maximum Area Independent Set (MAIS) problem, a natural restricted version of MWIS in disk intersection graphs where the weight equals the disk area. We obtain: (i) Quantitative bounds on the maximum total area of an independent set relative to the union area;(ii) Practical constant-ratio approximation algorithms for finding an independent set with a large total area relative to the union area.

关键词： Maximum independent set disk intersection graph approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Finding a Minimum Perimeter Polygon Intersecting a Set of Line Segments

引用

11th International Workshop on algorithms and Data Structures (WADS 2009)

作者： Hassanzadeh, Farzad Rappaport, David Queens Univ Kingston ON Canada

ISBN: (纸本)9783642033667

Let S denote a set of line segments in the plane. We say that a polygon P intersects S if every segment in S has a non-empty intersection with the interior or boundary of P. Currently, the best known algorithm finding a minimum perimeter polygon intersecting a set of line segments has a worst case exponential running time. It is also still unknown whether this problem is NP-hard. In this note we explore several approximation algorithms. We present efficient approximation algorithms that yield good empirical results, but can perform very poorly on pathological examples. We also present an O(n log n) algorithm with a guaranteed worst case performance bound that is at most pi/2 times that of the optimum.

关键词： Computational Geometry Line Segment Intersecting Polygon approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Parallel-machine parallel-batching scheduling with family jobs and release dates to minimize makespan

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2010年第1期19卷 84-93页

作者： Li, Shisheng Yuan, Jinjiang Zhengzhou Univ Dept Math Zhengzhou 450052 Henan Peoples R China

We consider the scheduling of n family jobs with release dates on m identical parallel batching machines. Each batching machine can process up to b jobs simultaneously as a batch. In the bounded model, b < n, and in the unbounded model, b=a. Jobs from different families cannot be placed in the same batch. The objective is to minimize the maximum completion time (makespan). When the number of families is a constant, for both bounded model and unbounded model, we present polynomial-time approximation schemes (PTAS).

关键词： Parallel machine Batching approximation algorithm Worst case ratio Family

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：