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

exact and approximation algorithms for finding an optimal bridge connecting two simple polygons

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2005年第6期15卷 609-630页

作者： Bhosle, AM Gonzalez, TF Amazon Software Dev Ctr Bangalore 560001 Karnataka India Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA

Given two simple polygons P and Q we define the weight of a bridge (p, q), with p is an element of rho(p) and q is an element of rho(Q), where rho() denotes the compact region enclosed by the boundary of the polygon, between the two polygons as gd(p, P) + d(p, q) + gd(q, Q), where d(p, q) is the Euclidean distance between the points p and q, and gd(x, X) is the geodesic distance between x and its geodesic furthest neighbor on X. Our problem differs from another version of the problem where the additional restriction of requiring the endpoints of the bridge to be mutually visible was imposed. We show that an optimal bridge always exists such that the endpoints of the bridge lie on the boundaries of the two polygons. Using this critical property, we present an algorithm to find an optimal bridge (of minimum weight) in O(n(2) log n) time. We present a polynomial time approximation scheme that for any epsilon > 0 generates a bridge with objective function within a factor of 1 + epsilon of the optimal value in O(kn log kn) time, where k = 2 * [1/log(1+epsilon)]. An improved polynomial time approximation scheme and algorithms for generalized versions of our problems are also discussed.

关键词： optimal bridge between polygons polynomial time approximation scheme exact algorithm

来源：评论

学校读者我要写书评

暂无评论

One and two facility network design revisited

引用

ANNALS OF OPERATIONS RESEARCH 2001年第1-4期108卷 19-31页

作者： Sastry, T Indian Inst Management Ahmedabad 380015 Gujarat India

The one facility one commodity network design problem (OFOC) with nonnegative flow costs considers the problem of sending d units of flow from a source to a destination where arc capacity is purchased in batches of C units. The two facility problem (TFOC) is similar, but capacity can be purchased either in batches of C units or one unit. Flow costs are zero. These problems are known to be NP-hard. We describe an exact O(n(3)3(n)) algorithm for these problems based on the repeated use of a bipartite matching algorithm. We also present a better lower bound of Omega(n(2k*)) for an earlier Omega(n(2k)) algorithm described in the literature where k = left perpendicular [d/C] right perpendicular and k* = min {k, left perpendicular (n - 2)/2 right perpendicular}. The matching algorithm is faster than this one for k greater than or equal to left perpendicular (n-2)/2 right perpendicular. Finally, we provide another reformulation of the problem that is quasi integral. This property could be useful in designing a modified version of the simplex method to solve the problem using a sequence of pivots with integer extreme solutions, referred to as the integral simplex method in the literature.

关键词： network design exact algorithm integer solutions quasi-integral

来源：评论

学校读者我要写书评

暂无评论

On variable-weighted exact satisfiability problems

引用

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2007年第1期51卷 27-54页

作者： Porschen, Stefan Univ Cologne Inst Informat D-50969 Cologne Germany

We show that the NP-hard optimization problems minimum and maximum weight exact satisfiability (XSAT) for a CNF formula C over n propositional variables equipped with arbitrary real-valued weights can be solved in O(||C||2(0.2441n)) time. To the best of our knowledge, the algorithms presented here are the first handling weighted XSAT optimization versions in non-trivial worst case time. We also investigate the corresponding weighted counting problems, namely we show that the number of all minimum, resp. maximum, weight exact satisfiability solutions of an arbitrarily weighted formula can be determined in O(n(2)center dot||C|| + 2(0.40567n)) time. In recent years only the unweighted counterparts of these problems have been studied (Dahllof and Jonsson, An algorithm for counting maximum weighted independent sets and its applications. In: Proceedings of the 13th ACM-SIAM Symposium on Discrete algorithms, pp. 292-298, 2002;Dahllof et al., Theor Comp Sci 320: 373-394, 2004;Porschen, On some weighted satisfiability and graph problems. In: Proceedings of the 31st Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2005). Lecture Notes in Comp. Science, vol. 3381, pp. 278-287. Springer, 2005).

关键词： weighted exact satisfiability exact algorithm combinatorial optimization counting problem NP-completeness perfect matching maximum weight independent set set partition

来源：评论

学校读者我要写书评

暂无评论

b-colouring outerplanar graphs with large girth

引用

DISCRETE MATHEMATICS 2012年第10期312卷 1796-1803页

作者： Maffray, Frederic Silva, Ana Univ Fed Ceara Dept Matemat Fortaleza Ceara Brazil CNRS Lab G SCOP Grenoble France

A b-colouring of a graph is a colouring of its vertices such that every colour class contains a vertex that has a neighbour in all other classes. The b-chromatic number of a graph is the largest integer k such that the graph has a b-colouring with k colours. We show here how to compute in polynomial time the b-chromatic number of an outerplanar graph of girth at least 8. This generalizes the seminal result of Irving and Manlove on trees. (C) 2012 Elsevier B.V. All rights reserved.

关键词： b-chromatic number b-colouring Outerplanar graphs exact algorithm

来源：评论

学校读者我要写书评

暂无评论

A Branch-and-Bound Approach for Tautomer Enumeration

引用

MOLECULAR INFORMATICS 2015年第5期34卷 263-275页

作者： Thalheim, Torsten Wagner, Barbara Kuehne, Ralph Middendorf, Martin Schueuermann, Gerrit Fritz Lipmann Inst Leibniz Inst Age Res D-07745 Jena Germany Helmholtz Ctr Environm Res UFZ Dept Ecol Chem D-04318 Leipzig Germany Tech Univ Bergakad Freiberg Inst Organ Chem D-09596 Freiberg Germany Univ Leipzig Parallel Comp & Complex Syst Grp Dept Comp Sci D-04109 Leipzig Germany

Knowledge about tautomer forms of a structure is important since, e.g., a property prediction for a molecule can yield to different results which depend on the individual tautomer. Tautomers are isomers that can be transformed to each other through chemical equilibrium reactions. In this paper the first exact Branch-and-Bound (B&B) algorithm to calculate tautomer structures is proposed. The algorithm is complete in the sense of tautomerism and generates all possible tautomers of a structure according to the tautomer definition, it is initialized with. To be efficient, the algorithm takes advantage of symmetric and formation proper-ties. Some restrictions are used to enable an early pruning of some branches of the B&B tree. This is important, since a simple enumeration strategy would lead to number of candidate tautomers that is exponentially increasing with the number of hydrogen atoms and their attachment sites. The proposed implementation of the B&B algorithm covers the majority of the prototropic tautomer cases, but can be adapted to other kinds of tautomerism too. Furthermore, a computer processable definition of tautomerism is given in the form of the moving hydrogen atom problem.

关键词： Branch-and-Bound Combinatorial optimization Computational chemistry Combinatorial chemistry Chemoinformatics Double bond exact algorithm Hydrogen atom shift Moving hydrogen atom Proton-shift tautomerism Optimization problem Tautomerism

来源：评论

学校读者我要写书评

暂无评论

When polynomial approximation meets exact computation

引用

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 2015年第3期13卷 227-245页

作者： Paschos, Vangelis Th. Univ Paris 09 LAMSADE CNRS UMR 7243 PSL Res Univ Paris France

We outline a relatively new research agenda aiming at building a new approximation paradigm by matching two distinct domains, the polynomial approximation and the exact solution of NP -hard problems by algorithms with guaranteed and non-trivial upper complexity bounds. We show how one can design approximation algorithms achieving ratios that are "forbidden" in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower than that of an exact computation.

关键词： Complexity Polynomial approximation exact algorithm Moderately exponential approximation

来源：评论

学校读者我要写书评

暂无评论

Kaltofen's division-free determinant algorithm differentiated for matrix adjoint computation

引用

JOURNAL OF SYMBOLIC COMPUTATION 2011年第7期46卷 773-790页

作者： Villard, Gilles Univ Lyon CNRS ENS Lyon INRIAUCBLLab LIP F-69364 Lyon 07 France

Kaltofen has proposed a new approach in Kaltofen (1992) for computing matrix determinants without divisions. The algorithm is based on a baby steps/giant steps construction of Krylov subspaces, and computes the determinant as the constant term of the characteristic polynomial. For matrices over an abstract ring, by the results of Baur and Strassen (1983), the determinant algorithm, actually a straight-line program, leads to an algorithm with the same complexity for computing the adjoint of a matrix. However, the latter adjoint algorithm is obtained by the reverse mode of automatic differentiation, and hence is in some way not "explicit". We present an alternative (still closely related) algorithm for obtaining the adjoint that can be implemented directly, without resorting to an automatic transformation. The algorithm is deduced partly by applying program differentiation techniques "by hand" to Kaltofen's method, and is completely described. As a subproblem, we study the differentiation of the computation of minimum polynomials of linearly generated sequences, and we use a lazy polynomial evaluation mechanism for reducing the cost of Strassen's avoidance of divisions in our case. (C) 2010 Elsevier Ltd. All rights reserved.

关键词： Matrix determinant Matrix adjoint Matrix inverse Characteristic polynomial exact algorithm Division-free complexity Wiedemann algorithm Automatic differentiation

来源：评论

学校读者我要写书评

暂无评论

The Geodesic Diameter of Polygonal Domains

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2013年第2期50卷 306-329页

作者： Bae, Sang Won Korman, Matias Okamoto, Yoshio Kyonggi Univ Dept Comp Sci Suwon South Korea Univ Politecn Cataluna Dept Matemat Aplicada 2 Barcelona Spain Univ Electrocommun Dept Commun Engn & Informat Chofu Tokyo 182 Japan

This paper studies the geodesic diameter of polygonal domains having holes and corners. For simple polygons (i.e., ), the geodesic diameter is determined by a pair of corners of a given polygon and can be computed in linear time, as shown by Hershberger and Suri. For general polygonal domains with , however, no algorithm for computing the geodesic diameter was known prior to this paper. In this paper, we present the first algorithms that compute the geodesic diameter of a given polygonal domain in worst-case time or . The main difficulty unlike the simple polygon case relies on the following observation revealed in this paper: two interior points can determine the geodesic diameter and in that case there exist at least five distinct shortest paths between the two.

关键词： Polygonal domain Shortest path Geodesic diameter exact algorithm Convex function Lower envelope

来源：评论

学校读者我要写书评

暂无评论

A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 2009年第4期58卷 619-631页

作者： Lazarev, Alexander A. Werner, Frank Russian Acad Sci Inst Control Sci Moscow 117997 Russia Otto VonGuericke Univ Magdegurg Fak Math D-39016 Magdeburg Germany

In this paper, we consider a graphical realization of dynamic programming. The concept is discussed on the partition and knapsack problems. In contrast to dynamic programming, the new algorithm can also treat problems with non-integer data without necessary transformations of the corresponding problem. We compare the proposed method with existing algorithms for these problems on small-size instances of the partition problem with n <= 10 numbers. For almost all instances, the new algorithm considers on average substantially less "stages" than the dynamic programming algorithm. Crown Copyright (C) 2009 Published by Elsevier Ltd. All rights reserved.

关键词： Dynamic programming exact algorithm Graphical algorithm Partition problem Knapsack problem

来源：评论

学校读者我要写书评

暂无评论

AN IMPROVED DYNAMIC-PROGRAMMING algorithm FOR THE SINGLE-MACHINE MEAN ABSOLUTE DEVIATION PROBLEM WITH A RESTRICTIVE COMMON DUE-DATE

引用

OPERATIONS RESEARCH LETTERS 1995年第3期17卷 149-152页

作者： VENTURA, JA WENG, MX Department of Industrial and Management Systems Engineering 207 Hammond Building The Pennsylvania State University University Park PA 16802 USA

In 1991, Hall et al. showed that the problem of minimizing the mean earliness and tardiness of n jobs scheduled on a single machine around a restrictive common due date is NP-complete. They proposed a pseudo-polynomial dynamic programming algorithm, called Optcet, for identifying an optimal schedule. This paper points out that two of the three subroutines in Optcet can be eliminated and, consequently, the total computational effort can be reduced significantly.

关键词： SCHEDULING MEAN ABSOLUTE DEVIATION DYNAMIC PROGRAMMING exact algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：