• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Of all publications in the section: 24
Sort:
by name
by year
Article
Stonyakin F. S., Alkousa M., Stepanov A. N. et al. Journal of Applied and Industrial Mathematics. 2019. Vol. 13. P. 557-574.

Under consideration are some adaptive mirror descent algorithms for the problems of minimization of a convex objective functional with several convex Lipschitz (generally, nonsmooth) functional constraints. It is demonstrated that the methods are applicable to the objective functionals of various levels of smoothness: The Lipschitz condition holds either for the objective functional itself or for its gradient or Hessian (while the functional itself can fail to satisfy the Lipschitz condition). The main idea is the adaptive adjustment of the method with respect to the Lipschitz constant of the objective functional (its gradient or Hessian), as well as the Lipschitz constant of the constraint. The two types of methods are considered: adaptive (not requiring the knowledge of the Lipschitz constants neither for the objective functional nor for constraints, and partially adaptive (requiring the knowledge of the Lipschitz constant for constraints). Using the restart technique, some methods are proposed for strongly convex minimization problems. Some estimates of the rate of convergence are obtained for all algorithms under consideration in dependence on the level of smoothness of the objective functional. Numerical experiments are presented to illustrate the advantages of the proposed methods for some examples.

Added: Oct 29, 2020
Article
Malyshev D. Journal of Applied and Industrial Mathematics. 2012. Vol. 6. No. 1. P. 97-99.

Under study is the complexity status of the independent set problem in a class of connected graphs that are defined by functional constraints on the number of edges depending on the number of vertices. For every natural number C, this problem is shown to be polynomially solvable in the class of graphs, On the other hand, this problem is proved to be not polynomially solvable in the class of graphs, for every unbounded nondecreasing function f(n): ℕ → ℕ, such that exponent of this function grows faster than a polynomial function of n. The latter result is true if there does not exist a subexponential algorithm for solving the independent set problem.

Added: Dec 7, 2012
Article
Malyshev D. Journal of Applied and Industrial Mathematics. 2013. Vol. 7. No. 2. P. 221-228.

The notion of a boundary class of graphs is a helpful tool for the computational complexity analysis of graph theory problems in the family of hereditary classes. Some general and specific features for families of boundary classes of graphs for the vertex k-colorability problem and its “limit” variant, the chromatic index problem, were studied by the author earlier. In the present article, these problems are considered in application to the edge version of the colorability problem. It turns out that each boundary class for the edge 3-colorability problem is a boundary class for the chromatic index problem; however, for each k > 3, there exist uncountably many boundary classes for the edge k-colorability problem each of which is not a boundary class for the chromatic index problem.We formulate some necessary condition for the existence of boundary classes of graphs for the vertex 3-colorability problem which are not boundary for the chromatic index problem. To the author’s mind, this condition is never satis.ed and so there are no such boundary classes for the vertex 3-colorability problem.

Added: Jun 23, 2013
Article
Romanov V. G., Nazarov A. Journal of Applied and Industrial Mathematics. 2012. Vol. 6. No. 4. P. 460-468.
Under study is the problem of finding the kernel and the index of dielectric permeability for the system of integrodifferential electrodynamics equations with wave dispersion. We consider a direct problem in which the external pulse current is a dipole located at a point y on the boundary ∂B of the unit ball B. The point y runs over the whole boundary and is a parameter of the problem. The information available about the solution to the direct problem is the trace on ∂B of the solution to the Cauchy problem given for the times close to the time when a wave from the dipole source arrives at a point x. The main result of the article consists in obtaining some theorems related to the uniqueness problems for a solution to the inverse problem.
Added: Feb 4, 2013
Article
Malyshev D. Journal of Applied and Industrial Mathematics. 2014. Vol. 8. No. 2. P. 245-255.
The edge list-ranking problem is a generalization of the classical edge coloring problem, and it is a mathematical model for some parallel processes. The computational complexity of this problem is under study for graph sets closed under isomorphism and deletion of vertices (hereditary classes). Allfinitely defined and minor-closed cases are described for which the problem is polynomial-time solvable (unless P=NP). Wefind the whole set of“critical”graph classes whose inclusion in a finitely defined class is equivalent to intractability of the edge list-ranking problem in this class (unless P=NP). It seems to be thefirst result on a complete description for nonartificial NP-complete graph problems. For this problem, weprove constructively that, among the inclusion minimal NP-complete hereditary cases, there are exactlyfivefinitely defined classes and the only minor-closed class.
Added: May 8, 2014
Article
Malyshev D. Journal of Applied and Industrial Mathematics. 2013. Vol. 7. No. 4. P. 537-548.

We prove the polynomial solvability of the independent set problem for some family of classes of the planar subcubic graphs.

Added: Jan 21, 2014
Article
Malyshev D. Journal of Applied and Industrial Mathematics. 2020. Vol. 14. No. 4. P. 706-721.

The edge coloring problem for a graph is to minimize the number of colors that are sufficient to color all edges of the graph so that all adjacent edges receive distinct colors. The computational complexity of the problem is known for all graph classes defined by forbidden subgraphs with at most 6 edges. We improve this result and obtain a complete complexity classification of the edge coloring problem for all sets of prohibitions each of which has at most 7 edges.

Added: Jan 30, 2021
Article
Malyshev D. Journal of Applied and Industrial Mathematics. 2017. Vol. 11. No. 1. P. 99-106.

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.

Added: Feb 13, 2017
Article
Gribanov D., Malyshev D., Mokeev D. B. Journal of Applied and Industrial Mathematics. 2020. Vol. 14. P. 480-489.

We consider the problem of minimizing the number of colors in the colorings of the vertices of a given graph so that, to each vertex there is assigned some set of colors whose number is equal to the given weight of the vertex; and adjacent vertices receive disjoint sets. For all hereditary classes defined by a pair of forbidden induced connected subgraphs on 5 vertices but four cases, the computational complexity of the weighted vertex coloring problem with unit weights is known. We prove the polynomial solvability on the sum of the vertex weights for this problem and the intersection of two of the four open cases. We hope that our result will be helpful in resolving the computational complexity of the weighted vertex coloring problem in the above-mentioned forbidden subgraphs.

Added: Oct 30, 2020
Article
Razvenskaya O., Malyshev D. Journal of Applied and Industrial Mathematics. 2021. Vol. 15. No. 1. P. 97-117.

The weighted vertex coloring problem for a given weighted graph is to minimize the number of colors so that for each vertex the number of the colors that are assigned to this vertex is equal to its weight and the assigned sets of vertices are disjoint for any adjacent vertices. For all but four hereditary classes that are defined by two connected 5-vertex induced prohibitions, the computational complexity is known of the weighted vertex coloring problem with unit weights. For four of the six pairwise intersections of these four classes, the solvability was proved earlier of the weighted vertex coloring problem in time polynomial in the sum of the vertex weights. Here we justify this fact for the remaining two intersections.

Added: Apr 23, 2021
Article
Malyshev D. Journal of Applied and Industrial Mathematics. 2013. Vol. 7. No. 3. P. 412-419.

The notion is introduced of an expanding operator for the independent set problem. This notion is a useful tool for the constructive formation of new cases with the efficient solvability of the problem in the family of hereditary classes of graphs and is applied to hereditary parts of the set Free({P_5,C_5}). It is proved that if for a connected graph G the problem is polynomial-time solvable in the class Free({P_5,C_5,G}) then it remains so in the class Free({P_5,C_5,G*O_2,G+K_1,p}) for every p. We also find two new hereditary subsets of Free({P_5,C_5}) with polynomially solvable the independent set problem that are not a corollary of appling the revealed operators.     

Added: Oct 3, 2013
Article
Rozhkov M., Malakhov S. Journal of Applied and Industrial Mathematics. 2019. Vol. 13. No. 2. P. 302-309.

MDS matrices are widely used as a diffusion primitive in the construction of block type encryption algorithms and hash functions (such as AES and GOST 34.12–2015). The matrices with the maximum number of 1s and minimum number of different elements are important for more efficient realizations of the matrix-vector multiplication. The article presents a new method for the MDS testing of matrices over finite fields and shows its application to the (8 × 8)-matrices of a special form with many 1s and few different elements; these matrices were introduced by Junod and Vaudenay. For the proposed method we obtain some theoretical and experimental estimates of effectiveness. Moreover, the article comprises a list of some MDS matrices of the above-indicated type.

Added: Jun 10, 2019
Article
Kochergin V. V. Journal of Applied and Industrial Mathematics. 2015. Vol. 9. No. 1. P. 68-82.

We study two generalizations of the classical problem of fast exponentiation, namely: Bellman’s problemon computational complexity (the minimal number ofmultiplications) based only on the variables of a normalized monomial of m variables and Knuth’s problem on the complexity of the simultaneous calculation of a system of m powers of one variable. Some results for these problems are reviewed in the paper. The asymptotic complexity bounds for Bellman’s and Knuth’s problems are improved for the cases whenmand complexity behave similarly (have the same growth order). The upper and lower complexity bounds for almost all sets of exponents for Bellman’s and Knuth’s problems that are established provide the complexity growth asymptotics for a wide range of relations between parameters (the number of variables or the computed exponents, the maximal power, and the product of all powers). Moreover, they guarantee the ratio of the upper and lower bounds not exceeding 5/3 for all relations between the parameters.

Added: Oct 8, 2018
Article
Malyshev D., Mokeev D. B. Journal of Applied and Industrial Mathematics. 2019. Vol. 13. No. 1. P. 85-92.

We describe the class of graphs whose each subgraph has the next property: The maximal number of disjoint 4-paths is equal to the minimal cardinality of sets of vertices such that every 4-path in the subgraph contains at least one of these vertices. We completely describe the set of minimal forbidden subgraphs for this class. Moreover, we present an alternative description of the class based on the operations of edge subdivision applied to bipartite multigraphs and the addition of so-called pendant subgraphs, isomorphic to triangles and stars.

Added: Feb 13, 2019
Article
Gribanov D., Malyshev D. Journal of Applied and Industrial Mathematics. 2020. Vol. 14. No. 1. P. 56-72.

Under consideration is the Successive Minima Problem for the 2-dimensional lattice with respect to the order given by some conic function f.We propose an algorithm with complexity of 3.32*log_2(R)+O(1) calls to the comparison oracle of f, where R is the radius of the circular searching area, while the best known lower oracle complexity bound is 3*log_2(R) + O(1).We give an efficient criterion for checking that given vectors of a 2-dimensional lattice are successive minima and form a basis for the lattice.Moreover, we show that the similar Successive Minima Problem for dimension n can be solved by an algorithm with at most (O(n))^{2n}*log_2(R) calls to the comparison oracle. The results of the article can be applied to searching successive minima with respect to arbitrary convex functions defined by the comparison oracle.

Added: Mar 3, 2020
Article
Веселов С. И., Gribanov D., Zolotykh N. et al. Journal of Applied and Industrial Mathematics. 2018. Vol. 12. No. 3. P. 587-594.

We consider the minimization problem for a symmetric quasiconvex function defined by an oracle on the set of integer points of a square. We formulate an optimality criterion for the solution, obtain a logarithmic lower bound for the complexity of the problem, and propose an algorithm for which the number of inquiries to the oracle is at most thrice the lower bound.

Added: Feb 17, 2019
Article
Makarov D., Yashunsky A. Journal of Applied and Industrial Mathematics. 2019. Vol. 13. No. 2. P. 280-289.

We consider the two-dimensional generalizations of de Bruijn sequences; i.e., the integer-valued arrays whose all fragments of a fixed size (windows) are different. For these arrays, dubbed sub-de Bruijn, we consider the complexity of decoding; i.e., the determination of a position of a window with given content in an array. We propose a construction of arrays of arbitrary size with arbitrary windows where the number of different elements in the array is of an optimal order and the complexity of decoding a window is linear.

Added: Sep 9, 2020
Article
Kochergin V.V., Mikhailovich A.V. Journal of Applied and Industrial Mathematics. 2018. Vol. 12. No. 1. P. 40-58.

The complexity of realization of k-valued logic functions by circuits in a special infinite basis is under study. This basis consists of Post negation (i.e. function x+1(mod k)) and all monotone functions. The complexity of the circuit is the total number of elements of this circuit. For an arbitrary function f, we find the lower and upper bounds of complexity, which differ from one another at most by 1. The complexity has the form 3log_3 (d(f)+1)+O(1), here d(f) is the maximum number of the value decrease of the value of f taken over all increasing chains of tuples of variable values. We find the exact value of the corresponding Shannon function which characterizes the complexity of the most complex function of a given number of variables.

Added: Mar 11, 2018
Article
Sirotkin D., Malyshev D. Journal of Applied and Industrial Mathematics. 2018. Vol. 12. No. 4. P. 759-769.

The 3-coloring problem for a given graph consists in verifying whether it is possible  to divide the vertex set of the graph into three subsets of pairwise nonadjacent vertices. A complete complexity classification is known for this problem for the hereditary classes defined by triples of forbidden induced subgraphs, each on at most 5 vertices. In this article, the quadruples of forbidden induced subgraphs is under consideration, each on at most 5 vertices. For all but three corresponding hereditary classes, the computational status of the 3-coloring problem is determined. Considering two of the remaining three classes, we prove their polynomial equivalence and polynomial reducibility to the third class.

Added: Nov 20, 2018
Article
Mokeev D. B., Malyshev D. Journal of Applied and Industrial Mathematics. 2020. Vol. 14. No. 2. P. 369-384.

We describe the hereditary class of graphs, whose every subgraph has the property that the maximum number of disjoint 5-paths (paths on 5 vertices) is equal to the minimum size of the sets of vertices having nonempty intersection with the vertex set of each 5-path. We describe this class in terms of the "forbidden subgraphs" and give an alternative description, using some operations on pseudographs.

Added: Jun 19, 2020
Article
Taletskii D., Malyshev D. Journal of Applied and Industrial Mathematics. 2018. Vol. 12. No. 2. P. 369-381.

For each n and d, we describe the structure of trees with the maximal possible number of greatest independent sets in the class of n-vertex trees of vertex degree at most d. We show that for all even n an extremal tree is unique but uniqueness may fail for odd n; moreover, for d = 3 and every odd n>6, there are exactly ceil{(n-3)/4} + 1 extremal trees. In the paper, the problem of searching for extremal (n; d)-trees is also considered for 2-caterpillars, i.e., trees in which every vertex lies at distance at most two from some simple path. For each n and d=3,4, we completely reveal all extremal 2-caterpillars on n vertices each of which has degree at most d.

Added: Jun 22, 2018
1 2