Modern exact algorithms for structure learning in Bayesian networks first compute an exact local score of every candidate parent set, and then find a network structure by combinatorial optimization so as to maximize t...
详细信息
Modern exact algorithms for structure learning in Bayesian networks first compute an exact local score of every candidate parent set, and then find a network structure by combinatorial optimization so as to maximize the global score. This approach assumes that each local score can be computed fast, which can be problematic when the scarcity of the data calls for structured local models or when there are both continuous and discrete variables, for these cases have lacked efficient-to-compute local scores. To address this challenge, we introduce a local score that is based on a class of classification and regression trees. We show that under modest restrictions on the possible branchings in the tree structure, it is feasible to find a structure that maximizes a Bayes score in a range of moderate-size problem instances. In particular, this enables global optimization of the Bayesian network structure, including the local structure. In addition, we introduce a related model class that extends ordinary conditional probability tables to continuous variables by employing an adaptive discretization approach. The two model classes are compared empirically by learning Bayesian networks from benchmark real-world and synthetic data sets. We discuss the relative strengths of the model classes in terms of their structure learning capability, predictive performance, and running time. (C) 2019 The Authors. Published by Elsevier Inc.
In this paper, we present improved exact and parameterized algorithms for the maximum satisfiability problem. In particular, we give an algorithm that computes a truth assignment for a boolean formula F satisfying the...
详细信息
In this paper, we present improved exact and parameterized algorithms for the maximum satisfiability problem. In particular, we give an algorithm that computes a truth assignment for a boolean formula F satisfying the maximum number of clauses in time O(1.3247(m)\F\), where m is the number of clauses in F, and \F\ is the sum of the number of literals appearing in each clause in F. Moreover, given a parameter k, we give an O(1.3695(k) + \F\) parameterized algorithm that decides whether a truth assignment for F satisfying at least k clauses exists. Both algorithms improve the previous best algorithms by Bansal and Raman for the problem. (C) 2004 Elsevier B.V. All rights reserved.
This article describes a heuristic and two exact algorithms for several classes of vehicle routing problems defined on tree networks. These include capacitated and time-constrained vehicle routing problems. One of the...
详细信息
This article describes a heuristic and two exact algorithms for several classes of vehicle routing problems defined on tree networks. These include capacitated and time-constrained vehicle routing problems. One of the exact algorithms is based on the computation of bin packing lower bounds. The other uses column generation. The first algorithm performs better on problems containing small customer demands and in which all vehicles are identical. Otherwise, the second algorithm is more powerful and more versatile. (C) 1999 John Wiley & Sons, Inc.
We study three new techniques that will speed up the branch-and-bound algorithm for the MAX-2-SAT problem: The first technique is a group of new lower bound functions for the algorithm and we show that these functions...
详细信息
We study three new techniques that will speed up the branch-and-bound algorithm for the MAX-2-SAT problem: The first technique is a group of new lower bound functions for the algorithm and we show that these functions are admissible and consistently better than other known lower bound functions. The other two techniques are based on the strongly connected components of the implication graph of a 2CNF formula: One uses the graph to simplify the formula and the other uses the graph to design a new variable ordering. The experiments show that the simplification can reduce the size of the input substantially no matter what is the clause-to-variable ratio and that the new variable ordering performs much better when the clause-to-variable ratio is less than 2. A direct outcome of this research is a high-performance implementation of an exact algorithm for MAX-2-SAT which outperforms any implementation we know about in the same category. We also show that our implementation is a feasible and effective tool to solve large instances of the Max-Cut problem in graph theory.
In 1994, Telle introduced the following notion of domination, which generalizes many domination-type graph invariants. Let sigma and rho be two sets of non-negative integers. A vertex subset S subset of V of an undire...
详细信息
In 1994, Telle introduced the following notion of domination, which generalizes many domination-type graph invariants. Let sigma and rho be two sets of non-negative integers. A vertex subset S subset of V of an undirected graph G = (V, E) is called a (sigma, rho)-dominating set of G if |N(v) boolean AND S| is an element of sigma for all v is an element of S and |N(v) boolean AND S| is an element of rho for all v is an element of V \ S. In this paper, we prove that decision, optimization, and counting variants of ({p}, {q})-domination are solvable in time 2(|V|/2), |V|(0(1)). We also show how to extend these results for infinite sigma = {p + M . l: l is an element of N-0} and rho = {q + m . l: l is an element of N-0}. For the case |sigma| + |rho| = 3, these problems can be solved in time 3(|V|/2). |V|(0(1)), and similarly to the case |sigma| = |rho| = 1 it is possible to extend the algorithm for some infinite sets. (C) 2009 Elsevier B.V. All rights reserved.
We show that the 3-colorability problem can be solved in O(1.296(n)) time on any n-vertex graph with minimum degree at least 15. This algorithm is obtained by constructing a dominating set of the graph greedily, enume...
详细信息
We show that the 3-colorability problem can be solved in O(1.296(n)) time on any n-vertex graph with minimum degree at least 15. This algorithm is obtained by constructing a dominating set of the graph greedily, enumerating all possible 3-colorings of the dominating set, and then solving the resulting 2-list coloring instances in polynomial time. We also show that a 3-coloring can be obtained in 2(o(n)) time for graphs having minimum degree at least w(n) where w(n) is any function which goes to infinity. We also show that if the lower bound on minimum degree is replaced by a constant (however large it may be), then neither a 2(o(n)) time nor a 2(o(m)) time algorithm is possible (m denotes the number of edges) for 3-colorability unless Exponential Time Hypothesis (ETH) fails. We also describe an algorithm which obtains a 4-coloring of a 3-colorable graph in O(1.2535(n)) time. (C) 2010 Elsevier B.V. All rights reserved.
In this note, we give a proof that several vertex ordering problems can be solved in O (au)(2 (n) ) time and O (au)(2 (n) ) space, or in O (au)(4 (n) ) time and polynomial space. The algorithms generalize algorithms f...
详细信息
In this note, we give a proof that several vertex ordering problems can be solved in O (au)(2 (n) ) time and O (au)(2 (n) ) space, or in O (au)(4 (n) ) time and polynomial space. The algorithms generalize algorithms for the Travelling Salesman Problem by Held and Karp (J. Soc. Ind. Appl. Math. 10:196-210, 1962) and Gurevich and Shelah (SIAM J. Comput. 16:486-502, 1987). We survey a number of vertex ordering problems to which the results apply.
Planar Maximum Covering Location by Ellipses is an optimization problem where one wants to choose the location of ellipses given their major and minor axes to cover demand points, maximizing a function depending on th...
详细信息
Planar Maximum Covering Location by Ellipses is an optimization problem where one wants to choose the location of ellipses given their major and minor axes to cover demand points, maximizing a function depending on the value of covered points. We propose new exact algorithms for two versions of this problem, one where the ellipses have to be parallel to the coordinate axes, and another where they can be freely rotated. Besides finding optimal solutions for previously published instances, including the ones where no optimal solution was known, both algorithms proposed by us were able to obtain optimal solutions for some new larger instances with up to seven hundred demand points and five ellipses. (C) 2020 Elsevier B.V. All rights reserved.
The aim of this paper is to point out that all mathematical programming models proposed by Ying et al. (2016) are incorrect. We present four revised mathematical programming models and four improved mathematical progr...
详细信息
The aim of this paper is to point out that all mathematical programming models proposed by Ying et al. (2016) are incorrect. We present four revised mathematical programming models and four improved mathematical programming models by adding and revising some constraints and decision variables. Moreover, we show that the first three scheduling problems considered in their paper are equivalent to the problems with the objective of minimizing the sum of completion times or minimizing the maximum lateness, which can be solved by algorithms proposed by Luo et al. (2015) in O(n(2)) time. (C) 2017 Elsevier Ltd. All rights reserved.
Given an edge-weighted bipartite digraph G = (A, B;E), the Bipartite Traveling Salesman Problem (BTSP) asks to find the minimum cost of a Hamiltonian cycle of G, or determine that none exists. When vertical bar A vert...
详细信息
Given an edge-weighted bipartite digraph G = (A, B;E), the Bipartite Traveling Salesman Problem (BTSP) asks to find the minimum cost of a Hamiltonian cycle of G, or determine that none exists. When vertical bar A vertical bar = vertical bar B vertical bar = n, the BTSP can be solved using polynomial space in O*(4(2n)n(log n)) time by using the divide-and-conquer algorithm of Gurevich and Shelah (SIAM Journal of Computation, 16(3), pp. 486-502, 1987). We adapt their algorithm for the bipartite case, and show an improved time bound of O*(4(2n)), saving the n(log n) factor.
暂无评论