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

4th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Ding, Wei Lin, Guohui Xue, Guoliang Zhejiang Water Conservancy & Hydropower Coll Hangzhou 310000 Zhejiang Peoples R China Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Arizona State Univ Dept Comp Sci & Engn Tempe AZ 85287 USA

ISBN: (纸本)9783642174605

Given an edge-weighted undirected graph C = (V, E, c, w), where each edge e is an element of E has a cost c(e) and a weight w(e), a set S subset of V of terminals and a positive constant Do, we seek a minimum cost Steiner tree where all terminals appear as leaves and its diameter is bounded by Do. Note that the diameter of a tree represents the maximum weight of path connecting two different leaves in the tree. Such problem is called the minimum cost diameter-constrained Steiner tree problem. This problem is NP-hard even when the topology of Steiner tree is fixed. In present paper we focus on this restricted version and present a fully polynomial time approximation scheme (FPTAS) for computing a minimum cost diameter-constrained Steiner tree under a fixed topology.

关键词： Diameter-constrained Steiner tree fully polynomial time approximation scheme fixed topology

来源：评论

学校读者我要写书评

暂无评论

The Bound Coverage Problem by Aligned Disks in L1 Metric 28th

The Bound Coverage Problem by Aligned Disks in L1 Metric

引用

28th International Computing and Combinatorics Conference (COCOON)

作者： Liu, Xiaofei Liu, Zhonghao Yunnan Univ Sch Informat Sci & Engn Kunming Yunnan Peoples R China Yunnan Univ Sch Math & Stat Kunming Yunnan Peoples R China

ISBN: (纸本)9783031221040;9783031221057

In this paper, we study the bound coverage problem by aligned disks in L-1 metric. Suppose U is a set of users, L is a horizontal line on the plane, and S is a set of points on the line L, where each user has a profit. This problem to select a set of disks in L-1 metric such that the center of each disk is a point in S (but with arbitrary radius) and the total profit of the covered users by the selected disk set is at least B, where B is a given profit bound, the disk in L-1 metric is a region with a rotated square boundary, and the relationship between the cost of a disk with radius r is r(alpha) (alpha >= 1). This objective is to minimize the total cost of the selected disks. We prove that this problem is NP-hard even when a = 1, and present a fully polynomial time approximation scheme based on a rounding-and-scaling technique.

关键词： Disk coverage problem Bound fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

polynomial approximation schemeS FOR THE MAX-MIN ALLOCATION PROBLEM UNDER A GRADE OF SERVICE PROVISION

引用

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS 2009年第3期1卷 355-368页

作者： Li, Jianping Li, Weidong Li, Jianbo Yunnan Univ Dept Math Kunming 650091 Peoples R China Kunming Univ Sci & Technol Sch Management & Econ Kunming 650031 Peoples R China

The max-min allocation problem under a grade of service provision is defined in the following model: given a set M of m parallel machines and a set J of n jobs, where machines and jobs are all entitled to different levels of grade of service (GoS), each job J(j). J has its processing time p(j) and it can only be allocated to a machine M-i whose GoS level is no more than the GoS level the job J(j) has. The goal is to allocate all jobs to m machines to maximize the minimum machine load among these m machines, where the machine load of Mi is the sum of the processing time of jobs executed on Mi. The best known approximation algorithm [4] to solve this problem produces an allocation in which the minimum machine completion time is at least Omega (log log log m/log log m) of the optimal value. In this paper, we respectively present four approximation schemes to solve this problem and its two special versions: (1) a polynomial time approximation scheme (PTAS) with a running time O(mn (O)(1\epsilon(2))) for the general version, where epsilon > 0;(2) a PTAS and a fully polynomial time pproximation scheme (FPTAS) with the running time O(n) for the version where the number m of machines is fixed;(3) a PTAS with the running time O(n) for the version where the number of GoS levels is bounded by k.

关键词： Scheduling allocation grade of service polynomial time approximation scheme fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

A half-product based approximation scheme for agreeably weighted completion time variance

A half-product based approximation scheme for agreeably weig...

引用

14th Annual Meeting of the European Chapter on Combinatorial Optimization (ECCO 14)

作者： Cheng, JL Kubiak, W Mem Univ Newfoundland Fac Business Adm St Johns NF A1B 3X5 Canada

A recent INFORMS Journal on Computing paper presents a fully polynomial time approximation scheme for minimizing the completion time variance with agreeable weights on a single machine. This paper presents a much fast... 详细信息

关键词： scheduling fully polynomial time approximation scheme weighted completion time variance agreeable weights half-products

来源：评论

学校读者我要写书评

暂无评论

Positive half-products and scheduling with controllable processing times

Positive half-products and scheduling with controllable proc...

引用

8th International Workshop on Project Management and Scheduling

作者： Janiak, A Kovalyov, MY Kubiak, W Werner, F Mem Univ Newfoundland Fac Business Adm St John NF A1B 3X5 Canada Wroclaw Univ Technol Inst Engn Cybernet Wroclaw Poland Belarusian State Univ Fac Econ Minsk 220050 BELARUS Natl Acad Sci Belarus United Inst Informat Problems Minsk 220050 BELARUS Otto Von Guericke Univ Magdeburg Germany

We study the single machine scheduling problem with controllable job processing times to minimize a linear combination of the total weighted job completion time and the total weighted processing time compression. We show that this scheduling problem is a positive half-product minimization problem. Positive half-products make up an interesting subclass of half-products and are introduced in this paper to provide a conceptual framework for the problem with controllable job processing times as well as other problems. This framework allows to readily derive in one fell swoop a number of results for the problem with controllable processing times from more general results obtained earlier for the half-product. We also present fast fully polynomial time approximation schemes for the problem with controllable processing times. The schemes apply to all positive half-products. (c) 2004 Elsevier B.V. All rights reserved.

关键词： single machine scheduling controllable processing times pseudo-Boolean optimization fully polynomial time approximation scheme computational complexity

来源：评论

学校读者我要写书评

暂无评论

On Energy-Optimal Voltage Scheduling for Fixed-Priority Hard Real-time Systems

引用

ACM Transactions on Embedded Computing Systems 2003年第3期2卷 393-430页

作者： Yun, Han-Saem Kim, Jihong School of Computer Science and Engineering Seoul National University Seoul Shilim-dong Kwanak-ku 151-742 South Korea

We address the problem of energy-optimal voltage scheduling for fixed-priority hard real-time systems, on which we present a complete treatment both theoretically and practically. Although most practical real-time systems are based on fixed-priority scheduling, there have been few research results known on the energy-optimal fixed-priority scheduling problem. First, we prove that the problem is NP-hard. Then, we present a fully polynomial time approximation scheme (FPTAS) for the problem. For any ɛ>0, the proposed approximation scheme computes a voltage schedule whose energy consumption is at most (1+ɛ) times that of the optimal voltage schedule. Furthermore, the running time of the proposed approximation scheme is bounded by a polynomial function of the number of input jobs and 1/ɛ. Given the NP-hardness of the problem, the proposed approximation scheme is practically the best solution because it can compute a near-optimal voltage schedule (i.e., provably arbitrarily close to the optimal schedule) in polynomial time. Experimental results show that the approximation scheme finds more efficient (almost optimal) voltage schedules faster than the best existing heuristic. © 2003, ACM. All rights reserved.

关键词： Algorithms approximation algorithms dynamic voltage scaling Fixed-priority scheduling fully polynomial time approximation scheme real-time systems variable voltage processor

来源：评论

学校读者我要写书评

暂无评论

The approximation scheme For Peak Power Driven Voltage Partitioning

The Approximation Scheme For Peak Power Driven Voltage Parti...

引用

IEEE/ACM International Conference on Computer-Aided Design (ICCAD)

作者： Wang, Jia Chen, Xiaodao Liao, Chen Hu, Shiyan Michigan Technol Univ Dept Elect & Comp Engn Houghton MI 49931 USA

ISBN: (纸本)9781457713989

With advancing technology, large dynamic power consumption has significantly limited circuit miniaturization. Minimizing peak power consumption, which is defined as the maximum power consumption among all voltage partitions, is important since it enables energy saving from the voltage island shutdown mechanism. In this paper, we prove that the peak power driven voltage partitioning problem is NP-complete and propose an efficient provably good fully polynomial time approximation scheme for it. The new algorithm can approximate the optimal peak power driven voltage partitioning solution in O(m(2)(mn/epsilon(4))(m)) time within a factor of (1 + epsilon) for sufficiently small positive epsilon, where n is the number of circuit blocks and m is the number of partitions which is a small constant in practice. Our experimental results demonstrate that the dynamic programming cannot finish for even 20 blocks while our new approximation algorithm runs fast. In particular, varying epsilon, orders of magnitude speedup can be obtained with only 0.6% power increase. The tradeoff between the peak power minimization and the total power minimization is also investigated. We demonstrate that the total power minimization algorithm obtains good results in total power but with quite large peak power, while our peak power optimization algorithm can achieve on average 26.5% reduction in peak power with only 0.46% increase in total power. Moreover, our peak power driven voltage partitioning algorithm is integrated into a simulated annealing based floorplanning technique. Experimental results demonstrate that compared to total power driven floorplanning, the peak power driven floorplanning can significantly reduce peak power with only little impact in total power, HPWL, estimated power ground routing cost, level shifter cost and runtime. Further, when the voltage island shutdown is performed, peak power driven voltage partitioning can lead to over 10% more energy saving than a greedy frequen

关键词： Voltage Partitioning fully polynomial time approximation scheme NP-Complete Peak Power Minimization Voltage Island Shutdown

来源：评论

学校读者我要写书评

暂无评论

polynomial approximation schemes for the Max-Min Allocation Problem under a Grade of Service Provision

Polynomial Approximation Schemes for the Max-Min Allocation ...

引用

3rd International Conference on Combinatorial Optimization and Applications (COCOA 2009)

作者： Li, Jianping Li, Weidong Li, Jianbo Yunnan Univ Dept Math Kunming 650091 Peoples R China Kunming Univ Sci & Tech Sch Management & Econ Kunming Peoples R China

ISBN: (纸本)9783642020254

The max-min allocation problem under a grade of service provision is defined in the following model: given a set, M of m parallel machines and a set J of n jobs, where machines and jobs are all entitled to different levels of grade of service (GoS), each job J(j) is an element of J has its processing time p(j) and it is only allocated to a machine M-i whose COS level is no more than the GoS level the job J(j) has. The goal is to allocate all jobs to Tit machines to maximize the minimum. Machine load, where the machine load of machine M-i is the sum of the precessing times of jobs executed on M-i. The best approximation algorithm [4] to solve this problem produces an allocation in which the minimum machine completion time is at least Omega(logloglogm/loglogm.) of the optimal value. In this paper, we respectively present. four approximation schemes to solve this problem and its two special versions: (1) a polynomial time approximation scheme (PTAS) with running time O(mn(O(1/epsilon 2))) for the general version, where epsilon > 0: (2) a PTAS and an fully polynomial time approximation scheme (FPTAS) with running time O(n) for the version where the number m of machines is fixed;(3) a PTAS with running time O(n.) for the version where the number of COS levels is bounded by k.

关键词： Scheduling allocation grade of service polynomial time approximation scheme fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

A Faster approximation scheme For Timing Driven Minimum Cost Layer Assignment

A Faster Approximation Scheme For Timing Driven Minimum Cost...

引用

ACM International Symposium on Physical Design

作者： Hu, Shiyan Li, Zhuo Alpert, Charles J. Michigan Technol Univ Dept Elect & Comp Engn Houghton MI 49931 USA

ISBN: (纸本)9781605584492

As VLSI technology moves to the 65nm node and beyond, interconnect delay greatly limits the circuit performance. As a critical component in interconnect synthesis, layer assignment manifests enormous potential in drastically reducing wire delay. This is clue the fact that wires on thick metals are much less resistive than those on thin metals. Nevertheless, it is not desired to assign all wires to thick metals and the right strategy is to only use minimal thick-metal routing resources for meeting the timing constraints. This timing driven minimum cost layer assignment problem is NP-Complete, and a fast algorithm with provable approximation bound is highly desired. In this paper, a new fully polynomial time approximation scheme is proposed. It is based on a linear-time dynamic programming algorithm for bounded-cost layer assignment and efficient oracle queries. The proposed algorithm can approximate the optimal layer assignment solution in O(mn(2)/epsilon) time within a factor of 1 + epsilon for any epsilon > 0, where n is the tree size and 771 is the number of routing layers. This significantly improves the previous work. The new algorithm is also highly practical. Our experiments on industrial netlists demonstrate that the new algorithm runs UP to 6.5x faster than the optimal dynamic programming with few percent additional wire as guaranteed theoretically. This gives another > 2x speedup over the previous work.

关键词： Layer Assignment fully polynomial time approximation scheme NP-Complete Oracle Dynamic Programming

来源：评论

学校读者我要写书评

暂无评论

How to sell a graph: Guidelines for graph retailers

引用

32nd International Workshop on Graph-Theoretic Concepts in Computer Science

作者： Grigoriev, Alexander van Loon, Joyce Sitters, Rene Uetz, Marc Maastricht Univ POB 616 NL-6200 MD Maastricht Netherlands Max Planck Inst Informat Algorithms & Complex D-66123 Saarbrucken Germany

ISBN: (纸本)3540483810

We consider a profit maximization problem where we are asked to price a set of m items that are to be assigned to a set of n customers. The items can be represented as the edges of an undirected (multi)graph G, where an edge multiplicity larger than one corresponds to multiple copies of the same item. Each customer is interested in purchasing a bundle of edges of G, and we assume that each bundle forms a simple path in G. Each customer has a known budget for her respective bundle, and is interested only in that particular bundle. The goal is to determine item prices and a feasible assignment of items to customers in order to maximize the total profit. When the underlying graph G is a path, we derive a fully polynomial time approximation scheme, complementing a recent NP-hardness result. If the underlying graph is a tree, and edge multiplicities are one, we show that the problem is polynomially solvable, contrasting its APX-hardness for the case of unlimited availability of items. However, if the underlying graph is a grid, and edge multiplicities are one, we show that it is even NP-complete to approximate the maximum profit to within a factor n(1-epsilon).

关键词： pricing problems tollbooth problem highway problem computational complexity dynamic programming fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：