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

asymptotic Quasi-Polynomial Time approximation scheme for Resource Minimization for Fire Containment

ALGORITHMICA 2022年第9期84卷 2462-2479页

作者： Rahgoshay, Mirmahdi Salavatipour, Mohammad R. Univ Alberta Dept Comp Sci Edmonton AB Canada

Resource Minimization Fire Containment (RMFC) is a natural model for optimal inhibition of harmful spreading phenomena on a graph. In the RMFC problem on trees, we are given an undirected tree G, and a vertex r where the fire starts at, called root. At each time step, the firefighters can protect up to B vertices of the graph while the fire spreads from burning vertices to all their neighbors that have not been protected so far. The task is to find the smallest B that allows for saving all the leaves of the tree. The problem is hard to approximate up to any factor better than 2 even on trees unless P= NP (King and MacGillivray in Discret Math 310(3):614-621, 2010). Chalermsook and Chuzhoy (In: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, Texas, USA, 17-19 Jan 2010, SIAM, pp 1334-1349, 2010) presented a Linear Programming (LP) based O (log* n) approximation for RMFC on trees that matches the integrality gap of the natural Linear Programming relaxation. This was recently improved by Adjiashvili et al. (ACM Trans Algorithms 15(2):20:1-20:33, 2019) to a 12-approximation through a combination of LP rounding along with several new techniques. In this paper we present an asymptotic QPTAS for RMFC on trees. More specifically, let epsilon > 0, and I be an instance of RMFC where the optimum number of firefighters to save all the leaves is OPT (I). We present an algorithm which uses at most inverted right perpendicular(1 + epsilon) O PT (I)inverted left perpendicular many firefighters at each time step and runs in time n(O(log log n/)(epsilon)). This suggests that the existence of an asymptotic PTAS is plausible especially since the exponent is O(log log n), not O(log n). Our result combines a more refined height reduction lemma than the one in Adjiashvili et al. (2019) with LP rounding and dynamic programming to find the solution. We also apply our height reduction lemma to the algorithm provided in Adjiashvili et al. (2019) plu

关键词： Firefighter problem Resource management Fire containment approximation algorithm asymptotic approximation scheme

来源：评论

学校读者我要写书评

暂无评论

asymptotic Quasi-Polynomial Time approximation scheme for Resource Minimization for Fire Containment 37

Asymptotic Quasi-Polynomial Time Approximation Scheme for Re...

引用

37th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Rahgoshay, Mirmahdi Salavatipour, Mohammad R. Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

ISBN: (纸本)9783959771405

Resource Minimization Fire Containment (RMFC) is a natural model for optimal inhibition of harmful spreading phenomena on a graph. In the RMFC problem on trees, we are given an undirected tree G, and a vertex r where the fire starts at, called root. At each time step, the firefighters can protect up to B vertices of the graph while the fire spreads from burning vertices to all their neighbors that have not been protected so far. The task is to find the smallest B that allows for saving all the leaves of the tree. The problem is hard to approximate up to any factor better than 2 even on trees unless P = NP [11]. Chalermsook and Chuzhoy [6] presented a Linear Programming based O(log* n) approximation for RMFC on trees that matches the integrality gap of the natural Linear Programming relaxation. This was recently improved by Adjiashvili, Baggio, and Zenklusen [1] to a 12-approximation through a combination of LP rounding along with several new techniques. In this paper we present an asymptotic QPTAS for RMFC on trees. More specifically, let is an element of > 0, and I be an instance of RMFC where the optimum number of firefighters to save all the leaves is OPT (I). We present an algorithm which uses at most [(1 - is an element of)OPT(I)] many firefighters at each time step and runs in time n(O()(log log n/)(is an element of)). This suggests that the existence of an asymptotic PTAS is plausible especially since the exponent is O(log log n), not O(log n). Our result combines a more powerful height reduction lemma than the one in [1] with LP rounding and dynamic programming to find the solution. We also apply our height reduction lemma to the algorithm provided in [1] plus a more careful analysis to improve their 12-approximation and provide a polynomial time (5 + is an element of)-approximation.

关键词： Firefighter Problem Resource Management Fire Containment approximation Algorithm asymptotic approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Polynomial-Time approximation schemes for Circle and Other Packing Problems

引用

ALGORITHMICA 2016年第2期76卷 536-568页

作者： Miyazawa, Flavio K. Pedrosa, Lehilton L. C. Schouery, Rafael C. S. Sviridenko, Maxim Wakabayashi, Yoshiko Univ Estadual Campinas Inst Comp Campinas SP Brazil Univ Sao Paulo Dept Comp Sci Sao Paulo Brazil Yahoo Labs New York NY USA

We consider the problem of packing a set of circles into a minimum number of unit square bins. To obtain rational solutions, we use augmented bins of height , for some arbitrarily small number . For this problem, we obtain an asymptotic approximation scheme (APTAS) that is polynomial on , and thus may be given as part of the problem input. For the special case that is constant, we give a (one dimensional) resource augmentation scheme, that is, we obtain a packing into bins of unit width and height using no more than the number of bins in an optimal packing without resource augmentation. Additionally, we obtain an APTAS for the circle strip packing problem, whose goal is to pack a set of circles into a strip of unit width and minimum height. Our algorithms are the first approximation schemes for circle packing problems, and are based on novel ideas of iteratively separating small and large items, and may be extended to a wide range of packing problems that satisfy certain conditions. These extensions comprise problems with different kinds of items, such as regular polygons, or with bins of different shapes, such as circles and spheres. As an example, we obtain APTAS's for the problems of packing d-dimensional spheres into hypercubes under the L-p-norm.

关键词： Circle bin packing Circle strip packing asymptotic approximation scheme Resource augmentation scheme Sphere packing Algebraic algorithms

来源：评论

学校读者我要写书评

暂无评论

An asymptotic fully polynomial time approximation scheme for bin covering

引用

THEORETICAL COMPUTER SCIENCE 2003年第1-3期306卷 543-551页

作者： Jansen, K Solis-Oba, R Univ Western Ontario Dept Comp Sci London ON N6A 5B7 Canada Univ Kiel Inst Informat & Prakt Math Kiel Germany

In the bin covering problem there is a group L = (a(l),..., a(n)) of items with sizes (s) over tilde (a(i)) is an element of (0, 1), and the goal is to find a packing of the items into bins to maximize the number of bins that receive items of total size at least 1. This is a dual problem to the classical bin packing problem. In this paper we present the first asymptotic fully polynomial-time approximation scheme for the problem. (C) 2003 Elsevier B.V. All rights reserved.

关键词： asymptotic approximation scheme bin covering linear programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：