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

Simultaneous Solution of Lagrangean Dual Problems Interleaved with Preprocessing for the Weight Constrained Shortest Path Problem

引用

NETWORKS 2009年第4期53卷 358-381页

作者： Muhandiramge, Ranga Boland, Natashia Univ Newcastle Sch Math & Phys Sci Callaghan NSW 2308 Australia Univ Western Australia Sch Math & Stat Crawley WA 6009 Australia

Conventional Lagrangean preprocessing for the network Weight Constrained Shortest Path Problem (WCSPP), for example Beasley and Christofides (Beasley and Christofides, Networks 19 (1989)9 379-394), calculates lower bounds on the cost of using each node and edge in a feasible path using a single optimal Lagrange multiplier for the relaxation of the WCSPP. These lower bounds are used in conjunction with an upper bound to eliminate nodes and edges. However, for each node and edge, a Lagrangean dual problem exists whose solution may differ from the relaxation of the full problem. Thus, using one Lagrange multiplier does not offer the best possible network reduction. Furthermore, eliminating nodes and edges from the network may change the Lagrangean dual solutions in the remaining reduced network, warranting an iterative solution and reduction procedure. We develop a method for solving the related Lagrangean dual problems for each edge simultaneously which is iterated with eliminating nodes and edges. We demonstrate the effectiveness of our method computationally: we test it against several others and show that it both reduces solve time and the number of intractable problems encountered. We use a modified version of Carlyle and Wood's (38th Annual ORSNZ Conference, Hamilton, New Zealand, November, 2003) enumeration algorithm in the gap closing stage. We also make improvements to this algorithm and test them computationally. (C) 2009 Wiley Periodicals, Inc. NETWORKS, Vol. 53(4), 358-381 2009

关键词： shortest paths constrained shortest paths enumeration algorithms Lagrangean relaxation preprocessing

来源：评论

学校读者我要写书评

暂无评论

Efficiently enumerating results of keyword search over data graphs

引用

INFORMATION SYSTEMS 2008年第4-5期33卷 335-359页

作者： Kimelfeld, Benny Sagiv, Yehoshua Hebrew Univ Jerusalem Selim & Rachel Benin Sch Engn & Comp Sci IL-91904 Jerusalem Israel

Various approaches for keyword search in different settings (e.g., relational databases and XML) actually deal with the problem of enumerating K-fragments. For a given set of keywords K, a K-fragment is a subtree T of the given data graph, such that T contains all the keywords of K and no proper subtree of T has this property. There are three types of K-fragments: directed, undirected and strong. This paper describes efficient algorithms for enumerating K-fragments. Specifically, for all three types of K-fragments, algorithms are given for enumerating all K-fragments with polynomial delay and polynomial space. It is shown how these algorithms can be enhanced to enumerate K-fragments in a heuristic order. For directed K-fragments and acyclic data graphs, an algorithm is given for enumerating with polynomial delay in the order of increasing weight (i.e., the ranked order), assuming that K is of a fixed size. (C) 2008 Elsevier B.V. All rights reserved.

关键词： databases data graphs enumeration algorithms keyword search reduced subtrees

来源：评论

学校读者我要写书评

暂无评论

Verifying and enumerating parameterized border arrays

引用

THEORETICAL COMPUTER SCIENCE 2011年第50期412卷 6959-6981页

作者： Tomohiro, I Inenaga, Shunsuke Bannai, Hideo Takeda, Masayuki Kyushu Univ Dept Informat Fukuoka 812 Japan

The parameterized pattern matching problem is to check if there exists a renaming bijection on the alphabet with which a given pattern can be transformed into a substring of a given text. A parameterized border array (p-border array) is a parameterized version of a standard border array, and we can efficiently solve the parameterized pattern matching problem using p-border arrays. In this paper, we present a linear time algorithm to verify if a given integer array is a valid p-border array for a binary alphabet. We also show a linear time algorithm to compute all binary parameterized strings sharing a given p-border array. In addition, we give an algorithm which computes all p-border arrays of length at most n, where n is a given threshold. This algorithm runs in O(B-2(n)) time, where B-2(n) is the number of all p-border arrays of length n for a binary parameter alphabet. The problems with a larger alphabet are much more difficult. Still, we present an O(n(1.5)) - time O(n) - space algorithm to verify if a given integer array of length n is a valid p-border array for an unbounded alphabet. The best previously known solution to this task takes time proportional to the n-th Bell number 1/e Sigma(infinity)(k=0) k(n)/k(l), and hence our algorithm is much more efficient. Also, we show that it is possible to enumerate all p-border arrays of length at most n for an unbounded alphabet in O(B(n)n(2.5)) time, where B-n denotes the number of p-border arrays of length n. (C) 2011 Elsevier B.V. All rights reserved.

关键词： String matching Parameterized pattern matching Reverse engineering enumeration algorithms

来源：评论

学校读者我要写书评

暂无评论

On computing all abductive explanations from a propositional horn theory

引用

JOURNAL OF THE ACM 2007年第5期54卷 24-1-24-54页

作者： Eiter, Thomas Making, Kazuhisa Vienna Univ Technol Inst Informat Syst A-1040 Vienna Austria Univ Tokyo Grad Sch Informat & Technol Dept Math Informat Tokyo 1138656 Japan

Abduction is a fundamental mode of reasoning with applications in many areas of AI and Computer Science. The computation of abductive explanations is an important computational problem, which is at the core of early systems such as the ATMS and Clause Management Systems and is intimately related to prime implicate generation in propositional logic. Many algorithms have been devised for computing some abductive explanation, and the complexity of the problem has been well studied. However, little attention has been paid to the problem of computing multiple explanations, and in particular all explanations for an abductive query. We fill this gap and consider the computation of all explanations of an abductive query from a propositional Horn theory, or of a polynomial subset of them. Our study pays particular attention to the form of the query, ranging from a literal to a compound formula, to whether explanations are based on a set of abducible literals and to the representation of the Horn theory, either by a Horn conjunctive normal form (CNF) or model-based in terms of its characteristic models. For these combinations, we present either tractability results in terms of polynomial total-time algorithms, intractability results in terms of nonexistence of such algorithms (unless P = NP), or semi-tractability results in terms of solvability in quasi-polynomial time, established by polynomial-time equivalence to the problem of dualizing a monotone CNF expression. Our results complement previous results in the literature, and refute a longstanding conjecture by Selman and Levesque. They elucidate the complexity of generating all abductive explanations and shed light on related problems such as generating sets of restricted prime implicates of a Horn theory. The algorithms for tractable cases can be readily applied for generating a polynomial subset of explanations in polynomial time.

关键词： algorithms theory abduction propositional logic Horn theories polynomial totaltime computation enumeration algorithms dualization problem model-based reasoning characteristic set prime implicates tractability NP-hardness

来源：评论

学校读者我要写书评

暂无评论

Polynomial-time dualization of r-exact hypergraphs with applications in geometry

引用

DISCRETE MATHEMATICS 2010年第17-18期310卷 2356-2363页

作者： Elbassioni, Khaled Rauf, Imran Max Planck Inst Informat Saarbrucken Germany Univ Jena Lehrstuhl Bioinformat Jena Germany

Let H subset of 2(V) be a hypergraph on vertex set V. For a positive integer r, we call H r-exact if any minimal transversal of H intersects any hyperedge of H in at most r vertices. This class includes several interesting examples from geometry, e.g., circular-arc hypergraphs (r = 2), hypergraphs defined by sets of axis parallel lines stabbing a given set of a-fat objects (r = 4 alpha), and hypergraphs defined by sets of points contained in translates of a given cone in the plane (r = 2). For constant r, we give a polynomial-time algorithm for the duality testing problem of a pair of r-exact hypergraphs. This result implies that minimal hitting sets for the above geometric hypergraphs can be generated in output polynomial time. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Hypergraphs Transversals Geometric hitting sets enumeration algorithms

来源：评论

学校读者我要写书评

暂无评论

Extended dualization: Application to maximal pattern mining

引用

THEORETICAL COMPUTER SCIENCE 2016年 618卷 107-121页

作者： Nourine, Lhouari Petit, Jean-Marc Univ Blaise Pascal CNRS LIMOS Clermont Ferrand France Univ Lyon CNRS INSA Lyon LIRIS Lyon France

The dualization in arbitrary posets is a well-studied problem in combinatorial enumeration and is a crucial step in many applications in logics, databases, artificial intelligence and pattern mining. The objective of this paper is to study reductions of the dualization problem on arbitrary posets to the dualization problem on boolean lattices, for which output quasi-polynomial time algorithms exist, Quasi-polynomial time algorithms are algorithms which run in no(logn) where n is the size of the input and output. We introduce convex embedding and poset reflection as key notions to characterize such reductions. As a consequence, we identify posets, which are not boolean lattices, for which the dualization problem remains in quasi-polynomial time and propose a classification of posets with respect to dualization. From these results, we study how they can be applied to maximal pattern mining problems. We deduce a new classification of pattern mining problems and we point out how known problems involving sequences and conjunctive queries patterns, fit into this classification. Finally, we explain how to adapt the seminal DUALIZE & ADVANCE algorithm to deal with such patterns. As far as we know, this is the first contribution to explicit non-trivial reductions for studying the hardness of maximal pattern mining problems and to extend the DUALIZE & ADVANCE algorithm for complex patterns. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Hypergraph dualization enumeration algorithms Patterns mining

来源：评论

学校读者我要写书评

暂无评论

A General Framework for Enumerating Equivalence Classes of Solutions

引用

ALGORITHMICA 2023年第10期85卷 3003-3023页

作者： Wang, Yishu Mary, Arnaud Sagot, Marie-France Sinaimeri, Blerina Univ Lyon Univ Lyon 1 CNRS Lab Biometrie & Biol Evolut UMR 5558 F-69622 Villeurbanne France Inria Lyon Villeurbanne France Luiss Univ Rome Italy

When a problem has more than one solution, it is often important, depending on the underlying context, to enumerate (i.e., to list) them all. Even when the enumeration can be done in polynomial delay, that is, spending no more than polynomial time to go from one solution to the next, this can be costly as the number of solutions themselves may be huge, including sometimes exponential. Furthermore, depending on the application, many of these solutions can be considered equivalent. The problem of an efficient enumeration of the equivalence classes or of one representative per class (without generating all the solutions), although identified as a need in many areas, has been addressed only for very few specific cases. In this paper, we provide a general framework that solves this problem in polynomial delay for a wide variety of optimization problems solvable by dynamic programming algorithms, and for certain types of equivalence relations between solutions.

关键词： enumeration algorithms Equivalence relation Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

An enumerative algorithm for solving nonconvex dynamic DEA models

引用

OPTIMIZATION LETTERS 2013年第1期7卷 101-115页

作者： Soleimani-damaneh, M. Univ Tehran Coll Sci Sch Math Stat & Comp Sci Tehran Iran

This paper provides a recursive enumeration algorithm for solving the nonconvex dynamic DEA models, to obtain cost minimum under nonconvex technologies. The validity of the algorithm is proved through some theorems. An illustrative example as well as a computational discussion are given to demonstrate the advantages of the proposed algorithm.

关键词： Dynamic DEA FDH Nonconvex models enumeration algorithms Recursive algorithms

来源：评论

学校读者我要写书评

暂无评论

algorithms FOR DUALIZATION OVER PRODUCTS OF PARTIALLY ORDERED SETS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2009年第1期23卷 487-510页

作者： Elbassioni, Khaled M. Max Planck Inst Informat D-66123 Saarbrucken Germany

Let P = P(1) x ... x P(n) be the product of n partially ordered sets (posets). Given a subset A. P, we consider problem DUAL(P, A, B) of extending a given partial list B of maximal independent elements of A in P. We give quasi-polynomial time algorithms for solving problem DUAL(P, A, B) when each poset P(i) belongs to one of the following classes: (i) semilattices of bounded width, (ii) forests, that is, posets with acyclic underlying graphs, with either bounded in-degrees or out-degrees, or (iii) lattices defined by a set of real closed intervals.

关键词： enumeration algorithms forests hypergraph transversals infrequent elements lattices monotone properties monotone generation ordered sets duality testing

来源：评论

学校读者我要写书评

暂无评论

Ranking and unranking of non-regular trees with a prescribed branching sequence

引用

MATHEMATICAL AND COMPUTER MODELLING 2011年第5-6期53卷 1331-1335页

作者： Wu, Ro-Yu Chang, Jou-Ming Chang, Chir-Ho Natl Taipei Coll Business Inst Informat & Decis Sci Taipei Taiwan Lunghwa Univ Sci & Technol Dept Ind Management Tao Yuan Taiwan

Ordered trees are called non-regular trees with a prescribed branching sequence (or non-regular trees for short) if their internal nodes have a pre-specified degree sequence in preorder list. This article presents two main results. First, we develop a simple algorithm to generate all non-regular trees in lexicographic order using RD-sequences defined by [R.-Y. Wu, J.-M. Chang, Y.-L. Wang, Loopless generation of non-regular trees with a prescribed branching sequence, The Computer Journal 53 (2010) 661-666]. Then, by analyzing the structure of a coding tree, this algorithm is proved to run in constant amortized time. Next, we propose efficient ranking algorithm (i.e., determining the rank of a given non-regular tree in such an order) and unranking algorithm (i.e., converting a positive integer to its corresponding RD-sequence). (C) 2010 Elsevier Ltd. All rights reserved.

关键词： Non-regular trees enumeration algorithms Ranking/unranking algorithms Constant amortized time

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：