Program Download in doc format
Second International Conference on
Network Analysis 2012
May 7th – May 9th, 2012
Center for Applied optimization (CAO),
University of Florida, USA
Laboratory of Algorithms and Technologies for Networks Analysis
(LATNA), Higher School of Economics, Russia
Monday, May 7th
Room 313 HSE, 25/12 Bolshaya Pecherskaya Str.
15:00-15:30 Panos M. Pardalos
Second International Conference on Network Analysis 2012
15:30-16:20 Christodoulos A. Floudas
Towards Large Scale Deterministic Global Optimization
16:20-16:40 Coffee Break
16:40-18:10 Session 1
Ludmila Egorova
Behavioral model of stock exchange
Dmitry Malyshev
On expanding operators for the independent set problem
Dmitry Mokeev
Structural and complexial properties of P3-könig graphs
Victor Zamaraev
A heuristics for the weighted independent set problem
Tuesday, May 8th
Room 313 HSE, 25/12 Bolshaya Pecherskaya Str.
10:00-10:50 Boris Mirkin
Representing Activities by Taxonomy Concepts: Clustering and Lifting
10:50-11:10 Coffee Break
11:10-12:30 Session 1
Pando G. Georgiev
Innovative tools for analyzing state transitions and evolution of complex dynamic networks
Alexey Yashunsky
Using Online Social Networks for Social Geography Studies
Alexander Rubchinsky
A New Algorithm of Network Decomposition and its Application for Stock Market Analysis
12:30-14:00 Lunch Break
14:00-14:50 Ding-Zhu Du
Min-Weight Connected Sensor Cover and Max-Lifetime Target Coverage
14:50-15:50 Session 2
Anton Kocheturov
Market Graph Analysis by Means of the P-Median Problem
Mikhail Batsyn
Applying Tolerances to the Asymmetric Capacitated Vehicle Routing Problem
Evgeny Maslov
Complex approach to solving the maximum clique problem
15:50-16:10 Coffee Break
16:10-17:30 Session 3
Grigory Bautin
Markov chains in modeling of the Russian financial market
Dmitry Gorbunov
Simulation of Pedestrian Crowds with Anticipation using Cellular Automata Approach
Pankaj Kumar
Behavioural Dynamics in Stock Market
Lazarev Evgeny Alexandrovich
Bi-criteria model and algorithms of solving data transmission network optimization problem
Wednesday, May 9th
Room 313 HSE, 25/12 Bolshaya Pecherskaya Str.
9:30-10:20 Mauricio G. C. Resende
Randomized Algorithms for the Handover Minimization Problem in Wireless Network Design
10:20-10:40 Coffee Break
10:40-12:20 Session 1
D.V. Kasatkin
Synaptic cellular automaton for description the sequential dynamics of excitatory neural networks
Pavel Sukhov
Heuristic Algorithm for the Single Machine Scheduling Problem
Ilya Bychkov
“Patterns” for solving the Cell Formation Problem
Peter Koldanov
Statistical Properties of the Market Graph
12:30-14:00 Lunch Break
Towards Large Scale Deterministic Global Optimization
Christodoulos A. Floudas
Department of Chemical and Biological Engineering
Princeton University, USA
floudas@princeton.edu
In this seminar, we will provide an overview of the research progress in deterministic global optimization. The focus will be on important contributions during the last five years, and will provide a perspective for future research opportunities. The overview will cover the areas of (a) twice continuously differentiable constrained nonlinear optimization, and (b) mixed-integer nonlinear optimization models. Subsequently, we will present our recent fundamental advances in (i) convex envelope results for multi-linear functions, and edge concave functions, (ii) a piecewise quadratic convex underestimator for twice continuously differentiable functions, (iii) piecewise linear relaxations of bilinear functions, (iv) large scale extended pooling problems, and (v) large scale generalized pooling problems. Computational studies on medium and large scale global optimization applications will illustrate the potential of these advances.
Behavioral model of stock exchange
Fuad Aleskerov, Lyudmila Egorova
National Research University Higher School of Economics, Moscow, Russia
alesk@hse.ru, legorova@hse.ru
Due to the global financial crisis and its consequences stock exchange nowadays is an essential element of market infrastructure, a sensitive "barometer" to the slightest changes in the economy. For this reason the importance of the study of the stock exchange processes and the construction of adequate models of the exchange game has been increased. Behavioral finance is a new direction in financial economics, which explains the trading process based on investor psychology and the impact of their behavior on the market. Recently Taleb N.N. suggested to analyze the crises (called Black Swans) as the events with three main properties. A Black Swan is a very rare event, it carries an extreme impact, and the occurrence of this event cannot be predicted in advance (and only after the Black Swan happened we can come up with its explanation). Thus, the Black Swan is a metaphor for the crisis itself. Therefore everyone has to expect these Black Swans and be ready for their occurrence. However, should all investors follow such a strategy? And should we expect a rare and unpredictable event, even with a big impact, rather than deal with “the bird in the hand”?
To answer this question we construct a mathematical model of the stock exchange, in which the processes are modeled as a reaction to the signals about the state of the economy. There are two Poisson flows of signals/events of two types, one of which is 'regular' event that corresponds to a stable economy and the second one is the 'crisis' event signaling about the crisis. The intensity of the first flow is much greater than the intensity of the crisis events (Black Swans rarity condition). The player does not know in advance about the type of the incoming signal and have to recognize it (the condition of unpredictability). Player’s wealth depends on how well she identifies the signals on the stock exchange, because gain/loss from the crisis event is much greater than the gain/loss in case of the ordinary, frequent events (condition of great influence).
We showed that the average player's gain will be positive if she can correctly recognize the ordinary events in slightly more than in the half of the cases. In other words, players do not need to play more sophisticated games, trying to identify crises events in advance. This conclusion resembles the logic of precautionary behavior, that prescripts to play the game with almost reliable small wins. We believe that this very phenomenon lies in the basis of unwillingness of people to expect crises permanently and to try recognizing them. The proposed model was tested on stock exchange indices (S&P 500, Dow Jones, САС 40, DAX, Nikkei 225, Hang Seng, on time interval 1999-2009) and on data of different shares (Microsoft, General Electric, Morgan Chase, Proctor&Gamble, Johnson&Johnson, Apple, AT&T, IBM, Bank of America).
Acknowledgement. We are grateful for partial financial support of the HSE International Laboratory of Decision Choice and Analysis (DeCAn Lab) and NRU HSE Science Foundation (grant № 10-04-0030). Lyudmila Egorova expresses sincere gratitude to the HSE Laboratory of Algorithms and Technologies for Networks Analysis (LATNA) for partial financial support.
On expanding operators for the independent set problem
Malyshev Dmitry Sergeevich
National Research University Higher School of Economics,
National Research University Lobachevky State University of Nizhniy Novgorod, Russia
dmalishev@hse.ru
All considered graphs are simple, i.e. undirected unlabeled graph without loops and multiple edges. A class of graphs is a set of simple graphs. A class of graphs is called hereditary if it is closed under deletions of vertices. It is known that a hereditary (and only hereditary class) can defined by a set of its forbidden induced subgraphs , i.e. graphs that don't belong to . It is denoted by.
Let be an NP-complete graph problem. A hereditary graph class is called -easy if is polynomial-time solvable for graphs in. All known to the author proofs of papers on expansions of cases with polynomial-time solvability substantially use a specific character of the old, narrower case. At the same time, it would be desirable to have «universal» such kind generalizations. For the family of hereditary graph classes it is offered to consider transformations (one- or many-variable function with arguments in a part of ), such that and from -easiness of follows that is also -easy. We will refer such kind transformations to -expanding operators.
The case, when is the independent set problem and , will be only considered further. The interest in hereditary subclasses of is conditioned by several causes. Firstly, if , then the independent set problem is polynomial-time solvable in if and only if is a forest. Moreover, the case is unique among all connected graphs with five vertices with open computational status of the problem for . There are many papers in which one or more forbidden induced subgraphs are added to and the effective solvability of the problem for obtained graphs class is proved. Secondly, for any graph with at most five vertices, and , the problem admits a polynomial-time algorithm for graphs in . Unfortunately, its complexity is unknown for the class .
Two concrete expanding operators for the independent set problem will be specified further. The product of and is the graph . It is easy to see that the mapping is an expanding operator for the problem. Two more such operators are described below.
Theorem. The mapping is an expanding operator for the independent set problem. For any natural the mapping is an expanding operator for the independent set problem.
The author is partially supported by LATNA Laboratory, NRU HSE, RF government grant, ag. 11.G34.31.0057, by Russian Foundation for Basic Research, grants11-01-00107-а и 12-01-00749-а, and by Federal Target Program «Academic and educational specialists of innovative Russia», state contract16.740.11.0310
Structural and complexial properties of P3-könig graphs
D. B. Mokeev
National Research University Lobachevky State University of Nizhniy Novgorod, Russia
mokeevDB@mail.ru
Hereditary class of graphs in which maximum number of non-intersecting P3-subgraphs is equal with minimum number of vertexes contains in every such subgraphs and polynomial recognition algorithm for this class are described.
A heuristics for the weighted independent set problem
B.I. Goldengorin1, D.S. Malyshev1,2, P.M. Pardalos1,3, V.A. Zamaraev1,2
1Laboratory of Algorithms and Technologies for Network Analysis, National Research University Higher School of Economics, Nizhniy Novgorod, Russia
2National Research University Lobachevky State University of Nizhniy Novgorod, Russia
3Center for Applied Optimization, University of Florida, Gainesville, USA
b.goldengorin@rug.nl, dmalishev@hse.ru, p.m.pardalos@gmail.com, vzamaraev@hse.ru
In this paper we design a new heuristic tolerance-based algorithm for solving the Weighted Independent Set problem (the WIS, for short). Our algorithm is based on the polynomially solvable special case of the WIS, which is defined on trees (the WIST, for short). We show that an optimal solution and all tolerances with respect to this solution of the WIST might be simultaneously found by the adjusted Chen et al. dynamic programming algorithm in O(n) time. Based on this procedure we offer a heuristic algorithm for the WIS, which takes O(mnlog(m)) time. We also present several computational experiments for its approximation ratio, they showed good enough results for some models of sparse graphs.
The authors is partially supported by LATNA Laboratory, NRU HSE, RF government grant, ag. 11.G34.31.0057. This study comprises research findings from the ‘Calculus of tolerances in combinatorial optimization problems: theory and algorithms’ Project carried out within The Higher School of Economics’ 2012 Academic Fund Program.
Representing Activities by Taxonomy Concepts: Clustering and Lifting
Boris Mirkin
National Research University Higher School of Economics, Moscow RF
Birkbeck University of London, London UK
bmirkin@hse.ru
Given a taxonomy of a domain, the activities of an organization in the domain can be represented by crisp or fuzzy clusters of the corresponding taxonomy leaf concepts (thematic clusters). To represent a thematic cluster in the taxonomy, a parsimonious lifting method is developed. The method maps the cluster’s topics to higher ranks of the taxonomy tree. The lifting criterion involves a penalty function summing penalties for the "head" subjects together with penalties for emerging gaps and offshoots. The developments are illustrated by using synthetic and real-world data.
Innovative tools for analyzing state transitions and evolution of complex dynamic networks
Pando G. Georgiev and Panos M. Pardalos
Center for Applied Optimization
University of Florida, Gainesville, USA
pandogeorgiev@ufl.edu, p.m.pardalos@gmail.com
The problem of detection and prediction of changes (state transitions), dependences and causalities in the evolution of complex networks is of tremendous significance. Several important practical networks desperately need tools for prediction, for instance: in biological networks - epileptic brain networks for prediction of epileptic seizures; in power system networks - electric grid, for prediction of blackouts; in social networks - for prediction of malicious behaviors of some social groups, etc.
We present several innovative tools applicable to this problem:
1) Reproducing Kernel Banach Spaces.
We extend the idea of Reproducing Kernel Hilbert Spaces to Banach spaces (and beyond), developing a theory without the requirement of existence of semi-inner product (which requirement is already explored in another construction of RKBS). We apply our construction to the basic learning algorithms, including support vector machines, kernel regression, kernel principal component analysis. We demonstrate the better adaptive features of such spaces to new dimensionality reduction techniques and to detection of state transitions in some complex networks, as epileptic brain. We introduce a qualitative new concept ”multiple reproducing kernels”, which encompasses not only bivariate, but also multivariate connections between data variables, arranging them in a kernel tensor - a generalization of the kernel matrix.
2) Tensor decompositions.
Multi-way structures of the data has been widely ignored in many fields of research, especially in dynamical complex networks. The functional MRI is another typical example, where the data is inheritably tensorial. Collapsing some of the modes to form of a matrix or vector leads to loss of information. Many tensor representations admit uniqueness of the decomposition without additional constraints such as orthogonality (as in Singular value decomposition, or PCA) or independence (as in Independent Component Analysis). We review some tensor decomposition methods and introduce new ones, involving sparsity, suitable for complex sparse networks.
3) Adaptive multi-class learning problems.
We generalize the main task of statistical learning theory to multiclass learning problems, allowing several classes approximating functions to choose adaptively from several classes of data (possibly heterogeneous).
4) Nonlinear skeletons of data sets and skeleton classifiers.
A particular case of multiclass learning problems is the problem of subspace clustering, which we extend to RKBS defining in such a way the concept of nonlinear skeletons and its derivative, Skeleton Classifier.
5) Trajectory reconstruction.
Square roots, or more generally, iterative roots of operators are of interest in dynamical systems, chaos and complexity theory and also in the modeling of certain industrial and financial processes. An operator f acting from a set X to X, satisfying the functional equation f(f(x)) = F(x) (for every x from X) is called ”square root” of the given operator F acting from X to X. The problem of computing square roots of operators (if exists) remains a hard task. While the theory of functional equations provides some insight for the iterative roots of real and complex valued functions, iterative roots of mappings in high dimensional spaces are almost not studied and there are little contributions to numerical algorithms for their computation. We prove existence of iterative roots of a certain class of monotone mappings in Hilbert spaces, generalizing the scalar case result for strictly monotone functions. We demonstrate how methods based on neural networks and statistical learning theory can find square roots of trajectories of certain dynamical systems.
Using Online Social Networks for Social Geography Studies
Alexey Yashunsky1 and Nadezda Zamiatina2
1Keldysh Institute of Applied Mathematics, Russia
2Geography Department, Moscow State University, Russia
yashunsky@keldysh.ru, nadezam@mail.ru
Research in social and economic geography more often than not relies on various statistics as raw data. Hence, the lack of trustworthy and detailed statistical materials may become a hinderance. Whereas developed countries (e.g. USA, EU countries) have vast statistic databases open to the public, the emerging economies and developing countries to this day still have very limited statistical information available.
This statistical vacuum forces researchers to look for other sources of information. These can be found, for instance, within online social networking services. Although this information is hardly representative of the entire population and never absolutely trustworthy, it can still be used to study certain social groups.
These research techniques may be of interest even for developed countries for studying phenomena that are not reflected by official statistics.
We have recently carried out some basic research on "knowledge spillover" in modern Russia using public data from the vk.com social network. The studied cases revealed some interesting spacial patterns in the origin and later employment locations of several Russian Universities' students. Further and deeper analysis may allow identification of the so-called bonding and bridging connections for Universities and trace their spacial components so as to evaluate their influence on creative and labor force migrations in modern Russia.
The challenges for network analysis in this area are both technical and theoretical. On the one hand, processing social network data with geographical goals requires the development of specific tools, on the other hand, formal network-level criteria could help the identification of certain geography-specific phenomena.
A New Algorithm of Network Decomposition and its Application for Stock Market Analysis
Boris Goldengorin1, Panos Pardalos1,2, Alexander Rubchinsky1
1Laboratory of Algorithms and Technologies for Network Analysis, National Research University Higher School of Economics, Nizhny Novgorod, Russia
2Center for Applied Optimization, University of Florida, Gainesville, USA
b.goldengorin@rug.nl, p.m.pardalos@gmail.com, arubchinsky@yahoo.com
The network decomposition problem is one of the well-known «classical» problems of network analysis. Informal character and great diversity of applications have led to many different formal statements of the problem. The essence of the suggested approach consists in a new combination of two known ideas: finding a cut by the so called frequency method and checking statistical stability of obtained divisions. In both directions new modifications are suggested.
The algorithm is constructed as a multistage procedure. A result of every stage is a family of decompositions that firstly is gradually expanded and after gradually contracted so that the output of the entire procedure consists of one decomposition.
The essential features of the suggested approach are formulated as follows.
1. The number of parts is determined by the algorithm itself. Particularly, the algorithm can establish the absence of reasonable divisions (at least, in the framework of the suggested method).
2. The output can produce not only decompositions but single parts and their families as well.
3. There are only few (for such a universal scheme) meaningful parameters.
The approach is applied to analysis of data from stock markets of USA, Sweden and Russia. The only input data consists of all the pairwise correlations between prices of stocks. The network is constructed as follows. Its vertices correspond to stocks; any vertex is connected to 4 closest (with the maximal correlation coefficients) vertices. Stable clusters were revealed in USA and Russian stocks. They correspond to firms engaged in the same or close kinds of activity (for instance, in USA in gold mining and investment, in Russia in electricity production). In Sweden market the algorithm does not reveal stock clusters.
Min-Weight Connected Sensor Cover and Max-Lifetime Target Coverage
Ding-Zhu Du
University of Texas at Dallas, USA
dzdu@utdallas.edu
It was open for many years whether the target coverage problem has a polynomial-time constant-approximation or not. In this talk, we introduce a solution, 3.65-approximation, which is a new result in our research group in UTD (University of Texas at Dallas).
The target coverage problem can be stated as follows:
Suppose each sensor has unit lifetime and a unit disk as its coverage area. Given a set of target-points and a set of sensors in the Euclidean plane, find a sensor sleep/activate schedule to maximize the lifetime under constraint that every target-point is monitored by at least one sensor during the lifetime. This constant-approximation is established by its connection to minimum weight connected sensor cover problem
Market Graph Analysis by Means of the P-Median Problem
Mikhail Batsyn1, Boris Goldengorin1, Anton Kocheturov1, Panos Pardalos1,2
1Laboratory of Algorithms and Technologies for Network Analysis, National Research University Higher School of Economics, Nizhny Novgorod, Russia
2Center for Applied Optimization, University of Florida, Gainesville, USA
mbatsyn@hse.ru, b.goldengorin@rug.nl, antrubler@gmail.com, p.m.pardalos@gmail.com
In this work we apply pseudo-Boolean approach to analysis of stock market graphs. We divide market graphs into clusters of highly correlated stocks by means of the p-Median model and search for regularity in the calculated results. Our final goal is to provide a new tool for a deeper understanding of the market structure dynamics.
Applying Tolerances to the Asymmetric Capacitated Vehicle Routing Problem
Mikhail Batsyn1, Boris Goldengorin1, Panos Pardalos1,2
1Laboratory of Algorithms and Technologies for Network Analysis, National Research University Higher School of Economics, Nizhny Novgorod, Russia
2Center for Applied Optimization, University of Florida, Gainesville, USA
mbatsyn@hse.ru, b.goldengorin@rug.nl, p.m.pardalos@gmail.com
In this talk we consider the Asymmetric Capacitated Vehicle Routing Problem (ACVRP). We solve the ACVRP with two different versions of branch-and-bound algorithm. The first one is the classical branch-and-bound algorithm which uses the cost-based branching rule. The second one is a new branch-and-bound algorithm in which we first take the branch which has the minimal tolerance. Such a tolerance-based approach was suggested by Boris Goldengorin, Gerard Sierksma and Marcel Turkensteen (2004) and proved its efficiency for the Asymmetric Travelling Salesman Problem (ATSP). We compare the number of search tree nodes and computational times for these two algorithms on several ACVRP instances and show that tolerance-based branching rule is more efficient.
We also present a new heuristic algorithm for the ACVRP which can be related to the class of cluster-first route-second heuristics. On the first stage the vertices are divided into K clusters by solving the Capacitated P-Median Problem so that all the vertices from one cluster can be visited by one of the K vehicles. This problem is solved exactly by means of the pseudo-Boolean p-median model suggested by Boris Goldengorin and his co-authors in 2009-2011. On the second stage the ATSP problem is solved exactly for each cluster again using a tolerance-based approach. After these two stages we iteratively move vertices between the found routes while the objective function is improved. Among all the vertices we move that vertex from one route to another, for which this movement is feasible and the improvement of the objective function is maximal.
A Combined Approach to Solving the Maximum Clique Problem
Mikhail Batsyn1, Boris Goldengorin1, Evgeny Maslov1, Panos Pardalos1,2
1Laboratory of Algorithms and Technologies for Network Analysis, National Research University Higher School of Economics, Nizhny Novgorod, Russia
2Center for Applied Optimization, University of Florida, Gainesville, USA
mbatsyn@hse.ru, b.goldengorin@rug.nl, lyriccoder@gmail.com, p.m.pardalos@gmail.com
In this talk we suggest a combined approach to solving the Maximum Clique Problem (MCP). It is based on two classical NP-hard combinatorial optimization problems: the Graph Coloring Problem (GCP) and the Maximum Independent Set Problem (MISP). We use heuristic solutions of these problems to improve the performance of our exact algorithm. Following the MCS algorithm (Tomita, Sutani, Higashi, Takahashi and Wakatsuki, 2010), graph coloring is used as a branching strategy for finding the maximum clique. A heuristic solution of the MISP for the complement graph returns a good lower bound for the MCP and improves the performance of the algorithm. Moreover, if colors are first assigned to those vertices which are in the large cliques, then the large search sub-trees related to such vertices are pruned due to the small color numbers. We have also improved the sequential graph coloring suggested by Tomita, Sutani, Higashi, Takahashi and Wakatsuki (2010). We illustrate our findings by means of a computational study for the MCP.
Markov chains in modeling of the Russian financial market
Grigory Bautin and Valery Kalyagin
Laboratory of Algorithms and Technologies for Network Analysis
National Research University Higher School of Economics, Nizhny Novgorod, Russia
greg.bautin@gmail.com, vkalyagin@hse.ru
We consider a Markov chains model for the problem of multiperiod portfolio optimization, and apply it to the Russian stock market. Due to higher volatility and other peculiarities of the Russian market, the known approaches produce the phenomena of non stability. We propose enhancements to the model in order to smooth it.
Simulation of Pedestrian Crowds with Anticipation using Cellular Automata Approach
Mikhail Batsyn1, Boris Goldengorin1, Dmitry Gorbunov1, Panos Pardalos1,2
1Laboratory of Algorithms and Technologies for Network Analysis, National Research University Higher School of Economics, Nizhny Novgorod, Russia
2Center for Applied Optimization, University of Florida, Gainesville, USA
mbatsyn@hse.ru, b.goldengorin@rug.nl, dmigorbunov@gmail.com, p.m.pardalos@gmail.com
Recently, cellular automata have been applied to models of traffic and evacuation without mental properties. Goldengorin, Krushinsky and Makarenko have shown that three criteria namely the minimization of evacuation time, maximization of instantaneous flow of pedestrians, and maximization of mentality-based synchronization of a crowd are interdependent. In this talk we discuss our implementation of this model and its potential application to study networks of neurons.
Behavioural Dynamics in Stock Market
Pankaj Kumar
Perm State National Research University, Russian Federation
kumar.x.pankaj@gmail.com
Stock market is an example of complex system, which is characterized by a highly intricate organization and the emergence of collective behaviour. In this paper, we quantify this behavioural dynamics in the stock market by using concepts of network synchronization. We consider networks constructed by the correlation matrix of asset returns and study the time evolution of the phase coherence among stock prices. It is verified that during financial crisis a synchronous state emerges in the system, defining the market's direction. Furthermore, the paper proposes a statistical regression model able to identify the network topological features that mostly influence such an emergence. The coefficients of the proposed model indicate that the average shortest path length is the measurement most related to network synchronization. Therefore, during economic crisis, the stock prices present a similar evolution, which tends to shorten the distances between stocks, indication a collective behavioural dynamics.
Bi-criteria model and algorithms of solving data transmission network optimization problem
Lazarev Evgeny Alexandrovich, Misevich Pavel Valerievich, Shaposhnikov Dmitry Evgenievich
Nizhny Novgorod State Technical University n.a. R.E. Alexeev, Nizhny Novgorod, Russia
elazarev.nnov@gmail.com, p_misevich@mail.ru, dm.shaposhnikov@gmail.com
A data transmission network model based on classic network-flow models is proposed. Consider acyclic oriented graph , describing existing data transmission network. Vertices of the graph represent multiplexers of the network. Edge connects vertices and , represents the data channel and has positive capacity . Two vertices of the graph and are considered information source and sink respectively.
The set () describes data channels which can be added to the network. The capacity and construction cost is given for each edge .
The amount of information which can be transmitted over the data channel per time unit is defined by the flow function ( describes the flow between vertices and ).
It is necessary to modify existing network by construction some channels of the set to increase the maximum network flow. A possible solution of the problem is a set of edges . Two optimization criteria are considered:
1. The cost of data channels construction:
2. The maximum network flow: ,
described by the graph .
Optimization problem: for given acyclic oriented graph and the set of edges , capacity matrices , and construction cost matrix find the set of Pareto-optimal solutions of problem .
It is proven that cardinality of the Pareto-optimal solutions set can have exponential dependence on the problem dimension (cardinality of ). Also, it is proven that the problem is NP-hard (the knapsack problem is polynomially reduced to the considered problem).
Taking into account assumption that and computational difficulty of the problem heuristic methods are proposed to find sub-optimal solutions for the considered problem. The paper presents exact algorithms based on branch and bound method, heuristic algorithms based on genetic algorithms and simulated annealing algorithm and results of computational experiments.
Randomized Algorithms for the Handover Minimization Problem in Wireless Network Design
Mauricio G. C. Resende
Algorithms & Optimization Research Department
AT&T Labs Research
Shannon Laboratory, Florham Park, New Jersey, USA
mgcr@research.att.com
Mobile wireless devices connect to an antenna tower to which it has a strong signal. As the device moves it may connect to a sequence of towers. The process that takes place when a device changes the tower to which it is connected to is called handover (or handoff). Handovers are not done by the tower itself but rather by the radio network controller
(RNC) to which the tower is connected. Each tower has associated with it a traffic level which depends, for example, on where it is located. One or more towers can connect to an RNC but each RNC can handle a maximum amount of traffic thus limiting the subsets of towers that can connect to it. Handovers between towers connected to different RNCs tend to fail more often than those between towers connected to the same RNC.
Handover failure causes a dropped call which one would prefer to avoid.
Therefore minimizing the number of handovers between towers connected to different RNCs may lead to a more reliable level of wireless service.
Given a set of towers, each with a given amount of traffic, a set of RNCs, each with a given capacity, and a matrix specifying the number of handovers between pairs of towers, the HANDOVER MINIMIZATION PROBLEM (HMP) seeks an assignment of towers to RNCs such that the RNC capacity is not violated and the number of handovers between towers connected to different RNCs is minimized.
We describe three randomized heuristics for solving the HMP. The first is a GRASP with path-relinking for the generalized quadratic assignment problem. The other two are specially tailored for the HMP. One is is a GRASP with evolutionary path-relinking and the other is a biased random-key genetic algorithm.
We compare these heuristics on a set of randomly generated instances as well as on real-world networks from a large wireless provider.
Synaptic cellular automaton for description the sequential dynamics of excitatory neural networks
D.V. Kasatkin1, A.S. Dmitrichev1, V.I. Nekorkin1,2
1Institute of Applied Physics of the Russian Academy of Sciences, Nizhny Novgorod, Russia
2Laboratory of Algorithms and Technologies for Network Analysis, National Research University Higher School of Economics, Nizhniy Novgorod, Russia
kasatkin@neuron.appl.sci-nnov.ru, admitry@neuron.appl.sci-nnov.ru, vnekorkin@neuron.appl.sci-nnov.ru
One of the significant problems of neurodynamics is development of analytical methods for studying of models of complex neural networks. We present an approach for analyzing the dynamics of excitatory neural networks. It consists in reducing continuous dynamics of neural networks to a discrete dynamical systems in the form of a cellular automaton (CA) on the graph of connections. In the approach the main role is played by the dynamics of synapses but not by the specific features of neurons. In fact, the CA represents a network of synapses with a finite number of states which alternate each other according to some fixed rules. To determine the rules one needs to study only the responses of an individual synapse onto actions of neighboring (in graph of connections) synapses through corresponding neurons. As a result the numerical integration of the whole system of ordinary differential equations (ODEs) is not needed. Moreover, since the form of the neuron responses is not important, the approach is applicable to a broad set of networks including those consisting of neurons, which possess the neural excitability property (neurons of the class 2 excitability).
Heuristic Algorithm for the Single Machine Scheduling Problem
Boris Goldengorin1, Panos Pardalos1,2, Pavel Sukhov1
1Laboratory of Algorithms and Technologies for Network Analysis, National Research University Higher School of Economics, Nizhny Novgorod, Russia
2Center for Applied Optimization, University of Florida, Gainesville, USA
b.goldengorin@rug.nl, p.m.pardalos@gmail.com, pavelandreevith@rambler.ru
There are three single machine scheduling problems with an open computational complexity status. One of them, the preemptive single machine scheduling problem of minimizing the total weighted completion time with equal processing times and arbitrary release dates, will be discussed in this talk. We are going to describe three heuristics for this scheduling problem. Two of them are based on it's linear assignment problem reduction, and one based on the WSRPT (weighted shortest remaining processing time) rule. Our computational experiments show that the WSRPT rule based heuristic returns either an exact optimal or a high quality schedule.
“Patterns” for solving the Cell Formation Problem
Mikhail Batsyn1, Ilya Bychkov1, Boris Goldengorin1, Panos Pardalos1,2
1Laboratory of Algorithms and Technologies for Network Analysis, National Research University Higher School of Economics, Nizhny Novgorod, Russia
2Center for Applied Optimization, University of Florida, Gainesville, USA
mbatsyn@hse.ru, il.bychkov@gmail.com, b.goldengorin@rug.nl, p.m.pardalos@gmail.com
In this paper we define the notion of a “pattern” which is closely connected with the Assignment Problem solution and show how to apply it for solving one well-known combinatorial optimization problem, namely the Cell Formation Problem. Our iterative algorithm is based on flexible adjustments of the given collection of cells starting with an initial solution. The algorithm terminates when all possible adjustments of shapes and sizes for each cell and the current collection of all cells cannot be improved by means of the prespecified objective function value. Sometimes such iterations may lead to patching a pair of neighboring cells or splitting each cell in a number of cells. Experiments with the number of cells allow us to increase the objective function values for some cell formation problem benchmark instances.
Statistical Properties of the Market Graph
Valery Kalyagin1, Alexander Koldanov1, Peter Koldanov1, Panos Pardalos1,2
1Laboratory of Algorithms and Technologies for Network Analysis, National Research University Higher School of Economics, Nizhny Novgorod, Russia
2Center for Applied Optimization, University of Florida, Gainesville, USA
vkalyagin@hse.ru, akoldanov@hse.ru, pkoldanov@hse.ru, p.m.pardalos@gmail.com
The paper deals with the statistical analysis of the construction method of the market graph introduced in [Boginski, Butenko and Pardalos 2003]. The main goal of the paper is the investigation of the optimality of the method of construction of the market graph from the statistical point of view. According to the classical approach by Wald the optimal statistical procedures is the statistical procedures with the minimal conditional risk in a fixed class. In our investigation we consider the class of unbiased statistical procedures. As a statistical model of the financial market we use the classical model by Markowitz. According to this model the returns of financial stocks have a multivariate normal distribution defined by the vector of their means and the covariance matrix. The market graph (true market graph) is the matrix with entries 0 and 1, where we put 0 if the associated correlation is less then given threshold and 1 otherwise. Sample market graph is the market graph constructed from the sample correlations. The main question discussed in this paper is the relation between true and sample market graphs. The construction method of the market graph introduced in [Boginski, Butenko and Pardalos 2003] can be considered as a statistical procedure for the construction of the true market graph from the sample market graph. We show that this method is optimal in the class of unbiased multiple decision statistical procedures. To prove this result we put the problem in the framework of Lehman theory of multiple decision statistical procedures and precise the choice of generating hypothesis.
Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!
To be used only for spelling or punctuation mistakes.