A machine learning approach to algorithm selection for $\mathcal{NP}$ -hard optimization problems: a case study on the MPE problem

Given one instance of an \(\mathcal{NP}\)-hard optimization problem, can we tell in advance whether it is exactly solvable or not? If it is not, can we predict which approximate algorithm is the best to solve it? Since the behavior of most approximate, randomized, and heuristic search algorithms for \(\mathcal{NP}\)-hard problems is usually very difficult to characterize analytically, researchers have turned to experimental methods in order to answer these questions. In this paper we present a machine learning-based approach to address the above questions. Models induced from algorithmic performance data can represent the knowledge of how algorithmic performance depends on some easy-to-compute problem instance characteristics. Using these models, we can estimate approximately whether an input instance is exactly solvable or not. Furthermore, when it is classified as exactly unsolvable, we can select the best approximate algorithm for it among a list of candidates. In this paper we use the MPE (most probable explanation) problem in probabilistic inference as a case study to validate the proposed methodology. Our experimental results show that the machine learning-based algorithm selection system can integrate both exact and inexact algorithms and provide the best overall performance comparing to any single candidate algorithm.     

The inertia of unicyclic graphs and the implications for closed-shells

The inertia of a graph is an integer triple specifying the number of negative, zero, and positive eigenvalues of the adjacency matrix of the graph. A unicyclic graph is a simple connected graph with an equal number of vertices and edges. This paper characterizes the inertia of a unicyclic graph in terms of maximum matchings and gives a linear-time algorithm for computing it. Chemists are interested in whether the molecular graph of an unsaturated hydrocarbon is (properly) closed-shell, having exactly half of its eigenvalues greater than zero, because this designates a stable electron configuration. The inertia determines whether a graph is closed-shell, and hence the reported result gives a linear-time algorithm for determining this for unicyclic graphs.     

Partial Colorings of Unimodular Hypergraphs

Combinatorial discrepancy theory asks for vertex-colorings of hypergraphs such that all hyperedges contain all colors in (as good as possible) equal quantity. Unimodular hypergraphs are good in this sense: They (and all their induced subhypergraphs as well) can be two-colored in a way that in each hyperedge the number of vertices in one color deviates from that in the other color by at most one. Note that this means that even cardinality hyperedges are perfectly balanced, whereas odd ones have a deviation of exactly one. This observation raises the question whether one can spare these deviations of one by leaving some vertices uncolored. In this work, we give a complete characterization of when this is possible.     

具有四个不同特征值的竞赛矩阵

设A是n阶竞赛矩阵，k是非负整数。文[3]刻划了恰好有三个不同特征值的n阶竞赛矩阵，文[4]刻划了恰好有四个不同特征值并且0作为一个一重特征值的n阶竞赛矩阵。在这篇文章中我们主要研究了两个问题：（1）讨论当k是A的特征值时A的性质。（2）刻划恰好有四个不同特征值并且k作为一个一重特征值的全部n阶竞赛矩阵。     

The Kardar-Parisi-Zhang equation and its matrix generalization

We study the problem of the condensate (stochastic average) origination for an auxiliary field in the Kardar-Parisi-Zhang equation and its matrix generalization. We cannot reliably conclude that there is a condensate for the Kardar-Parisi-Zhang equation in the framework of the one-loop approximation improved by the renormalization group method. The matrix generalization of the Kardar-Parisi-Zhang equation permits a positive answer to the question of whether there is a nonzero condensate, and the problem can be solved exactly in the large-N limit.     

On primitively universal quadratic forms

In 1999, Manjul Bhargava proved the Fifteen Theorem and showed that there are exactly 204 universal positive definite integral quaternary quadratic forms. We consider primitive representations of quadratic forms and investigate a primitive counterpart to the Fifteen Theorem. In particular, we give an efficient method for deciding whether a positive definite integral quadratic form in four or more variables with odd square-free determinant is almost primitively universal.     

Gauging and comparing the performances of dissimilar entities

The problem of comparing the performances of a set of entities that are not entirely similar in their operating characteristics challenges most of the existing performance measurement methods. A performance measurement method called operational competitiveness rating analysis (OCRA) is introduced, which is suitable for gauging and comparing the performances of entities that consume inputs of resources to produce outputs of goods and services that are not exactly the same. Additionally, the entities may assign different degrees of relative importance to the inputs and outputs reflecting different managerial priorities. OCRA's development is summarized and an example is presented to illustrate its application for comparing the performances of faculty members in two academic departments with dissimilar research orientations and investigating whether or not their salaries are consistent with their performances.     

Characterizations of intervals via continuous selections

We prove that: (i) a pathwise connected, Hausdorff space which has a continuous selection is homeomorphic to one of the following four spaces: singleton, [0,1), [0,1] or the long lineL, (ii) a locally connected (Hausdorff) space which has a continuous selection must be orderable, and (iii) an infinite connected, Hausdorff space has exactly two continuous selections if and only if it is compact and orderable. We use these results to give various characterizations of intervals via continuous selections. For instance, (iv) a topological spaceX is homeomorphic to [0,1] if (and only if)X is infinite, separable, connected, Hausdorff space and has exactly two continuous selections, and (v) a topological spaceX is homeomorphic to [0,1) if (and only if) one of the following equivalent conditions holds: (a)X is infinite, Hausdorff, separable, pathwise connected and has exactly one continuous selection; (b)X is infinite, separable, locally connected and has exactly one continuous selection; (c)X is infinite, metric, locally connected and has exactly one continuous selection. Three examples are exhibited which demonstrate the necessity of various assumptions in our results.     

On nice equivalence relations on <Superscript>λ</Superscript>2

Let E be an equivalence relation on the powerset of an uncountable set, which is reasonably definable. We assume that any two subsets with symmetric difference of size exactly 1 are not equivalent. We investigate whether for E there are many pairwise non equivalent sets. I would like to thank Alice Leonhardt for the beautiful typing.This research was supported by The Israel Science Foundation. Publication 724. Mathematics Subject Classification (2000): 03E47, 03E35; 20K20, 20K35     

Given a one-step numerical scheme,on which ordinary differential equations is it exact?

A necessary condition for a (non-autonomous) ordinary differential equation to be exactly solved by a one-step, finite difference method is that the principal term of its local truncation error be null. A procedure to determine some ordinary differential equations exactly solved by a given numerical scheme is developed. Examples of differential equations exactly solved by the explicit Euler, implicit Euler, trapezoidal rule, second-order Taylor, third-order Taylor, van Niekerk’s second-order rational, and van Niekerk’s third-order rational methods are presented.