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

fully polynomial time approximation scheme to maximize early work on parallel machines with common due date

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2020年第1期284卷 67-74页

作者： Chen, Xin Liang, Yage Sterna, Malgorzata Wang, Wen Blazewicz, Jacek Liaoning Univ Technol Sch Elect & Informat Engn Shiying Jinzhou 121001 Peoples R China Dalian Univ Technol Sch Software Tuqiang 321 Dalian 116023 Peoples R China Poznan Univ Tech Inst Comp Sci Piorrowo 2 PL-60965 Poznan Poland Polish Acad Sci Inst Bioorgan Chem Noskowskiego 12-14 PL-61704 Poznan Poland European Ctr Bioinformat & Genom Piotrowo 2 PL-60965 Poznan Poland

We study the scheduling problem on parallel identical machines in order to maximize the total early work, i.e. the parts of non-preemptive jobs executed before a common due date, and investigate mainly the model with a fixed number of machines, for which a dynamic programming approach and a fully polynomial time approximation scheme (FPTAS) are proposed. The proposal of these methods allowed us to establish the complexity and approximability status of this problem more exactly. Moreover, since our FPTAS can be also applied for the two-machine case, we improve considerably the result known in the literature for this model, in which a polynomial time approximation scheme (PTAS) was given. The new FPTAS has not only the best computational complexity, but also the much better approximation ratio than the PTAS. Finally, the theoretical studies are completed with computational experiments, performed for dynamic programming, PTAS and FPTAS, showing the high efficiencies of FPTAS both in terms of time consumption and solution quality. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Scheduling Parallel identical machines Early work Late work fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

A new fully polynomial time approximation scheme for the interval subset sum problem

引用

JOURNAL OF GLOBAL OPTIMIZATION 2017年第4期68卷 749-775页

作者： Diao, Rui Liu, Ya-Feng Dai, Yu-Hong Chinese Acad Sci Acad Math & Syst Sci Inst Computat Math & Sci Engn Comp State Key Lab Sci & Engn Comp Beijing 100190 Peoples R China

The interval subset sum problem (ISSP) is a generalization of the well-known subset sum problem. Given a set of intervals {[a(i), 1, a(i,2) ](i=1)(n) and a target integer T, the ISSP is to find a set of integers, at most one from each interval, such that their sum best approximates the target T but cannot exceed it. In this paper, we first study the computational complexity of the ISSP. We show that the ISSP is relatively easy to solve compared to the 0-1 knapsack problem. We also identify several subclasses of the ISSP which are polynomial time solvable (with high probability), albeit the problem is generally NP-hard. Then, we propose a new fully polynomial time approximation scheme for solving the general ISSP problem. The time and space complexities of the proposed scheme are O (n max {1/epsilon, log n} and O (n+1/epsilon), respectively, where epsilon is the relative approximation error. To the best of our knowledge, the proposed scheme has almost the same time complexity but a significantly lower space complexity compared to the best known scheme. Both the correctness and efficiency of the proposed scheme are validated by numerical simulations. In particular, the proposed scheme successfully solves ISSP instances with n = 100,000 and epsilon = 0.1% within 1 s.

关键词： Interval subset sum problem Computational complexity Solution structure fully polynomial time approximation scheme Worst-case performance

来源：评论

学校读者我要写书评

暂无评论

A fully polynomial time approximation scheme for Timing Driven Minimum Cost Buffer Insertion 09

A Fully Polynomial Time Approximation Scheme for Timing Driv...

引用

46th ACM/IEEE Design Automation Conference (DAC 2009)

作者： Hu, Shiyan Li, Zhuo Alpert, Charles J. Michigan Technol Univ Dept Elect & Comp Engn Houghton MI 49931 USA IBM Corp Austin Res Lab Austin TX 78758 USA

ISBN: (纸本)9781605584973

As VLSI technology enters the nanoscale regime, interconnect delay has become the bottleneck of the circuit timing. As one of the most powerful techniques for interconnect optimization, buffer insertion is indispensable in the physical synthesis flow. Buffering is known to be NP-complete and existing works either explore dynamic programming to compute optimal solution in the worst-case exponential time or design efficient heuristics without performance guarantee. Even if buffer insertion is one of the most studied problems in physical design, whether there is an efficient algorithm with provably good performance still remains unknown. This work settles this open problem. In the paper, the first fully polynomial time approximation scheme for the timing driven minimum cost buffer insertion problem is designed. The new algorithm can approximate the optimal buffering solution within a factor of 1 + epsilon running in O(m(2)n(2)b/epsilon(3) + n(3)b(2)/epsilon) time for any 0 < epsilon < 1, where n is the number of candidate buffer locations, m is the number of sinks in the tree, and b is the number of buffers in the buffer library. In addition to its theoretical guarantee, our experiments on 1000 industrial nets demonstrate that compared to the commonly-used dynamic programming algorithm, the new algorithm well approximates the optimal solution, with only 0.57% additional buffers and 4.6x speedup. This clearly demonstrates the practical value of the new algorithm.

关键词： Buffer Insertion fully polynomial time approximation scheme NP-complete Cost Minimization Dynamic Programming

来源：评论

学校读者我要写书评

暂无评论

A fully polynomial time approximation scheme for Adaptive Variable Rate Task Demand 24

A Fully Polynomial Time Approximation Scheme for Adaptive Va...

引用

32nd International Conference on Real-time Networks and Systems

作者： Willcock, Aaron Fisher, Nathan Chantem, Thidapat (Tam) Wayne State Univ Detroit MI 48202 USA Virginia Polytech Inst & State Univ Arlington VA USA State Univ Arlington Arlington VA USA

ISBN: (纸本)9798400717246

The Adaptive Variable Rate (AVR) task model defines a task where job WCET and period are a function of engine speed. Motivated by a lack of tractable AVR task demand methods, this work uses predefined job sequences for the Bounded Precedence Constraint Knapsack Problem inherent in AVR task demand calculation instead of enumerating all considered speeds as in existing work. A new, exact approach is proposed and approximated, enabling the derivation of a fully polynomial time approximation scheme that outperforms the state-of-the-art in runtime (7,800x improvement) and RAM use (99% reduction) with less than 8% demand overestimate.

关键词： Adaptive variable rate task demand bounded precedence constraint knapsack problem fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

A polynomial time approximation scheme for minimum cost delay-constrained multicast tree under a Steiner topology

引用

ALGORITHMICA 2005年第1期41卷 53-72页

作者： Xue, GL Xiao, W Arizona State Univ Dept Comp Sci & Engn Tempe AZ 85287 USA Univ Vermont Dept Comp Sci Burlington VT 05405 USA

This paper is concerned with a restricted version of minimum cost delay-constrained multicast in a network where each link has a delay and a cost. Given a source vertex s and p destination vertices t(1), t(2),...,t(p) 14 together with p corresponding nonnegative delay constraints d(1), d(2),...,d(p), many QoS multicast problems seek a minimum cost multicast tree in which the delay along the unique s-t(i) path is no more than d(i) for 1less than or equal toiless than or equal top. This problem is NP-hard even when the topology of the multicast tree is fixed. In this paper we show that every multicast tree has an underlying Steiner topology and that every minimum cost delay-constrained multicast tree corresponds to a minimum cost delay-constrained realization of a corresponding Steiner topology. We present a fully polynomial time approximation scheme for computing a minimum cost delay-constrained multicast tree under a Steiner topology. We also present Computational results of a preliminary implementation to illustrate the effectiveness of our algorithm and discuss its applications.

关键词： computer communications mininum cost delay-constrained network under a Steiner topology fully polynomial time approximation scheme quality of service

来源：评论

学校读者我要写书评

暂无评论

The K-prize-collecting coverage problem by aligned disks

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2025年

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

In this paper, we study the K-prize-collecting coverage problem by using aligned disks. 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 I., where each user corresponds to a coordinate point, with an associated profit and an uncovered penalty. The problem is to select a set D of disks whose centers are all in S such that the total profit of the users covered by D' is at least K, and the objective value, which consists of the total cost of the disks in D' plus the total penalty of the uncovered users in U\U (D'), is minimized, where the cost of disk D is r(D)(alpha), alpha >= 1 is an attenuation factor, r(D) is the radius of disk D, and K is a given profit bound. We first prove that this problem is NP-hard even when all users are located on line L, alpha=1 and the penalty of each user is 0. We present a pseudo-polynomial-time algorithm. Finally, we present a fully polynomial time approximation scheme for the problem.

关键词： disk coverage problem K-prize-collecting dynamic programming fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

TheK$K$-prize-collecting coverage problem by aligned disks

引用

International Transactions in Operational Research 2025年

作者： Hao Zhang Xiya Zheng Zhonghao Liu Xiaofei Liu School of Information Science and Engineering Yunnan University Kunming 650500 China School of Mathematics and Statistics Yunnan University Kunming 650500 China

In this paper, we study the K $K$ -prize-collecting coverage problem by using aligned disks. Suppose U $U$ is a set of users, L $L$ is a horizontal line on the plane, and S $S$ is a set of points on the line L $L$ , where each user corresponds to a coordinate point, with an associated profit and an uncovered penalty. The problem is to select a set D ′ $\mathcal {D}^{\prime }$ of disks whose centers are all in S $S$ such that the total profit of the users covered by D ′ $\mathcal {D}^{\prime }$ is at least K $K$ , and the objective value, which consists of the total cost of the disks in D ′ $\mathcal {D}^{\prime }$ plus the total penalty of the uncovered users in U ∖ U ⁡ ( D ′ ) $U\setminus U(\mathcal {D}^{\prime })$ , is minimized, where the cost of disk D $D$ is r ⁢ ( D ) α $r(D)^{\alpha }$ , α ≥ 1 $\alpha \ge 1$ is an attenuation factor, r ⁡ ( D ) $r(D)$ is the radius of disk D $D$ , and K $K$ is a given profit bound. We first prove that this problem is N ⁢ P $NP$ -hard even when all users are located on line L $L$ , α = 1 $\alpha =1$ and the penalty of each user is 0. We present a pseudo-polynomial-time algorithm. Finally, we present a fully polynomial time approximation scheme for the problem.

关键词： disk coverage problem K$K$-prize-collecting dynamic programming fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Recursive functions on the plane and FPTASs for production planning and scheduling problems with two facilities

引用

MATHEMATICAL METHODS OF OPERATIONS RESEARCH 2009年第2期70卷 313-335页

作者： Chubanov, Sergei Pesch, Erwin Univ Siegen Inst Informat Syst Siegen Germany

We consider a production model with two facilities sharing a resource during a time horizon consisting of a number of time periods. Cumulative production levels at the ends of consecutive periods are linked with constraints of a general form. This allows us to give different interpretations related to scheduling and input-output analysis. The model may arise either separately or in the structure of more general production models. In both cases it is reasonable to find an optimal or near-optimal distribution of resources between these two facilities. This helps either to develop a new production plan or to improve an existing one. The problem in question is NP-hard. We show that our approach leads to fully polynomial time approximation schemes (FPTASs).

关键词： Scheduling Input-output model Dynamic programming fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

A single-item economic lot-sizing problem with a non-uniform resource: approximation

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2008年第3期189卷 877-889页

作者： Chubanov, Sergei Kovalyov, Mikhail Y. Pesch, Erwin Univ Siegen Inst Informat Syst D-57068 Siegen Germany Belarusian State Univ Fac Econ Minsk BELARUS Natl Acad Sci United Inst Informat Problems Minsk BELARUS

We study a generalization of the classical single-item capacitated economic lot-sizing problem to the case of a non-uniform resource usage for production. The general problem and several special cases are shown to be non-approximable with any polynomially computable relative error in polynomial time. An optimal dynamic programming algorithm and its approximate modification are presented for the general problem. fully polynomial time approximation schemes are developed for two NP-hard special cases: (1) cost functions of total production are separable and holding and backlogging cost functions are linear with polynomially related slopes, and (2) all holding costs are equal to zero. (C) 2007 Elsevier B.V. All rights reserved.

关键词： lot-sizing dynamic programming fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Knapsack problem with objective value gaps

引用

OPTIMIZATION LETTERS 2017年第1期11卷 31-39页

作者： Dolgui, Alexander Kovalyov, Mikhail Y. Quilliot, Alain Ecole Mines Nantes CNRS UMR 6597 IRCCYN 4 Rue Alfred KastlerBP 20722 F-44307 Nantes 3 France Natl Acad Sci Belarus United Inst Informat Problems Minsk BELARUS Univ Blaise Pascal CNRS LIMOS UMR 6158Bat ISIMA Campus CezeauxBP 125 F-63173 Aubiere France

We study a 0-1 knapsack problem, in which the objective value is forbidden to take some values. We call gaps related forbidden intervals. The problem is NP-hard and pseudo-polynomially solvable independently on the measure of gaps. If the gaps are large, then the problem is polynomially non-approximable. A non-trivial special case with respect to the approximate solution appears when the gaps are small and polynomially close to zero. For this case, two fully polynomial time approximation schemes are proposed. The results can be extended for the constrained longest path problem and other combinatorial problems.

关键词： Knapsack problem Computational complexity fully polynomial time approximation scheme Forbidden values

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：