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

SUPER-POLYNOMIAL APPROXIMATION branching algorithmS

RAIRO-OPERATIONS RESEARCH 2016年第4-5期50卷 979-994页

作者： Escoffier, Bruno Paschos, Vangelis Th. Tourniaire, Emeric UPMC Univ Paris 06 Sorbonne Univ CNRS UMR 7606LIP6 4 Pl Jussieu F-75005 Paris France Univ Paris 09 PSL Res Univ LAMSADE CNRSUMR 7243 Paris France

We give sufficient conditions for deriving moderately exponential and/or parameterized time approximation schemata (i.e., algorithms achieving ratios 1 +/- epsilon, for arbitrarily small epsilon) for broad classes of combinatorial optimization problems via a well-known technique widely used for deriving exact algorithms, namely the branching tree pruning.

关键词： branching algorithm moderately exponential approximation approximation schema

来源：评论

学校读者我要写书评

暂无评论

Exact rates of convergence for a branching particle approximation to the solution of the Zakai equation

引用

ANNALS OF PROBABILITY 2003年第2期31卷 693-718页

作者： Crisan, D Univ London Imperial Coll Sci Technol & Med Dept Math London SW7 2BZ England

In Crisan, Gaines and Lyons [SIAM J Appl. Probab. 58 (1998) 313-3421 we describe a branching particle algorithm that produces a particle approximation to the solution of the Zakai equation and find an upper bound for the rate of convergence of the mean square error. In this paper, the exact rate of convergence of the mean square error is deduced. Also, several variations of the branching algorithm with better rates of convergence are introduced.

关键词： Zakai equation branching algorithm particle filters filtering Monte Carlo approximation

来源：评论

学校读者我要写书评

暂无评论

Estimation of tree root lengths using fractal branching rules:: a comparison with soil coring for Grevillea robusta

引用

PLANT AND SOIL 2001年第2期229卷 295-304页

作者： Smith, DM Ctr Ecol & Hydrol Wallingford OX10 8BB Oxon England

Previous theoretical research has suggested that lengths of tree roots can be estimated on the basis of their branching characteristics, if branching has a fractal pattern that is independent of root diameter. This theory and its underlying assumptions was tested for Grevillea robusta trees at a site in Kenya by comparing estimates of root length from conventional soil coring and the output of a fractal branching algorithm. The trees were in a 4-year-old stand established on a 3 x 4 m planting grid. Root lengths (L-r) in four units of the planting grid were estimated by soil coring. branching characteristics determined by examination of 32 excavated roots from 16 trees were: The number of branches at each branching point;the length of links between branching points (L-l);the diameter of root tips;and parameters which describe the change in diameter at each branching point. Each was found to be independent of root size. These data were used to parameterise a branching algorithm, which was then used to estimate numbers of root links in the four grid units (n(l)) from root diameters at the bases of the four trees at the corners of each unit. Root lengths, from (L) over cap (r) = n(1) L-1, severely underestimated L-r. This discrepancy probably resulted from inaccuracy in the parameterisation of the branching algorithm, as output from the algorithm was very sensitive to small changes in parameter values. Use of fractal branching rules alone to estimate roots length does not appear possible unless the algorithm is calibrated to adjust for errors in parameter estimation. Calibration can be achieved by calculation of an 'effective link length', L-1(eff), from L-r/n(l), where L-r is measured by a reference method such as soil coring.

关键词： branching algorithm calibration root branching root length estimation root system size

来源：评论

学校读者我要写书评

暂无评论

Interval branching 08

Interval branching

引用

22nd International Workshop on Principles of Advanced and Distributed Simulation

作者： Peschlow, Patrick Martini, Peter Liu, Jason Univ Bonn Dept Comp Sci 4 Roemerstr 164 D-53117 Bonn Germany Florida Int Univ Sch Comp & Informat Sci Miami FL 33199 USA

ISBN: (纸本)9780769531595

We propose a new simulation method, called interval branching, which aims to facilitate efficient simulation studies of systems that involve temporal uncertainty. The method uses interval timestamps for events and explores different execution orders of overlapping events by branching the simulation. We first present a sequential version of interval branching, and then extend it to parallel simulation using the logical process paradigm. The parallel interval branching algorithm uses the logical-process cloning technique for efficient computation of branches. Our preliminary experiments show its potential as an efficient method for discrete-event simulation studies.

关键词： branches analog approach simulating discrete event simulation Event driven simulation branching algorithm

来源：评论

学校读者我要写书评

暂无评论

An improved algorithm for the (n, 3)-MaxSAT problem: asking branchings to satisfy the clauses

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2021年第3期42卷 524-542页

作者： Xu, Chao Li, Wenjun Wang, Jianxin Yang, Yongjie Cent South Univ Sch Comp Sci & Engn Changsha Peoples R China Changsha Univ Sci & Technol Hunan Prov Key Lab Intelligent Proc Big Data Tran Changsha Peoples R China Saarland Univ Econ Theory Saarbrucken Germany

We study the (n, 3)-MaxSAT problem where we are given an integer k and a CNF formula with n variables, each of which appears in at most 3 clauses, and the question is whether there is an assignment that satisfies at least k clauses. Based on refined observations, we propose a branching algorithm for the (n, 3)-MaxSAT problem which significantly improves the previous results. More precisely, the running time of our algorithm can be bounded by O* (1.175(k)) and O* (1.194(n)), respectively. Prior to our study, the running time of the best known exact algorithm can be bounded by O* (1.194(k)) and O*(1.237n), respectively.

关键词： CNF formula 3-SAT branching algorithm Complexity Parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Parameterized computational complexity of finding small-diameter subgraphs

引用

OPTIMIZATION LETTERS 2012年第5期6卷 883-891页

作者： Schaefer, Alexander Komusiewicz, Christian Moser, Hannes Niedermeier, Rolf Tech Univ Berlin Inst Softwaretech & Theoret Informat D-10587 Berlin Germany Max Planck Inst Human Cognit & Brain Sci Dept Neurol D-04103 Leipzig Germany Univ Jena Inst Informat D-07743 Jena Germany

Finding subgraphs of small diameter in undirected graphs has been seemingly unexplored from a parameterized complexity perspective. We perform the first parameterized complexity study on the corresponding NP-hard s-Cl... 详细信息

关键词： Clique relaxation s-Club NP-hard problem Problem kernel Polynomial-time preprocessing branching algorithm

来源：评论

学校读者我要写书评

暂无评论

Partition on trees with supply and demand: Kernelization and algorithms

引用

THEORETICAL COMPUTER SCIENCE 2017年第PartA期657卷 11-19页

作者： Lin, Mugang Feng, Qilong Chen, Jianer Li, Wenjun Cent S Univ Sch Informat Sci & Engn Changsha Hunan Peoples R China Hengyang Normal Univ Sch Comp Sci & Technol Hengyang Peoples R China Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA Changsha Univ Sci & Technol Sch Comp & Commun Engn Hunan Prov Key Lab Intelligent Proc Big Data Tran Changsha Hunan Peoples R China

Network reconfiguration is an important research topic in the planning and operation of power distribution networks. In this paper, we study the partition problem on trees with supply and demand from parameterized computation perspective. We analyze the relationship between supply nodes and demand nodes, and give four reduction rules, which result in a kernel of size O(k(2)) for the problem. Based on branching technique, a parameterized algorithm of running time O*(2.828(k)) is presented. (C) 2016 Published by Elsevier B.V.

关键词： Fixed-parameter tractability Network reconfiguration Kemelizaton branching algorithm

来源：评论

学校读者我要写书评

暂无评论

Matching cut: Kernelization, single-exponential time FPT, and exact exponential algorithms

引用

DISCRETE APPLIED MATHEMATICS 2020年 283卷 44-58页

作者： Komusiewicz, Christian Kratsch, Dieter Le, Van Bang Philipps Univ Marburg Fachbereich Math & Informat Marburg Germany Univ Lorraine Lab Genie Informat Prod & Maintenance Metz France Univ Rostock Inst Informat Rostock Germany

In a graph, a matching cut is an edge cut that is a matching. Matching Cut, which is known to be NP-complete, is the problem of deciding whether or not a given graph G has a matching cut. In this paper we show that Matching Cut admits a quadratic-vertex kernel for the parameter distance to cluster and a linear-vertex kernel for the parameter distance to clique. We further provide an O*(2(dc(G)))-time and an O*((2d (c) over bar (G)))-time FPT algorithm for MATCHING CUT, where dc(G) and d((c) over bar)(G) are the distance to cluster and distance to co-cluster, respectively. We also improve the running time of the best known branching algorithm to solve Matching Cut from O*(1.4143(n)) to O*(1.3071(n)) where n is the number of vertices in G. Moreover, we point out that, unless NP subset of coNP/poly, Matching Cut does not admit a polynomial kernel when parameterized simultaneously by treewidth, the number of edges crossing the cut, and the maximum degree of G. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Graph problem NP-hard problem Kernelization branching algorithm

来源：评论

学校读者我要写书评

暂无评论

COST OPTIMIZATION OF MAINTENANCE SCHEDULING FOR A SYSTEM WITH ASSURED RELIABILITY

引用

IEEE TRANSACTIONS ON RELIABILITY 1992年第1期41卷 21-25页

作者： JAYABALAN, V CHAUDHURI, D INDIAN INST TECHNOL DEPT HUMANITIES & SOCIAL SCIMADRAS 600036TAMIL NADUINDIA

Systems which have to work at or below a maximum acceptable failure rate, should be maintained at predetermined points such that the failure rate does not exceed the acceptable level. As the system ages, the post-maintenance failure rate of the system drops to some newer one, unless the system has been replaced, but does not restore the system to the original state. This paper presents a branching algorithm with effective dominance rules that curtail the number of nodes created;this algorithm determines the number of maintenance interventions before each replacement in order to minimize the total cost over a finite time horizon. The model considers inflationary trends. A numerical example and computational experience demonstrate the algorithm. Most papers on maintenance problems have considered the maintenance interval as constant and increasing cost for successive maintenance for a system. This paper treats the maintenance cost as constant and successive simple-maintenance intervals as decreasing. Though our algorithm assumes that the cost/maintenance is constant, any increasing maintenance cost function could be incorporated. The optimum solutions depend on the: constant improvement factor first simple-maintenance point rate of increase in acquisition cost maintenance cost factor planning period.

关键词： SIMPLE PREVENTIVE MAINTENANCE PREVENTIVE REPLACEMENT IMPROVEMENT FACTOR branching algorithm

来源：评论

学校读者我要写书评

暂无评论

SPLIT VERTEX DELETION meets VERTEX COVER: New fixed-parameter and exact exponential-time algorithms

引用

INFORMATION PROCESSING LETTERS 2013年第5-6期113卷 179-182页

作者： Cygan, Marek Pilipczuk, Marcin Univ Lugano IDSIA Lugano Switzerland Univ Warsaw Inst Informat PL-00325 Warsaw Poland

In the SPLIT VERTEX DELETION problem, given a graph G and an integer k, we ask whether one can delete k vertices from the graph G to obtain a split graph (i.e., a graph, whose vertex set can be partitioned into two sets: one inducing a clique and the second one inducing an independent set). In this paper we study exact (exponential-time) and fixed-parameter algorithms for SPLIT VERTEX DELETION. We show that, up to a factor quasipolynomial in k and polynomial in n, the SPLIT VERTEX DELETION problem can be solved in the same time as the well-studied VERTEX COVER problem. By plugging in the currently best fixed-parameter algorithm for VERTEX COVER due to Chen et al. [Theor. Comput Sci. 411 (40-42) (2010) 3736-3756], we obtain an algorithm that solves SPLIT VERTEX DELETION in time O(-1.2738(k)k(O(logk)) + n(3)). We show that all maximal induced split subgraphs of a given n-vertex graph can be listed in O(3(n/3) n(O(logn))) time. To achieve our goals, we prove the following structural result that may be of independent interest: for any graph G we may compute a family P of size n(O(logn)) containing partitions of V(C) into two parts, such that for any two disjoint sets X-C, X-I subset of V (G) where G[X-C] is a clique and G[X-I] is an independent set, there is a partition in P which contains all vertices of X-C on one side and all vertices of X-I on the other. Moreover, the family P can be enumerated in O(n(O(logn))) time. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Fixed-parameter algorithms Split graphs Split vertex deletion branching algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：