Reusing the Same Coloring in the Child Nodes of the Search Tree for the Maximum Clique Problem
Lecture Notes in Computer Science. 2015. Vol. 8994. P. 275-280.
Nikolaev A., Batsyn M., San Segundo P.
In this paper we present a new approach to reduce the computational time spent on coloring in one of the recent branch-and-bound algorithms for the maximum clique problem. In this algorithm candidates to the maximum clique are colored in every search tree node. We suggest that the coloring computed in the parent node is reused for the child nodes when it does not lead to many new branches. So we reuse the same coloring only in the nodes for which the upper bound is greater than the current best solution only by a small value δ. The obtained increase in performance reaches 70 % on benchmark instances.
Priority areas: IT and mathematics
, , et al., Journal of Combinatorial Optimization 2014 Vol. 27 No. 2 P. 397-416
In this paper we present improvements to one of the most recent and fastest branch-and-bound algorithm for the maximum clique problem—MCS algorithm by Tomita et al. (Proceedings of the 4th international conference on Algorithms and Computation, WALCOM’10, pp. 191–203, 2010). The suggested improvements include: incorporating of an efficient heuristic returning a high-quality initial solution, fast ...
Added: February 17, 2013
, , , Computers & Operations Research 2015 Vol. 64 P. 293-303
Many efficient exact branch and bound maximum clique solvers use approximate coloring to compute an upper bound on the clique number for every subproblem. This technique reasonably promises tight bounds on average, but never tighter than the chromatic number of the graph. Li and Quan, 2010, AAAI Conference, p. 128–133 describe a way to compute even ...
Added: August 24, 2015
, Информационные технологии 2016 Т. 22 № 4 С. 249-254
In this paper a new approach for solving the maximum clique problem is presented. For a given graph the suggested approach uses machine learning technique to predict the fastest algorithm from several algorithms for the maximum clique problem. Then the chosen algorithm is applied for solving the maximum clique problem in this graph. The computational ...
Added: May 27, 2016
Hybrid neural network and bi-criteria tabu-machine: comparison of new approaches to maximum clique problem
, , , International Journal of Big Data Intelligence 2018 Vol. 5 No. 3 P. 143-155
This paper presents two new approaches to solving a classical NP-hard problem of maximum clique problem (MCP), which frequently arises in the domain of information management, including design of database structures and big data processing. In our research, we are focusing on solving that problem using the paradigm of artificial neural networks. The first approach ...
Added: October 3, 2018
Implementation and Use of Coarse-grained Parallel Branch-and-bound in Everest Distributed Environment
, , , Procedia Computer Science 2017 Vol. 108 P. 1532-1541
This paper examines the coarse-grained approach to parallelization of the branch-and-bound (B&B) algorithm in a distributed computing environment. This approach is based on preliminary decomposition of a feasible domain of mixed-integer programming problem into a set of subproblems. The produced subproblems are solved in parallel by a distributed pool of standalone B&B solvers. The incumbent ...
Added: August 30, 2018
, , , Journal of Global Optimization 2014 Vol. 59 No. 1 P. 1-21
In this paper we consider two branch and bound algorithms for the maximum clique problem which demonstrate the best performance on DIMACS instances among the existing methods. These algorithms are MCS algorithm by Tomita et al. (2010) and MAXSAT algorithm by Li and Quan (2010a, b). We suggest a general approach which allows us to speed ...
Added: May 24, 2013
, , , , in : Models, Algorithms, and Technologies for Network Analysis. Vol. 59.: NY : Springer, 2013. Ch. 7. P. 93-99.
In this chapter, we present our enhancements of one of the most efficient exact algorithms for the maximum clique problem—MCS algorithm by Tomita, Sutani, Higashi, Takahashi and Wakatsuki (in Proceedings of WALCOM’10, 2010, pp. 191–203). Our enhancements include: applying ILS heuristic by Andrade, Resende and Werneck (in Heuristics 18:525–547, 2012) to find a high-quality initial solution, fast detection ...
Added: November 19, 2013
, , Optimization Letters 2015 Vol. 9 No. 5 P. 839-843
The quadratic programming problem is known to be NP-hard for Hessian matrices with only one negative eigenvalue, but it is tractable for convex instances. These facts yield to consider the number of negative eigenvalues as a complexity measure of quadratic programs. We prove here that the clique problem is tractable for two variants of its Motzkin-Strauss ...
Added: September 26, 2014
, Using modular decomposition technique to solve the maximum clique problem / Cornell University Library. 2017.
In this article we use the modular decomposition technique for exact solving the weighted maximum clique problem. Our algorithm takes the modular decomposition tree from the paper of Tedder et. al. and finds solution recursively. Also, we propose algorithms to construct graphs with modules. We show some interesting results, comparing our solution with Ostergard's algorithm ...
Added: October 15, 2017
, , et al., 2017 Т. 13 № 1 С. 19-24
The complexity of the individual traveling salesman problem was analyzed by means of mathematical statistics. The complexity is defined as a number of nodes of the decision tree created by the branch and bound algorithm. We obtained approximate representations for parameters of probability distribution of the natural logarithm of the complexity. These representations are functions ...
Added: September 26, 2017
, , , An efficient approach to the protein structure alignment problem / Институт прикладной математики им. М.В. Келдыша Российской академии наук. 2015. No. 91.
The Protein Structure Alignment Problem (PSAP) consists in finding the best alignment of two proteins defined by their primary structures. It finds the most similar substructure of two proteins. This problem is polynomially reducible to the Maximum Clique Problem (MCP) for the protein alignment graph. In this paper we present an efficient algorithm for the PSAP based on our recent ...
Added: October 24, 2016
, , et al., Pre-experiments on Annotation of Russian Coreference Corpus / НИУ ВШЭ. Series WP BRP "Linguistics". 2015.
Building benchmark corpora in the domain of coreference and anaphora resolution is an important task for developing and evaluating NLP systems and models. Our study is aimed at assessing the feasibility of enhancing corpora with information about coreference relations. The annotation procedure includes identification of text segments that are subjects to annotation (markables), marking their ...
Added: December 15, 2015
, , Computational Mathematics and Modeling 2016 Vol. 27 No. 2 P. 247-253
Added: December 22, 2016
, , Вестник Московского финансово-юридического университета 2017 № 1 С. 200-206
Some questions of scientific visualization are under consideration in this paper. This article also discusses the peculiarities of application of cognitive computer graphics, singles out a range of tasks of scientific visualization. The paper gives a brief overview of modern support tools for program visualization, tendencies of their development and their main characteristics. A module ...
Added: June 10, 2017
, , et al., Physica A: Statistical Mechanics and its Applications 2014 Vol. 413 No. 1 P. 59-70
A general approach to measure statistical uncertainty of different filtration techniques for market network analysis is proposed. Two measures of statistical uncertainty are introduced and discussed. One is based on conditional risk for multiple decision statistical procedures and another one is based on average fraction of errors. It is shown that for some important cases ...
Added: July 19, 2014
М. : National Instruments Russia, 2017
Содержание сборника составляют доклады с результатами оригинальных исследований и технических решений, ранее не публиковавшиеся. Мы надеемся, что предлагаемый сборник окажется полезным для специалистов, работающих в различных областях науки и техники, для широкого круга преподавателей, аспирантов и студентов ВУЗов, а также для преподавателей средних школ и технических колледжей. ...
Added: May 10, 2017
, , , Inorganic Materials: Applied Research 2016 Vol. 7 No. 1 P. 34-39
A database (DB) on the bandgap of inorganic substances available via the Internet (http://bg.imetdb.ru) was developed for the information service of specialists in the sphere of inorganic chemistry and materials science. The DB is integrated with other information systems on the properties of inorganic substances and materials, which provides the search of a wide range ...
Added: February 23, 2016
, М. : Юрайт, 2016
В настоящее время компьютерные науки стремительно развиваются. Новые версии операционных систем появляются каждые полтора-два года, поэтому было принято решение о включении в данную книгу такого материала, который не будет устаревать. Содержание учебника представляет собой некоторые наиболее общие принципы построения операционных систем, которые были разработаны более 50 лет назад и практически не изменились за прошедшее время. ...
Added: October 13, 2009
, , Bernoulli: a journal of mathematical statistics and probability 2013 Vol. 19 No. 4 P. 1268-1293
Motivated by a problem arising when analysing data from quarantine searches, we explore properties of distributions of sums of independent means of independent lattice-valued random variables. The aim is to determine the extent to which approximations to those sums require continuity corrections. We show that, in cases where there are only two different means, the ...
Added: September 29, 2014
"Авиакосмические технологии" (АКТ-2014): Тезисы I тура XV Всероссийской научно-технической конференции и школы молодых ученых, аспирантов и студентов
ООО Фирма "Элист", 2014
В книге представлены тезисы докладов I тура XV Всероссийской научно-технической конференции и школы молодых ученых, аспирантов и студентов. ...
Added: October 17, 2014
Barcelona : International Association of Technology, Education and Development , 2012
Added: September 11, 2012
Совершенствование преподавания дисциплин математического цикла на основе инвариантов, необходимых для преподавания курса «Эконометрика» экономистам-бакалаврам
, , Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Социальные науки 2019 Т. 55 № 3 С. 183-189
The article describes a method that allows to improve the content of disciplines of the mathematical cycle by dividing them into invariant (general) and variable parts. The invariants were identified for such disciplines as «Linear algebra», «Mathematical analysis», «Probability theory and mathematical statistics» delivered to Bachelors program students of economics at several universities. Based on ...
Added: January 28, 2020
Методика самовосстановления распределенной системы контроля и управления техническими объектами на основе методов теории принятия решений
, , , Датчики и системы 2018 Т. 221 № 1 С. 18-24
The article discusses the recovery of distributed control systems of technical objects. The options for the design of subsystems recovery after hardware or software fault of the sensor system are investigated. The development of an integrated subsystems recovery is proposed on the basis of decision-making system to develop the most rational control actions by ...
Added: January 27, 2018
On the Impact of Word Error Rate on Acoustic-Linguistic Speech Emotion Recognition: An Update for the Deep Learning Era
, On the Impact of Word Error Rate on Acoustic-Linguistic Speech Emotion Recognition: An Update for the Deep Learning Era / Cornell University. Series Computer Science "arxiv.org". 2021.
Text encodings from automatic speech recognition (ASR) transcripts and audio representations have shown promise in speech emotion recognition (SER) ever since. Yet, it is challenging to explain the effect of each information stream on the SER systems. Further, more clarification is required for analysing the impact of ASR's word error rate (WER) on linguistic emotion ...
Added: February 14, 2023