This paper describes BBMCW, a new efficient exact maximum clique algorithm tailored for large sparse graphs which can be bit-encoded directly into memory without a heavy performance penalty. These graphs occur in real-life problems when some form of locality may be exploited to reduce their scale. One such example is correspondence graphs derived from data association problems. The new algorithm is based on the bit-parallel kernel used by the BBMC family of published exact algorithms. BBMCW employs a new bitstring encoding that we denote ‘watched’, because it is reminiscent of the ‘watched literal’ technique used in satisfiability and other constraint problems. The new encoding reduces the number of spurious operations computed by the BBMC bit-parallel kernel in large sparse graphs. Moreover, BBMCW also improves on bound computation proposed in the literature for bit-parallel solvers. Experimental results show that the new algorithm performs better than prior algorithms over data sets of both real and synthetic sparse graphs. In the real data sets, the improvement in performance averages more than two orders of magnitude with respect to the state-of-the-art exact solver IncMaxCLQ.
Flow variations over time generalize standard network flows by introducing an element of time. In contrast to the classical case of static flows, a flow over time in such a network specifies a flow rate entering an arc for each point in time. In this setting, the capacity of an arc limits the rate of flow into the arc at each point in time. Traditionally, flows over time are computed in time-expanded networks that contain one copy of the original network for each discrete time step. While this method makes available the whole algorithmic toolbox developed for static network flows, its drawback is the enormous size of the time-expanded network. In this paper, we extend the results about the minimum flow problem to network flows (with n nodes and m arcs) in which the time-varying lower bounds can involve both the source and the sink nodes (as in Fathabadi et al.) and also one additional node other than the source and the sink nodes. It is shown that this problem for the set (Formula presented.) of time points can be solved by at most n minimum flow computations, by suitably extending the dynamic minimum flow algorithm and reoptimization techniques. The running time of the presented algorithm is (Formula presented.).
In this paper we examine the maintenance decision support in classification of the dangerous situations discovered by the monitoring system. This task is reduced to the contextual multi-armed bandit problem. We highlight small sample size problem appeared in this task due to the rather rare failures. The novel algorithm based on the nearest neighbor search is proposed. An experimental study is provided for several synthetic datasets with the situations described by either simple features or grayscale images. It is shown, that our algorithm outperforms the well-known contextual multi-armed methods with the Upper Confidence Bound and softmax random search strategies.
This paper addresses the problem of insufficient performance of statistical classification with the medium-sized database (thousands of classes). Each object is represented as a sequence of independent segments. Each segment is defined as a random sample of independent features with the distribution of multivariate exponential type. To increase the speed of the optimal Kullback-Leibler minimum information discrimination principle, we apply the clustering of the training set and an approximate nearest neighbor search of the input object in a set of cluster medoids. By using the asymptotic properties of the Kullback-Leibler divergence, we propose the maximal likelihood search procedure. In this method the medoid to check is selected from the cluster with the maximal joint density (likelihood) of the distances to the previously checked medoids. Experimental results in image recognition with artificially generated dataset and Essex facial database prove that the proposed approach is much more effective, than an exhaustive search and the known approximate nearest neighbor methods from FLANN and NonMetricSpace libraries.
A class of graphs is called monotone if it is closed under deletion of vertices and edges. Any such class may be defined in terms of forbidden subgraphs. The chromatic index of a graph is the smallest number of colors required for its edge-coloring such that any two adjacent edges have different colors. We obtain a complete classification of the complexity of the chromatic index problem for all monotone classes defined in terms of forbidden subgraphs having at most 6 edges or at most 7 vertices.
The notions of boundary and minimal hard classes of graphs, united by the term “critical classes”, are useful tools for analysis of computational complexity of graph problems in the family of hereditary graph classes. In this family, boundary classes are known for several graph problems. In the paper, we consider critical graph classes in the families of strongly hereditary and minor closed graph classes. Prior to our study, there was the only one example of a graph problem for which boundary classes were completely described in the family of strongly hereditary classes. Moreover, no boundary classes were known for any graph problem in the family of minor closed classes. In this article, we present several complete descriptions of boundary classes for these two families and some classical graph problems. For the problem of 2-additive approximation of graph bandwidth, we find a boundary class in the family of minor closed classes. Critical classes are not known for this problem in the other two families of graph classes.
In this paper we focus on two essential problems of maintenance decision support systems, namely, 1) detection of potential dangerous situation, and 2) classification of this situation in order to recommend an appropriate repair action. The former task is usually solved with the known statistical process control techniques. The latter problem can be reduced to the contextual multi-armed bandit problem. We propose a novel algorithm with Bayesian classification of abnormal situation and the softmax rule to explore the decision space. The dangerous situations are detected with the Shewhart control charts for the distances between the current and the normal situations. It is experimentally shown, that our algorithm is more accurate than the known contextual multi-armed methods with stochastic search strategies.
Deep convolutional neural networks are widely used to extract high-dimensional features in various image recognition tasks. If the count of classes is relatively large, performance of the classifier for such features can be insufficient to be implemented in real-time applications, e.g., in video-based recognition. In this paper we propose the novel approximate nearest neighbor algorithm, which sequentially chooses the next instance from the database, which corresponds to the maximal likelihood (joint density) of distances to previously checked instances. The Gaussian approximation of the distribution of dissimilarity measure is used to estimate this likelihood. Experimental study results in face identification with LFW and YTF datasets are presented. It is shown that the proposed algorithm is much faster than an exhaustive search and several known approximate nearest neighbor methods.
We analyzed the way to increase computational efficiency of video-based image recognition methods with matching of high dimensional feature vectors extracted by deep convolutional neural networks. We proposed an algorithm for approximate nearest neighbor search. At the first step, for a given video frame the algorithm verifies a reference image obtained when recognizing the previous frame. After that the frame is compared with a few number of reference images. Each next examined reference image is chosen so that to maximize conditional probability density of distances to the reference instances tested at previous steps. To decrease the required memory space we beforehand calculate only distances from all the images to small number of instances (pivots). When experimenting with either face photos from Labeled Faces in the Wild and PubFig83 datasets or with video data from YouTube Faces we showed that our algorithm allows accelerating the recognition procedure by 1.4–4 times comparing with known approximate nearest neighbor methods.
We consider a class of nonlinear integer optimization problems commonly known as fractional 0–1 programming problems (also, often referred to as hyperbolic 0–1 programming problems), where the objective is to optimize the sum of ratios of affine functions subject to a set of linear constraints. Such problems arise in diverse applications across different fields, and have been the subject of study in a number of papers during the past few decades. In this survey we overview the literature on fractional 0–1 programs including their applications, related computational complexity issues and solution methods including exact, approximation and heuristic algorithms.
In this paper we describe our algorithmic approach, which was used for submissions in the fifth Emotion Recognition in the Wild (EmotiW 2017) group-level emotion recognition sub-challenge. We extracted feature vectors of detected faces using the Convolutional Neural Network trained for face identification task, rather than traditional pre-training on emotion recognition problems. In the final pipeline an ensemble of Random Forest classifiers was learned to predict emotion score using available training set. In case when the faces have not been detected, one member of our ensemble extracts features from the whole image. During our experimental study, the proposed approach showed the lowest error rate when compared to other explored techniques. In particular, we achieved 75.4% accuracy on the validation data, which is 20% higher than the handcrafted feature-based baseline. The source code using Keras framework is to be made publicly available.Image already added
The problem of homogenity hypothesis testing for degree distribution of the market graph is studied. Multiple hypotheses testing procedure is proposed and applied for China and India stock markets. The procedure is constructed using bootstrap method for individual hypotheses and Bonferroni correction for multiple testing. It is shown that homogenity hypothesis of degree distribution for the stock market for the period of 2003 - 2-14 is not accepted.
The inverse max ++ sum spanning tree (MSST) problem is considered by modifying the sum-cost vector under the Hamming Distance. On an undirected network G(V, E, w, c), a weight w(e) and a cost c(e) are prescribed for each edge e∈Ee∈E. The MSST problem is to find a spanning tree T∗T∗ which makes the combined weight maxe∈Tw(e)+∑e∈Tc(e)maxe∈Tw(e)+∑e∈Tc(e) as small as possible. It can be solved in O(mlogn)O(mlogn) time, where m:=|E|m:=|E| and n:=|V|n:=|V|. Whereas, in an inverse MSST problem, a given spanning tree T0T0 of G is not an optimal MSST. The sum-cost vector c is to be modified to c¯c¯ so that T0T0 becomes an optimal MSST of the new network G(V,E,w,c¯)G(V,E,w,c¯) and the cost ∥c¯−c∥‖c¯−c‖ can be minimized under Hamming Distance. First, we present a mathematical model for the inverse MSST problem and a method to check the feasibility. Then, under the weighted bottleneck-type Hamming distance, we design a binary search algorithm whose time complexity is O(mlog2n)O(mlog2n). Next, under the unit sum-type Hamming distance, which is also called l0l0 norm, we show that the inverse MSST problem (denoted by IMSST00) is NP−NP−hard. Assuming NP⊈DTIME(mpolylogm)NP⊈DTIME(mpolylogm), the problem IMSST00 is not approximable within a factor of 2log1−εm2log1−εm, for any ε>0ε>0. Finally, We consider the augmented problem of IMSST00 (denoted by AIMSST00), whose objective function is to multiply the l0l0 norm ∥β∥0‖β‖0 by a sufficiently large number M plus the l1l1 norm ∥β∥1‖β‖1. We show that the augmented problem and the l1l1 norm problem have the same Lagrange dual problems. Therefore, the l1l1 norm problem is the best convex relaxation (in terms of Lagrangian duality) of the augmented problem AIMSST00, which has the same optimal solution as that of the inverse problem IMSST00.
Vehicle Routing Problem is a well-known problem in logistics and transportation. There is a big variety of VRP problems in the literature, as they arise in many real-life situations. It is a NP-hard combinatorial optimization problem and finding an exact optimal solution is practically impossible in real-life formulations. There is an important subclass of VRP, which is called Truck and Trailer Routing Problem. For this class of problems, every vehicle contains truck and, possibly, trailer parts. In this work, Site-Dependent Truck and Trailer Routing Problem with Hard and Soft Time Windows and Split Deliveries are considered. We develop an Iterative Local Search heuristic for solving this problem. The heuristic is based on the local search approach and also allows infeasible solutions. A greedy heuristic is applied to construct an initial solution.