检索结果-内蒙古大学图书馆

Heuristic for maximizing grouping efficiency in the cell formation problem

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Bychkov, Ilya Batsyn, Mikhail Pardalos, Panos M. Laboratory of Algorithms and Technologies for Network Analysis National Research University Higher School of Economics 136 Rodionova Street Nizhny Novgorod603093 Russia Center for Applied Optimization University of Florida 401 Weil Hall P.O. Box 116595 GainesvilleFL32611-6595

In our paper we consider the Cell Formation Problem in Group Technology with grouping efficiency as an objective function. We present a heuristic approach for obtaining high-quality solutions of the CFP. The suggested heuristic applies an improvement procedure to obtain solutions with high grouping efficiency. This procedure is repeated many times for randomly generated cell configurations. Our computational experiments are performed for popular benchmark instances taken from the literature with sizes from 10x20 to 50x150. Better solutions unknown before are found for 23 instances of the 24 considered. Copyright © 2017, The Authors. All rights reserved.

关键词： Heuristic methods

Faster algorithms for Sparse ILP and Hypergraph Multi-Packing/Multi-Cover Problems

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Gribanov, Dmitry Malyshev, Dmitry Zolotykh, Nikolai Shumilov, Ivan Laboratory of Algorithms and Technologies for Network Analysis HSE University 136 Rodionova Ulitsa Nizhny Novgorod603093 Russia Lobachevsky State University of Nizhny Novgorod 23 Gagarina Avenue Nizhny Novgorod603950 Russia Mathematics of Future Technologies Center Lobachevsky State University of Nizhni Novgorod 23 Gagarina Avenue Nizhny Novgorod603950 Russia

In our paper, we consider the following general problems: check feasibility, count the number of feasible solutions, find an optimal solution, and count the number of optimal solutions in P ∩ Zn, assuming that P is a polyhedron, defined by systems Ax ≤ b or Ax = b, x ≥ 0 with a sparse matrix A. We develop algorithms for these problems that outperform state of the art ILP and counting algorithms on sparse instances with bounded elements. We use known and new methods to develop new exponential algorithms for Edge/Vertex Multi-Packing/Multi-Cover Problems on graphs and hypergraphs. This framework consists of many different problems, such as the Stable Multi-set, Vertex Multi-cover, Dominating Multi-set, Set Multi-cover, Multi-set Multi-cover, and Hypergraph Multi-matching problems, which are natural generalizations of the standard Stable Set, Vertex Cover, Dominating Set, Set Cover, and Maximum Matching problems. Copyright © 2022, The Authors. All rights reserved.

关键词： Optimal systems

Delta-modular ILP Problems of Bounded Codimension, Discrepancy, and Convolution

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Gribanov, Dmitry V. Malyshev, Dmitry S. Pardalos, Panos M. Laboratory of Discrete and Combinatorial Optimization Moscow Institute of Physics and Technology Institutsky lane 9 Moscow region Dolgoprudny141700 Russia Laboratory of Algorithms and Technologies for Network Analysis HSE University 136 Rodionova Ulitsa Nizhny Novgorod603093 Russia Department of Industrial and Systems Engineering University of Florida 401 Weil Hall GainesvilleFL116595 United States

For k, n ≥ 0, and c ∈ Zn, we consider ILP problems max(c+x: Ax = b, x ∈ Zn≥0+} with A ∈ Zk×n, rank(A) = k, b ∈ Zk and max{cTx: Ax ≤ b, x ∈ Zn} with A ∈ Z(n+k)×n, rank(A) = n, b ∈ Zn+k. The first pr... 详细信息

For k, n ≥ 0, and c ∈ Zn, we consider ILP problems max(c+x: Ax = b, x ∈ Zn≥0+} with A ∈ Zk×n, rank(A) = k, b ∈ Zk and max{cTx: Ax ≤ b, x ∈ Zn} with A ∈ Z(n+k)×n, rank(A) = n, b ∈ Zn+k. The first problem is called an ILP problem in the standard form of the codimension k, and the second problem is called an ILP problem in the canonical form with n+k constraints. We show that, for any sufficiently large ∆, both problems can be solved with 2O(k) · (fk,d · ∆)2/2Ω(√log(fk,d·∆)) operations, where fk,d = min n kk/2, (log k · log(d + k))k/2o , d is the dimension of a corresponding polyhedron and ∆ is the maximum absolute value of rank(A) × rank(A) sub-determinants of A. Our result improves the best previously known computational complexity bound (log k)O(k2) · ∆2 · polylog(∆, n, k). As our second main result, we show that the feasibility variants of both problems can be solved with 2O(k) · fk,d · ∆ · log3(fk,d · ∆) operations. The constant fk,d can be replaced by other constant gk,∆ = (log k · log(k∆))k/2 that depends only on k and ∆. Additionally, we consider different partial cases with k = 0 and k = 1, which have interesting applications: the expected ILP computational complexity with respect to a varying right-hand side b, ILP problems with generic constraint matrices, ILP problems on simplices. Based on our results with respect to small k, we present refined computational complexity bounds for these applications. As a result of independent interest, we propose an n2/2Ω(√log n) -time algorithm for the tropical convolution problem on sequences, indexed by elements of a finite Abelian group of the order n. This result is obtained, reducing the above problem to the matrix multiplication problem on a tropical semiring and using seminal algorithm by R. Williams. Additionally, we give a complete, self-contained error analysis of the generalized Discrete Fourier Transform for Abelian groups with respect to the Word-RAM computational model. Copyright © 2024, The Authors. All rig

关键词： Convolution

On NP-completeness of the cell formation problem

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Batsyn, Mikhail V. Batsyna, Ekaterina K. Bychkov, Ilya S. Laboratory of Algorithms and Technologies for Network Analysis National Research University Higher School of Economics 25/12 B. Pecherskaya Nizhny Novgorod603155 Russia Department of Applied Mathematics and Informatics National Research University Higher School of Economics 25/12 B. Pecherskaya Nizhny Novgorod603155 Russia

In the current paper we provide a proof of NP-completeness for the Cell Formation Problem (CFP) with the fractional grouping efficacy objective. For this purpose we first consider the CFP with the linear objective minimizing the total number of exceptions and voids. Following the ideas of Pinheiro et al. (2016) we show that it is equivalent to the Bicluster Graph Editing Problem (BGEP), which is known to be NP-complete (Amit 2004). Then we suggest a reduction of the CFP problem with the linear objective function to the CFP with the grouping efficacy objective. Copyright © 2019, The Authors. All rights reserved.

关键词： Cellular manufacturing

Calcium transient imaging as tool for neuronal and glial network interaction study

学校读者我要写书评

暂无评论

Calcium transient imaging as tool for neuronal and glial net...

作者： Zakharov, Yu. N. Mitroshina, E.V. Shirokova, O. Mukhina, I.V. Radiophysical faculty N. I. Lobachevsky State University of Nizhny Novgorod 23 Gagarin ave. Nizhny Novgorod Russia Laboratory of Algorithms and Technologies for Network Analysis The National Research University Higher School of Economics 136 Rodionova Str. Nizhny Novgorod Russian Federation 603093 Russia Nizhny Novgorod State Medical Academy 10/1 Minin sq Nizhny Novgorod Russia Biological faculty N. I. Lobachevsky State University of Nizhny Novgorod 23 Gagarin ave. Nizhny Novgorod Russia

ISBN: (纸本)9781461455738

Signaling in neuronal networks plays a crucial role in regulating the processes of proper network formation during development and learning in the matured nervous system. Adaptation of neuronal networks to the cultured conditioning in the absence of external drive stimulates appearance of self-sustained spiking patterns without any specific stimuli. Some alteration like electrical stimulation, medium changing, metabolic activation, or depression of mature culture evokes to novel properties of spiking pattern. These properties are reversible usually and may be considered as a new function system occurring in consequence of strong stimulations. Intracellular calcium transients are the basic signaling mechanisms in nerve cells in addition to membrane potential. However, little is known about the transition of spontaneous intracellular calcium dynamics and the relationship between calcium transients and electrical activity during network development. To identify function neuronal networks in vitro we investigated spontaneous intracellular calcium transients in mouse hippocampal networks cultured on MEA for month after plating. © Springer Science+Business Media New York 2013.

关键词： Neurons

On ∆-Modular Integer Linear Problems In The Canonical Form And Equivalent Problems

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Gribanov, Dmitry Shumilov, Ivan Malyshev, Dmitry Pardalos, Panos Laboratory of Algorithms and Technologies for Network Analysis HSE University 136 Rodionova Ulitsa Nizhny Novgorod603093 Russia Lobachevsky State University of Nizhny Novgorod 23 Gagarina Avenue Nizhny Novgorod603950 Russia Department of Industrial and Systems Engineering University of Florida 401 Weil Hall GainesvilleFL116595 United States

Many papers in the field of integer linear programming (ILP, for short) are devoted to problems of the type max{cx: Ax = b, x ∈ Zn≥0}, where all the entries of A, b, c are integer, parameterized by the number of rows of A and kAkmax. This class of problems is known under the name of ILP problems in the standard form, adding the word"bounded" if x ≤ u, for some integer vector u. Recently, many new sparsity, proximity, and complexity results were obtained for bounded and unbounded ILP problems in the standard form. In this paper, we consider ILP problems in the canonical form max{cx: bl ≤ Ax ≤ br, x ∈ Zn}, where bl and br are integer vectors. We assume that the integer matrix A has the rank n, (n + m) rows, n columns, and parameterize the problem by m and ∆(A), where ∆(A) is the maximum of n × n sub-determinants of A, taken in the absolute value. We show that any ILP problem in the standard form can be polynomially reduced to some ILP problem in the canonical form, preserving m and ∆(A), but the reverse reduction is not always possible. More precisely, we define the class of generalized ILP problems in the standard form, which includes an additional group constraint, and prove the equivalence to ILP problems in the canonical form. We generalize known sparsity, proximity, and complexity bounds for ILP problems in the canonical form. Additionally, sometimes, we strengthen previously known results for ILP problems in the canonical form, and, sometimes, we give shorter proofs. Finally, we consider the special cases of m ∈ {0, 1}. By this way, we give specialised sparsity, proximity, and complexity bounds for the problems on simplices, Knapsack problems and Subset-Sum problems. Copyright © 2020, The Authors. All rights reserved.

关键词： Equivalence classes

On existence of a Morse energy function for topological flows with finite chain recurrent sets

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Medvedev, Timur V. Pochinka, Olga V. Zinina, Svetlana Kh. Laboratory of Algorithms and Technologies for Network Analysis National Research University Higher School of Economics 136 Rodionova Street Niznhy Novgorod Russia National Research University Higher School of Economics 25/12 Bolshaya Pecherckaya Street Niznhy Novgorod Russia Ogarev Mordovia State University 111v-2 Bolshevistskaya street Saransk Russia

We prove the existence of a continuous Morse energy function for an arbitrary topological flow with finite hyperbolic (in topological sense) chain recurrent set on a topological manifold of any dimension. This result is a partial solution of the Morse problem of existence of continuous Morse functions on any topological manifolds. Namely, we prove that a topological manifold admits a continuous Morse function if it admits a topological ow with finite hyperbolic chain recurrent set. Copyright © 2019, The Authors. All rights reserved.

关键词： Lyapunov functions

A New and Faster Representation for Counting Integer Points in Parametric Polyhedra

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Gribanov, Dmitry V. Malyshev, Dmitry S. Pardalos, Panos M. Zolotykh, Nikolai Yu. Laboratory of Discrete and Combinatorial Optimization Moscow Institute of Physics and Technology Institutsky Lane 9 Moscow Region Dolgoprudny141700 Russia Laboratory of Algorithms and Technologies for Network Analysis HSE University 136 Rodionova Ulitsa Nizhny Novgorod603093 Russia Department of Industrial and Systems Engineering University of Florida 401 Weil Hall GainesvilleFL116595 United States Lobachevsky State University of Nizhny Novgorod 23 Gagarina Avenue Nizhny Novgorod603950 Russia

In this paper, we consider the counting function EP(y) = | Py ∩ Znx | for a parametric polyhedron Py = {x ∈ Rnx : Ax ≤ b + By}, where y ∈ Rny. We give a new representation of EP(y), called a piece-wise step-polynomial with periodic coefficients, which is a generalization of piece-wise step-polynomials and integer/rational Ehrhart’s quasi-polynomials. It gives the fastest way to calculate EP(y) in certain scenarios. The most important cases are the following: 1) We show that, for the parametric polyhedron Py defined by a standard-form system Ax = y, x ≥ 0 with a fixed number of equalities, the function EP(y) can be represented by a polynomial-time computable function. In turn, such a representation of EP(y) can be constructed by an poly(n, A∞)-time algorithm;2) Assuming again that the number of equalities is fixed, we show that integer/rational Ehrhart’s quasi-polynomials of a polytope can be computed by FPT-algorithms, parameterized by sub-determinants of A or its elements;3) Our representation of EP is more efficient than other known approaches, if A has bounded elements, especially if it is sparse in addition;Additionally, we provide a discussion about possible applications in the area of compiler optimization. In some "natural" assumptions on a program code, our approach has the fastest complexity bounds. Copyright © 2023, The Authors. All rights reserved.

关键词： Polynomial approximation

Marine mammal calls detection in acoustic signals via gradient boosting model

学校读者我要写书评

暂无评论

Proceedings of Meetings on Acoustics 2021年第1期44卷

作者： Mikhail Salin Alexander Ponomarenko 1Center of Hydroacoustics Institute of Applied Physics RAS Nizhny Novgorod 603950 RUSSIAN FEDERATION mikesalin@ipfran.ru 2Laboratory of Algorithms and Technologies for Network Analysis National Research University Higher School of Economics Niznhy Novgorod RUSSIAN FEDERATION aponomarenko@hse.ru

This paper is devoted to methods of processing hydrophone records in order to identify specific signals, produced by marine mammals. The aim of processing is to detect a signal according to a certain pattern against the background of non-stationary noise. Development of a robust detection algorithm is of great interest because it could help to assess marine mammal occurrence and distribution at greater temporal and spatial scales by excluding laborious task of manually analyzing acoustic data. In addition, such algorithm may be implemented in automatic systems designed to warn vessel crew to avoid potential collision with whales. The data, studied in this paper, contained the calls of North Atlantic right whales, that were collected in the Gulf of St. Lawrence. Machine learning is exploited to solve a signal detection problem. The model was trained by a set of manually labelled signal fragments. Each fragment is labelled whether a whale call is present or not in the fragment. The proposed detection method is based on the two-level stacked gradient boosting models (XGBoost algorithm). The first-level model deals with spectral features, extracted from the short signal frames. The second model accumulates estimated output for a group of subsequent frames.

关键词：