Article
Maximum shortest path interdiction problem by upgrading edges on trees under hamming distance
We consider the maximum shortest path interdiction problem by upgrading edges on
trees under Hamming distance (denoted by (MSPITH)), which has wide applications
in transportation network, networkwar and terrorist network. The problem (MSPITH)
aims to maximize the length of the shortest path from the root of a tree to all its leaves
by upgrading edge weights such that the upgrade cost under sum-Hamming distance
is upper-bounded by a given value. We show that the problem (MSPITH) under
weighted sum-Hamming distance is NP-hard. We consider two cases of the problem
(MSPITH) under unit sum-Hamming distance based on the number K of critical
edges. We propose a greedy algorithm within O(n + l log l) time when K = 1 and a
dynamic programming algorithm within O(n(log n + K3)) time when K > 1, where
n and l are the numbers of nodes and leaves in a tree, respectively. Furthermore, we
consider a minimum cost shortest path interdiction problem by upgrading edges on
trees under unit Hamming distance, denoted by (MCSPITUH) and propose a binary
search algorithm within O(n4 log n) time, where a dynamic programming algorithm
is executed in each iteration to solve its corresponding problem (MSPITH). Finally,
we design numerical experiments to show the effectiveness of the algorithms.
The issues of information support based on the use of artifical neural networks for the rapid recognition of odors using devices such as "elecronic nose" are considered. The variants the reducing the test sampl for an artifical neural network are proposed with the aim of increasing the stabilutyof computatijns and the speed of calculations. A method for the rapid recognition of odors in the presence of background odors is proposed.
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.
Shortest path problems play important roles in computer science, communication networks, and transportation networks. In a shortest path improvement problem under unit Hamming distance, an edge-weighted graph with a set of source–terminal pairs is given. The objective is to modify the weights of the edges at a minimum cost under unit Hamming distance such that the modified distances of the shortest paths between some given sources and terminals are upper bounded by the given values. As the shortest path improvement problem is NP-hard, it is meaningful to analyze the complexity of the shortest path improvement problem defined on rooted trees with one common source. We first present a preprocessing algorithm to normalize the problem. We then present the proofs of some properties of the optimal solutions to the problem. A dynamic programming algorithm is proposed for the problem, and its time complexity is analyzed. A comparison of the computational experiments of the dynamic programming algorithm and MATLAB functions shows that the algorithm is efficient although its worst-case complexity is exponential time.
The issues of information support based on the use of artifical neural networks for the rapid recognition of odors using devices such as "elecronic nose" are considered. The variants the reducing the test sampl for an artifical neural network are proposed with the aim of increasing the stabilutyof computatijns and the speed of calculations. A method for the rapid recognition of odors in the presence of background odors is proposed.
We address the complexity class of several problems related to finding a path in a properly colored directed graph. A properly colored graph is defined as a graph G whose vertex set is partitioned into X(G) stable subsets, where X(G) denotes the chromatic number of G. We show that to find a simple path that meets all the colors in a properly colored directed graph is NP-complete, and so are the problems of finding a shortest and longest of such paths between two specific nodes.
A model for organizing cargo transportation between two node stations connected by a railway line which contains a certain number of intermediate stations is considered. The movement of cargo is in one direction. Such a situation may occur, for example, if one of the node stations is located in a region which produce raw material for manufacturing industry located in another region, and there is another node station. The organization of freight traffic is performed by means of a number of technologies. These technologies determine the rules for taking on cargo at the initial node station, the rules of interaction between neighboring stations, as well as the rule of distribution of cargo to the final node stations. The process of cargo transportation is followed by the set rule of control. For such a model, one must determine possible modes of cargo transportation and describe their properties. This model is described by a finite-dimensional system of differential equations with nonlocal linear restrictions. The class of the solution satisfying nonlocal linear restrictions is extremely narrow. It results in the need for the “correct” extension of solutions of a system of differential equations to a class of quasi-solutions having the distinctive feature of gaps in a countable number of points. It was possible numerically using the Runge–Kutta method of the fourth order to build these quasi-solutions and determine their rate of growth. Let us note that in the technical plan the main complexity consisted in obtaining quasi-solutions satisfying the nonlocal linear restrictions. Furthermore, we investigated the dependence of quasi-solutions and, in particular, sizes of gaps (jumps) of solutions on a number of parameters of the model characterizing a rule of control, technologies for transportation of cargo and intensity of giving of cargo on a node station.
Event logs collected by modern information and technical systems usually contain enough data for automated process models discovery. A variety of algorithms was developed for process models discovery, conformance checking, log to model alignment, comparison of process models, etc., nevertheless a quick analysis of ad-hoc selected parts of a journal still have not get a full-fledged implementation. This paper describes an ROLAP-based method of multidimensional event logs storage for process mining. The result of the analysis of the journal is visualized as directed graph representing the union of all possible event sequences, ranked by their occurrence probability. Our implementation allows the analyst to discover process models for sublogs defined by ad-hoc selection of criteria and value of occurrence probability
Existing approaches suggest that IT strategy should be a reflection of business strategy. However, actually organisations do not often follow business strategy even if it is formally declared. In these conditions, IT strategy can be viewed not as a plan, but as an organisational shared view on the role of information systems. This approach generally reflects only a top-down perspective of IT strategy. So, it can be supplemented by a strategic behaviour pattern (i.e., more or less standard response to a changes that is formed as result of previous experience) to implement bottom-up approach. Two components that can help to establish effective reaction regarding new initiatives in IT are proposed here: model of IT-related decision making, and efficiency measurement metric to estimate maturity of business processes and appropriate IT. Usage of proposed tools is demonstrated in practical cases.