Search

This document discusses the importance of optimization in various fields such as statistics, biology, finance, economics, and control. It highlights the advancements made in optimization theory and methods, including first-order methods and augmented Lagrangian methods. The document also introduces a special issue on "Symmetry in Optimization Theory, Algorithms and Applications," which features five papers on topics such as ensemble learning, ant colony system algorithms, subspace algorithms, consensus problems in multi-agent systems, and dynamic conditional correlation models. The authors express their gratitude to the contributors and reviewers of the special issue. [Extracted from the article]

Distributed time-varying formation technology for multi-agent systems is recently become a research hotspot in formation control field. However, the formation reconfiguration control technology for agents that randomly appeared to fail during maneuvers is rarely studied. In this paper, the topological relations between intelligence are designed by graph theory to simplify the cooperative interaction between multi-agent systems. Moreover, this paper constructs the time-varying configuration of the target formation based on the rigidity graph theory and leader–follower strategy. Drawing on the establishment of the expert experience database in a collaborative process, we innovatively propose the establishment of a graphic library to help the multi-agent system quickly form an affine transformation as soon as it is disabled. Secondly, the improved Hungarian algorithm is adopted to allocate the target point when the first failure occurs. This algorithm incorporates a gradient weighting factor from the auction algorithm to improve the speed of system reconfiguration with minimum path cost. On this basis, a distributed multi-agent control law based on consistency theory is established, and the system's stability can be guaranteed via Lyapunov functions. Finally, the simulation results demonstrate the feasibility and effectiveness of the proposed formation reconfiguration control algorithm in a collaborative environment. [ABSTRACT FROM AUTHOR]

The aim of this paper is to develop a method for proving almost sure convergence in the Gromov-Hausdorff-Prokhorov topology for a class of models of growing random graphs that generalises Rémy's algorithm for binary trees. We describe the obtained limits using some iterative gluing construction that generalises the famous line-breaking construction of Aldous' Brownian tree, and we characterize some of them using the self-similarity property in law that they satisfy. To do that, we develop a framework in which a metric space is constructed by gluing smaller metric spaces, called blocks, along the structure of a (possibly infinite) discrete tree. Our growing random graphs seen as metric spaces can be understood in this framework, that is, as evolving blocks glued along a growing discrete tree structure. Their scaling limit convergence can then be obtained by separately proving the almost sure convergence of every block and verifying some relative compactness property for the whole structure. For the particular models that we study, the discrete tree structure behind the construction has the distribution of an affine preferential attachment tree or a weighted recursive tree. We strongly rely on results concerning those two models and their connection, obtained in the companion paper Sénizergues (2021). [ABSTRACT FROM AUTHOR]

Optimal stopping is a fundamental class of stochastic dynamic optimization problems with numerous applications in finance and operations management. In "A nonparametric algorithm for optimal stopping based on robust optimization," the author introduces an approach based on robust optimization for computing near-optimal solutions for computationally demanding stochastic optimal stopping problems with known probability distributions. Through this new use of robust optimization, the paper develops new algorithms for solving stochastic optimal stopping problems that are practical and can outperform state-of-the-art simulation-based algorithms in the context of pricing high-dimensional financial options. Optimal stopping is a fundamental class of stochastic dynamic optimization problems with numerous applications in finance and operations management. We introduce a new approach for solving computationally-demanding stochastic optimal stopping problems with known probability distributions. The approach uses simulation to construct a robust optimization problem that approximates the stochastic optimal stopping problem to any arbitrary accuracy; we then solve the robust optimization problem to obtain near-optimal Markovian stopping rules for the stochastic optimal stopping problem. In this paper, we focus on designing algorithms for solving the robust optimization problems that approximate the stochastic optimal stopping problems. These robust optimization problems are challenging to solve because they require optimizing over the infinite-dimensional space of all Markovian stopping rules. We overcome this challenge by characterizing the structure of optimal Markovian stopping rules for the robust optimization problems. In particular, we show that optimal Markovian stopping rules for the robust optimization problems have a structure that is surprisingly simple and finite-dimensional. We leverage this structure to develop an exact reformulation of the robust optimization problem as a zero-one bilinear program over totally unimodular constraints. We show that the bilinear program can be solved in polynomial time in special cases, establish computational complexity results for general cases, and develop polynomial-time heuristics by relating the bilinear program to the maximal closure problem from graph theory. Numerical experiments demonstrate that our algorithms for solving the robust optimization problems are practical and can outperform state-of-the-art simulation-based algorithms in the context of widely-studied stochastic optimal stopping problems from high-dimensional option pricing. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2023.2461. [ABSTRACT FROM AUTHOR]

For large-scale engineering problems, it has been generally accepted that domain-partitioning algorithms are highly desirable for general-purpose finite element analysis (FEA). This paper presents a heuristic numerical algorithm that can efficiently partition any transportation network (or any finite element mesh) into a specified number of subdomains (usually depending on the number of parallel processors available on a computer), which will result in "minimising the total number of system BOUNDARY nodes" (as a primary criterion) and achieve "balancing work loads" amongst the subdomains (as a secondary criterion). The proposed seven-step heuristic algorithm (with enhancement features) is based on engineering common sense and observation. This current work has the following novelty features: (i) complicated graph theories that are NOT needed and (ii) unified treatments of transportation networks (using line elements) and finite element (FE) meshes (using triangular, tetrahedral, and brick elements) that can be performed through transforming the original network (or FE mesh) into a pseudo-transportation network which only uses line elements. Several examples, including real-life transportation networks and finite element meshes (using triangular/brick/tetrahedral elements) are used (under MATLAB computer environments) to explain, validate and compare the proposed algorithm's performance with the popular METIS software. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we approach a method of clustering binary signature of image in order to create a clustering graph structure for building the content‐based image retrieval. First, the paper presents the segmentation method based on low‐level visual features including colour and texture of image. On the basis of segmented image, the paper creates binary signature to describe location, colour, and shape of interest objects. In order to match similar images, the paper presents a similarity measure between the images based on binary signature. From that, the paper proposes the method of clustering binary signature to quickly query similar images. At the same time, the graph data structure is built using the partition cluster technique and the rules of binary signatures' distribution of images. On the basis of data structure, we propose a graph creation algorithm, a cluster splitting/merging algorithm, and a similarity image retrieval algorithm. To illustrate the proposed theory, we build an image retrieval application and assess the experimental results on the image datasets including COREL (1,000 images), CBIR images (1,344 images), WANG (10,800 images), MSRDI (15,720 images), and ImageCLEF (20,000 images). [ABSTRACT FROM AUTHOR]

In the current era of increasingly complex social life, as people's demand quality is getting higher and higher, the solution of the problem often has multiple indicators to achieve the optimum. This forces the graph coloring problem (GCP) to become complicated, and it is difficult to directly obtain the optimal solution, which brings new challenges to the solution of the problem. In response to this problem, the GCP field is of great research significance. With the in-depth study of GCP, the research on multiobjective optimization (MOO) in graph coloring algorithm (GCA) is gradually carried out. Its performance advantage is of great significance for solving multicondition constraint problems. This paper aims to study the application of Genetic Algorithm (GA) in GCA. Through the analysis and research of GA, and the fusion of numerical analysis and scientific computing, it can be applied to the construction of the neighbor distinguishable uniform V-full coloring algorithm (AVDEVTCA) to solve the AVDEVTC problem. This paper describes the basic theory of MOO and graph coloring. It conducts an experimental analysis of the algorithm performance and uses the relevant theoretical formulas to explain it. The results show that the algorithm takes 5754.142 S seconds to test 21325415 images and can color a large number of results that cannot be done manually in less time. It has greatly improved in terms of time and manpower saving and greatly improved practicability and work efficiency. [ABSTRACT FROM AUTHOR]

We present the algebraic representation and basic algorithms for MultiAspect Graphs (MAGs). A MAG is a structure capable of representing multilayer and time-varying networks, as well as higher-order networks, while also having the property of being isomorphic to a directed graph. In particular, we show that, as a consequence of the properties associated with the MAG structure, a MAG can be represented in matrix form. Moreover, we also show that any possible MAG function (algorithm) can be obtained from this matrix-based representation. This is an important theoretical result since it paves the way for adapting well-known graph algorithms for application in MAGs. We present a set of basic MAG algorithms, constructed from well-known graph algorithms, such as degree computing, Breadth First Search (BFS), and Depth First Search (DFS). These algorithms adapted to the MAG context can be used as primitives for building other more sophisticated MAG algorithms. Therefore, such examples can be seen as guidelines on how to properly derive MAG algorithms from basic algorithms on directed graphs. We also make available Python implementations of all the algorithms presented in this paper. [ABSTRACT FROM AUTHOR]

Fault diagnosis of interconnection networks is vital to ensuring the reliability and maintenance of multiprocessor systems. Based on graph theory, diagnostic algorithms for solving the problem of fault diagnosis in interconnection networks have been widely studied. As the number of processors in multiprocessor systems has increased in recent years, fault diagnosis algorithms based on graph theory cannot meet the current diagnosis requirements of some interconnection networks, such as t-diagnosable systems. In this paper, we use the evolution diagnosis approach to study fault diagnosis in t-diagnosable systems under the PMC model. First, for a t-diagnosable system G with a syndrome σ , we use a simple centralized algorithm to generate its simplified diagnosis graph G f , which contains all the faulty nodes in G. Based on the graph, we prove that the faulty node set in G is the minimum cover set of G f . Next, we prove that the problem of computing the minimum cover set for G f is equivalent to the problem of computing the optimal solution of a zero-one integer program. Using this result, we propose a novel genetic algorithm to solve the problem of the zero-one integer program. The simulation results show that the diagnostic accuracy of our proposed algorithm is equal to or greater than 96% and that the proposed algorithm outperforms its competitors in terms of diagnostic accuracy, number of iterations and running time. [ABSTRACT FROM AUTHOR]

Indoor space information is the basis of indoor location services such as indoor navigation, path planning, emergency evacuation, etc. Focusing on indoor navigation needs, this paper proposes a fast construction algorithm for a complex indoor space topology model based on disjoint set for the problem of lacking polygon description and topological relationship expression of indoor space entity objects in building plan drawings. Firstly, the Tarjan algorithm is used for identifying the hanging edges existing in the indoor space. Secondly, each edge is stored as two different edges belonging to two adjacent polygons that share the edge. A ring structure is introduced to judge the geometric position of walls, and then an efficient disjoint set algorithm is used to perform set merging. After that, disjoint set is queried to obtain all indoor space contours and external boundary contours, thereby the complete indoor space topological relationship at multiple levels is established. Finally, the connectivity theory of graph is used for solving the problem of a complex isolated polygon in topology information generation. The experimental results show that the proposed algorithm has generality to efficiently complete the automatic construction of a topological model for complex scenarios, and effectively acquire and organize indoor space information, thus providing a good spatial cognition mode for indoor navigation. [ABSTRACT FROM AUTHOR]

In graph theory, domination number and its variants such as total domination number are studied by many authors. Let the domination number and the total domination number of a graph G without isolated vertices be γ(G) and γt(G), respectively. Based on the inequality γt(G) ≤ 2γ(G), we investigate the graphs satisfying the upper bound, that is, graphs G with γt(G) = 2γ(G). In this paper, we present some new properties of such graphs and provide an algorithm which can determine whether γt(G) = 2γ(G) or not for a family of graphs not covered by the previous results in the literature. [ABSTRACT FROM AUTHOR]

Phylogenetic networks generalize phylogenetic trees by allowing the modelization of events of reticulate evolution. Among the different kinds of phylogenetic networks that have been proposed in the literature, the subclass of binary tree-child networks is one of the most studied ones. However, very little is known about the combinatorial structure of these networks. In this paper we address the problem of generating all possible binary tree-child (BTC) networks with a given number of leaves in an efficient way via reduction/augmentation operations that extend and generalize analogous operations for phylogenetic trees, and are biologically relevant. Since our solution is recursive, this also provides us with a recurrence relation giving an upper bound on the number of such networks. We also show how the operations introduced in this paper can be employed to extend the evolutive history of a set of sequences, represented by a BTC network, to include a new sequence. An implementation in python of the algorithms described in this paper, along with some computational experiments, can be downloaded from . [ABSTRACT FROM AUTHOR]

Energy recharging has received much attention now because of the development of wireless recharging technology. This paper proposes a greedy constructing tree algorithm for shortest path in perpetual wireless recharging wireless sensor networks (GCTA) which enables the recharger to work while moving through the shortest path. The algorithm can construct the shorter path which passes all the sensors only once and guarantees that each sensor will be fully recharged. It computes the path in advance with lower complexity. And it also uses the graph theory, the tree theory, the Markov chain theorem and the powerful computing function of a computer. The contributions of the paper are itemized as follows: guaranteeing all the sensors to be fully recharged only once and reducing the length of the recharging path through constructing the greedy tree. In the experiment, this algorithm can construct the shorter path. So it is novel, general and can be applied widely. [ABSTRACT FROM AUTHOR]

As a tool of qualitative representation, conditional preference network (CP-net) has recently become a hot research topic in the field of artificial intelligence. The semantics of CP-nets does not restrict the generation of cycles, but the existence of the cycles would affect the property of CP-nets such as satisfaction and consistency. This paper attempts to use the feedback set problem theory including feedback vertex set (FVS) and feedback arc set (FAS) to cut cycles in CP-nets. Because of great time complexity of the problem in general, this paper defines a class of the parent vertices in a ring CP-nets firstly and then gives corresponding algorithm, respectively, based on FVS and FAS. Finally, the experiment shows that the running time and the expressive ability of the two methods are compared. [ABSTRACT FROM AUTHOR]

Broadcasting is disseminating information in a network where a specific message must spread to all network vertices as quickly as possible. Finding the minimum broadcast time of a vertex in an arbitrary network is proven to be NP-complete. However, this problem is solvable for a few families of networks. In this paper, we present an optimal algorithm for finding the broadcast time of any vertex in a fully connected tree ( FCT n ) in O (| V | log log n) time. An FCT n is formed by attaching arbitrary trees to vertices of a complete graph of size n where | V | is the total number of vertices in the graph. [ABSTRACT FROM AUTHOR]

Damage detection through an inverse optimization problem has been investigated by many researchers. Recently, Modal Strain Energy (MSE) has been utilized as an index (MSEBI) for damage localization that serves to guide the optimization. This guided approach considerably reduces the computational cost and increases the accuracy of optimization. Although this index mostly exhibits an acceptable performance, it fails to find some damaged elements' locations in some cases. The aim of this paper is twofold. Firstly, a Graph-based Adaptive Threshold (GAT) is proposed to identify some of those elements that are not detected by basic MSEBI. GAT relies on the concepts from graph theory and MSE working as a simple anomaly detection technique. Secondly, an Improved version of the Water Strider Algorithm (IWSA) is introduced, applied to the damage detection problems with incomplete modal data and noisecontaminated inputs. Several optimization algorithms, including the newly-established Water Strider Algorithm (WSA), are utilized to test the proposed method. The investigations on several damage detection problems demonstrate the GAT and IWSA's satisfactory performance compared to the previous methods. [ABSTRACT FROM AUTHOR]

The history of infections and epidemics holds famous examples where understanding, containing, and ultimately treating an outbreak began with understanding its mode of spread. Influenza, HIV, and most computer viruses spread person to person, device to device, and through contact networks; Cholera, Cancer, and seasonal allergies, on the other hand, do not. In this paper, we study two fundamental questions of detection. First, given a snapshot view of a (perhaps vanishingly small) fraction of those infected, under what conditions is an epidemic spreading via contact (e.g., Influenza), distinguishable from a random illness operating independently of any contact network (e.g., seasonal allergies)? Second, if we do have an epidemic, under what conditions is it possible to determine which network of interactions is the main cause of the spread—the causative network—without any knowledge of the epidemic, other than the identity of a minuscule subsample of infected nodes? The core, therefore, of this paper, is to obtain an understanding of the diagnostic power of network information. We derive sufficient conditions that networks must satisfy for these problems to be identifiable, and produce efficient, highly scalable algorithms that solve these problems. We show that the identifiability condition we give is fairly mild, and in particular, is satisfied by two common graph topologies: the $d$ -dimensional grid, and the Erdös-Renyi graphs. [ABSTRACT FROM AUTHOR]

Let k 1 be an integer, and let G be a finite and simple graph with vertex set V (G). A signed total Italian k-dominating function on a graph G is a function f: V (G) ! f1; 1; 2g such that P u2N(v) f(u) ≥ k for every v 2 V (G), where N(v) is the neighborhood of v, and each vertex u with f(u) = 1 is adjacent to a vertex v with f(v) = 2 or to two vertices w and z with f(w) = f(z) = 1. A set ff1; f2;: ::; fdg of distinct signed total Italian k-dominating functions on G with the property that Pd i=1 fi(v) ≤ k for each v 2 V (G), is called a signed total Italian k-dominating family (of functions) on G. The maximum number of functions in a signed total Italian k-dominating family on G is the signed total Italian k-domatic number of G, denoted by dk stI (G). In this paper we initiate the study of signed total Italian k-domatic numbers in graphs, and we present sharp bounds for dk stI (G). In addition, we determine the signed total Italian k-domatic number of some graphs. [ABSTRACT FROM AUTHOR]

The paper presents a novel 2D geometrical path plan algorithm that reduces calculation load and time by filtering obstacles before path planning starts by the newly introduced hexagon filter and also while path search is in progress. Unlike other methods that use only obstacle filtering before path planning starts. The suggested algorithm was able to solve a randomly created maze that contains 400 obstacles with 800 nodes, which was considered before, as next to impossible to solve. This is because computational time is proportional to n2log(n) where n is the number of obstacles, node suggested algorithm reduced the computational time to about 1 in 2500 times compared to the best of (ESOVG, DVG or ECoVG). In addition, the suggested algorithm can be used in the case of a fixed start point and different target points (e.g. a swarm of robots leaving from the same start point with different targets). [ABSTRACT FROM AUTHOR]

The self-replication introduced by John von Neumann is a process that produces a copy of itself. As a novel approach, this paper studies the self-replication process through the process of reproduction. In this paper, we propose a comprehensive graph reproduction system (GRS) and identify a specific reproduction system that turns out to be a graph self-replication system (GSS), with which a copy of any given graph can be produced through an algorithmic process. Unlike the GRS studied by Richard Southwell, our model considers the evolution of edges along with the evolution of vertices. We analyze some of the existing reproduction models through our system and identify the models that are self-replicable. [ABSTRACT FROM AUTHOR]

In this paper, we consider the mixture of sparse linear regressions model. Let $\boldsymbol {\beta }^{(1)},\ldots, \boldsymbol {\beta }^{(L)}\in \mathbb {C} ^{n}$ be $L $ unknown sparse parameter vectors with a total of $K $ non-zero elements. Noisy linear measurements are obtained in the form $y_{i} = \boldsymbol {x}_{i} ^{\mathrm{ H}} \boldsymbol {\beta }^{(\ell _{i})} + w_{i}$ , each of which is generated randomly from one of the sparse vectors with the label $\ell _{i} $ unknown. The goal is to estimate the parameter vectors efficiently with low sample and computational costs. This problem presents significant challenges as one needs to simultaneously solve the demixing problem of recovering the labels $\ell _{i} $ as well as the estimation problem of recovering the sparse vectors $\boldsymbol {\beta }^{(\ell)} $. Our solution to the problem leverages the connection between modern coding theory and statistical inference. We introduce a new algorithm, Mixed-Coloring, which samples the mixture strategically using query vectors $\boldsymbol {x}_{i} $ constructed based on ideas from sparse graph codes. Our novel code design allows for both efficient demixing and parameter estimation. To find $K$ non-zero elements, it is clear that we need at least $\Theta (K)$ measurements, and thus the time complexity is at least $\Theta (K)$. In the noiseless setting, for a constant number of sparse parameter vectors, our algorithm achieves the order-optimal sample and time complexities of $\Theta (K)$. In the presence of Gaussian noise, for the problem with two parameter vectors (i.e., $L = 2$), we show that the Robust Mixed-Coloring algorithm achieves near-optimal $\Theta (K \mathop {\mathrm {polylog}}\nolimits (n))$ sample and time complexities. When $K = \mathcal {O}(n^{\alpha })$ for some constant $\alpha \in (0,1)$ (i.e., $K$ is sublinear in $n$), we can achieve sample and time complexities both sublinear in the ambient dimension. In one of our experiments, to recover a mixture of two regressions with dimension $n = 500$ and sparsity $K = 50$ , our algorithm is more than 300 times faster than EM algorithm, with about one third of its sample cost. 1 The proposed algorithm works even when the noise is non-Gaussian in nature, but the guarantees on sample and time complexities are difficult to obtain. [ABSTRACT FROM AUTHOR]

Simultaneous localization and planning (SLAP) is a crucial ability for an autonomous robot operating under uncertainty. In its most general form, SLAP induces a continuous partially observable Markov decision process (POMDP), which needs to be repeatedly solved online. This paper addresses this problem and proposes a dynamic replanning scheme in belief space. The underlying POMDP, which is continuous in state, action, and observation space, is approximated offline via sampling-based methods, but operates in a replanning loop online to admit local improvements to the coarse offline policy. This construct enables the proposed method to combat changing environments and large localization errors, even when the change alters the homotopy class of the optimal trajectory. It further outperforms the state-of-the-art Feedback-based Information RoadMap (FIRM) method by eliminating unnecessary stabilization steps. Applying belief space planning to physical systems brings with it a plethora of challenges. A key focus of this paper is to implement the proposed planner on a physical robot and show the SLAP solution performance under uncertainty, in changing environments and in the presence of large disturbances, such as a kidnapped robot situation. [ABSTRACT FROM AUTHOR]

Since 1997 a considerable effort has been spent on the study of the swap (switch) Markov chains on graphic degree sequences. All of these results assume some kind of regularity in the corresponding degree sequences. Recently, Greenhill and Sfragara published a breakthrough paper about irregular normal and directed degree sequences for which rapid mixing of the swap Markov chain is proved. In this paper we present two groups of results. An example from the first group is the following theorem: let be a directed degree sequence on n vertices. Denote by Δ the maximum value among all in- and out-degrees and denote by the number of edges in the realization. Assume furthermore that . Then the swap Markov chain on the realizations of is rapidly mixing. This result is a slight improvement on one of the results of Greenhill and Sfragara. An example from the second group is the following: let d be a bipartite degree sequence on the vertex set U ⊎ V, and let 0 < c1 ≤ c2 < |U| and 0 < d1 ≤ d2 < |V| be integers, where c1 ≤ d(v) ≤ c2: ∀v ∈ V and d1 ≤ d(u) ≤ d2: ∀u ∈ U. Furthermore assume that (c2 − c1 − 1)(d2 − d1 − 1) < max{c1(|V| − d2), d1(|U| − c2)}. Then the swap Markov chain on the realizations of d is rapidly mixing. A straightforward application of this latter result shows that when a random bipartite or directed graph is generated under the Erdős—Rényi G(n, p) model with mild assumptions on n and p then the degree sequence of the generated graph has, with high probability, a rapidly mixing swap Markov chain on its realizations. [ABSTRACT FROM AUTHOR]

The Graph Coloring Problem is a well-known NP-hard problem. Over the years, numerous scholars have been pursuing efficient algorithms to obtain high-quality solutions. Nested Rollout Policy Adaptation (NRPA) is a Monte Carlo Tree Search algorithm for single-player games, and it has been proven effective and good in combinatorial optimization problems. In this paper, we use for the first time the NRPA algorithm combined with the destruction and reconstruction ideas of the Iterative Greedy algorithm to solve the Graph Coloring Problem. First, the basic principle of the NRPA algorithm is introduced. Then, NRPA is extended by using mixed sorting, destruction and reconstruction, and the Diversity-NRPA algorithm is proposed, which improves the diversity of the algorithm. Finally, Diversity-NRPA is applied to solve the Graph Coloring Problem by combining it with the knowledge of the graph theory field. We evaluate the performance of Diversity-NRPA on DIMACS, a well-known graph benchmark instance, and compare it with traditional graph coloring algorithms. The experimental results show that the Diversity-NRPA algorithm can achieve excellent performance in both solution quality and search efficiency in solving the Graph Coloring problem. [ABSTRACT FROM AUTHOR]

The problem of completing a large low rank matrix using a subset of revealed entries has received much attention in the last ten years. The main result of this paper gives a necessary and sufficient condition, stated in the language of graph limit theory, for a sequence of matrix completion problems with arbitrary missing patterns to be asymptotically solvable. It is then shown that a small modification of the Candès–Recht nuclear norm minimization algorithm provides the required asymptotic solution whenever the sequence of problems is asymptotically solvable. The theory is fully deterministic, with no assumption of randomness. A number of open questions are listed. [ABSTRACT FROM AUTHOR]

This paper investigates subchannel allocation based on clustered interference alignment in dense small cell networks when all small cell user equipments (SUEs) have differentiated requirements for data streams. By imposing the condition that each cluster has a size not exceeding the maximum value achieved when each SUE needs only one data stream, we maximize the number of SUEs with guaranteed requirements for data streams, which is NP-hard. Hence, we propose a two-phase efficient solution with much lower complexity and reduced feedback overhead. First, similarity clustering is performed by graph partition, and then, subchannel allocation is done through a coloring algorithm. Numerical results show that the proposed solution offers a performance better than the related schemes and close to the approximate optimal solution. [ABSTRACT FROM AUTHOR]

Growing ramification in WSN contemplations are not restricted to routing, construction of protocols, dynamic of mobile nodes and infrastructure of the network. Although transcended to geometric level demonstrated as computational and dynamical geometries in spite of graph theory. In this paper we present step forward recognition features of a network devoted to solve the problem of reconstructing the disconnected network by connecting any disconnected chains. It considers geometrical properties of random depletion nodes deviated from unit grid. Number of chains and number of nodes in each chain are calculated with the average number of connections to a total nodes and longest chain. Histogram represented number of chains and numbers of nodes for each chain are used to show fragmentation of the network. Algorithm included a method to translate adjacent matrix to chain matrix and vice versa to check the agreement of initial case with the results. The amount of chain deviation and average connections per node for longest connected chain and for the total network are drawn as bar charts and conduct interpretations. [ABSTRACT FROM AUTHOR]

This paper proposes a local search algorithm for a specific combinatorial optimisation problem in graph theory: the Hamiltonian completion problem (HCP) on undirected graphs. In this problem, the objective is to add as few edges as possible to a given undirected graph in order to obtain a Hamiltonian graph. This problem has mainly been studied in the context of various specific kinds of undirected graphs (e.g. trees, unicyclic graphs and series-parallel graphs). The proposed algorithm, however, concentrates on solving HCP for general undirected graphs. It can be considered to belong to the category of matheuristics, because it integrates an exact linear time solution for trees into a local search algorithm for general graphs. This integration makes use of the close relation between HCP and the minimum path partition problem, which makes the algorithm equally useful for solving the latter problem. Furthermore, a benchmark set of problem instances is constructed for demonstrating the quality of the proposed algorithm. A comparison with state-of-the-art solvers indicates that the proposed algorithm is able to achieve high-quality results. [ABSTRACT FROM AUTHOR]

Introduces the papers presented in the February 2001 issue of `Information Theory' journal, about codes, graphs and iterative algorithms. Problems that motivate all the papers in the issue; Authors of the paper on graphical representations and algorithms; Papers on iterative algorithms.

Isomap is a well‐known nonlinear dimensionality reduction method that highly suffers from computational complexity. Its computational complexity mainly arises from two stages; a) embedding a full graph on the data in the ambient space, and b) a complete eigenvalue decomposition. Although the reduction of the computational complexity of the graphing stage has been investigated by graph processing methods, the eigenvalue decomposition stage remains a bottleneck in the problem. In this paper, we propose the Low‐Rank Isomap (LRI) algorithm by introducing a projection operator on the embedded graph from the ambient space to a low‐rank latent space to facilitate applying the partial eigenvalue decomposition. This approach leads to reducing the complexity of Isomap to a linear order while preserving the structural information during the dimensionality reduction process as long as the number of observations remains extensively larger than the dimensionality of the ambient space. The superiority of the LRI algorithm compared to some state‐of‐art algorithms is experimentally verified on facial image clustering in terms of speed and accuracy. [ABSTRACT FROM AUTHOR]

In data aggregation networks (WSNs, ad hoc, mesh, etc.), it is key to schedule the network resources, such as channels and TDMA time slots, to minimize the communication conflict and optimize the network data-gathering performance. In this paper, the resources scheduling problem is formulated as a vertex coloring problem in graph theory. Then, a multi-channel TDMA scheduling algorithm based on the Gibbs optimization is proposed. By defining the Gibbs energy expression according to the objective function of the problem, the joint probability of channel and time slot can be computed for the optimized selection of channels and time slots. This algorithm is low-complexity and its convergence performance can be proven. Experiments with different network parameters demonstrate that the proposed algorithm can reduce the communication conflict, improve the network throughput, and effectively reduce the network transmission delay and scheduling length for the data aggregation networks. [ABSTRACT FROM AUTHOR]

This paper studies the 2D localization problem of a sensor network given anchor node positions in a common global coordinate frame and relative position measurements in local coordinate frames between node pairs. It is assumed that the local coordinate frames of different sensors have different orientations and the orientation difference with respect to the global coordinate frame are not known. In terms of graph connectivity, a necessary and sufficient condition is obtained for self-localizability that leads to a fully distributed localization algorithm. Moreover, a distributed verification algorithm is developed to check the graph connectivity condition, which can terminate successfully when the sensor network is self-localizable. Finally, a fully distributed, linear, and iterative algorithm based on the complex-valued Laplacian associated with the sensor network is proposed, which converges globally and gives the correct localization result. [ABSTRACT FROM PUBLISHER]

Graph cuts are widely used in computer vision. To speed up the optimization process and improve the scalability for large graphs, Strandmark and Kahl introduced a splitting method to split a graph into multiple subgraphs for parallel computation in both shared and distributed memory models. However, this parallel algorithm (the parallel BK-algorithm) does not have a polynomial bound on the number of iterations and is found to be non-convergent in some cases due to the possible multiple optimal solutions of its sub-problems. To remedy this non-convergence problem, in this paper, we first introduce a merging method capable of merging any number of those adjacent sub-graphs that can hardly reach agreement on their overlapping regions in the parallel BK-algorithm. Based on the pseudo-boolean representations of graph cuts, our merging method is shown to be effectively reused all the computed flows in these sub-graphs. Through both splitting and merging, we further propose a dynamic parallel and distributed graph cuts algorithm with guaranteed convergence to the globally optimal solutions within a predefined number of iterations. In essence, this paper provides a general framework to allow more sophisticated splitting and merging strategies to be employed to further boost performance. Our dynamic parallel algorithm is validated with extensive experimental results. [ABSTRACT FROM PUBLISHER]

Euler path is one of the most interesting and widely discussed topics in graph theory. An Euler path (or Euler trail) is a path that visits every edge of a graph exactly once. Similarly, an Euler circuit (or Euler cycle) is an Euler trail that starts and ends on the same node of a graph. A graph having Euler path is called Euler graph. While tracing Euler graph, one may halt at arbitrary nodes while some of its edges left unvisited. In this paper, we have proposed some precautionary steps that should be considered in exploring a deadlock-free Euler path, i.e., without being halted at any node. Simulation results show that our proposed approach improves the process of exploring the Euler path in an undirected connected graph without interruption. Furthermore, our proposed algorithm is complete for all types of undirected Eulerian graphs. The paper concludes with the proofs of the correctness of proposed algorithm and its computation complexity. [ABSTRACT FROM AUTHOR]

Ensuring reliable operation of large power systems subjected to multiple outages is a challenging task because of the combinatorial nature of the problem. Traditional approaches for security assessment are often limited by their scope and/or speed, resulting in missing of critical contingencies that could lead to cascading failures. This paper proposes a two-component methodology to enhance power system security. The first component combines an efficient algorithm to detect cut-set saturation (called the feasibility test (FT) algorithm) with real-time contingency analysis (RTCA) to create an integrated corrective action (iCA), whose goal is to secure the system against cut-set saturation as well as critical branch overloads. The second component only employs the results of the FT to create a relaxed corrective action (rCA) to secure the system against post-contingency cut-set saturation. The first component is more comprehensive, but the latter is computationally more efficient. The effectiveness of the two components is evaluated based upon the number of cascade triggering contingencies alleviated, and the computation time. The results obtained by analyzing different case-studies on the IEEE 118-bus and 2000-bus synthetic Texas systems indicate that the proposed two-component methodology successfully enhances the scope and speed of power system security assessment during multiple outages. [ABSTRACT FROM AUTHOR]

Phase balancing of American-type three-phase distribution circuits is one of the classical problems faced by distribution system operators and planners. In this paper, a mixed-integer non-linear programming problem is formulated to minimize the number of phase connection changes in existing circuits to reach the desired phase balancing. The proposed algorithm uses geographical information system models of distribution circuits to build a reduced model and realistic load profiles offered by smart meters, or measurements at the distribution transformers to characterize the demand. The formulation is validated in highly unbalanced distribution circuits with thousands of single-phase customers. The results show that it is possible to rebalance large-scale circuits by moving a few single-phase laterals and loads. In addition, the application of the proposed method, based on loading conditions at different hours of the day, pointed out the same places to make the changes. [ABSTRACT FROM AUTHOR]

This paper investigates algorithmic properties and overall performance of the exact auction algorithm in Demange, Gale and Sotomayor (J. Polit. Economy 94: 863-872, 1986) or DGS for short. This task is achieved by interpreting DGS as a graph and by conducting a large number of computer simulations. The crucial step in DGS is when the auctioneer selects a so-called minimal overdemanded set of items because the specific selection may affect a number of performance measures such as the number of iterations and the ratio of elicited preferences. The computational results show that (i) DGS graphs are typically large even for relatively small numbers of bidders and items, (ii) DGS converges slowly and (iii) DGS performs well in terms of preference elicitation. The paper also demonstrates that the modification to DGS based on the Ford-Fulkerson algorithm outperforms all investigated rules for selecting a minimal overdemanded set of items in DGS both in terms of termination speed and preference elicitation. [ABSTRACT FROM AUTHOR]

A subset S Ç V in a graph G = (V, E) is called a [1, k]-set, if for every vertex v 6 V\S, 1 < |NG(v) nS| < k. The [1, k]-domination number of G, denoted by Y[i,k](G) is the size of the smallest [1,k]-sets of G. A set S' Ç V (G) is called a total [1,k]-set, if for every vertex v e v, 1 < |.ezG(v) ns| $\ k. If a {graph G has at least one total [1, k]-set then the cardinality of the smallest such setz is denoted by Yt[1,k](G). In this paper, we investigate the existence of [1,k]-sets in lexicographic products Go Ti. Furthermore, we completely characterize graphs whose lexicographic product lias £it leaet one total [1,k]-set. Finally, we show that finding smallest total [1, k]-set is an NP-complete problem. [ABSTRACT FROM AUTHOR]

We use the Katona-Kierstead definition of a Hamiltonian cycle in a uniform hypergraph. A decomposition of complete fc-uniform hypergraph Knkinto Hamiltonian cycles was studied by Bailey-Stevens and Meszka-Rosa. For n = 2,4, 5 (mod 6), we design an algorithm for decomposing the complete 3-uniform hypergraphs into Hamiltonian cycles by using the method of edge-partition. A decomposition of Kn³ into 5-cycles has been presented for all admissible n ≤ 17, and for all n = 4m + 1 when m is a positive integer. In general, the existence of a decomposition into 5-cycles remains open. In this paper, we show if 42 Ι (n - 1)(n- 2) and if there exist λ = (n-1)(n-2)/42 sequences (ki0,ki1,...,ki6) on Dall(n), then Kn(³) can be decomposed into 7-cycles. We use the method of edge-partition and cycle sequence. We find a decomposition of K37(³) and K43(³ ) into 7-cycles. [ABSTRACT FROM AUTHOR]

This paper provides performance bounds for compressed sensing in the presence of Poisson noise using expander graphs. The Poisson noise model is appropriate for a variety of applications, including low-light imaging and digital streaming, where the signal-independent and/or bounded noise models used in the compressed sensing literature are no longer applicable. In this paper, we develop a novel sensing paradigm based on expander graphs and propose a maximum a posteriori (MAP) algorithm for recovering sparse or compressible signals from Poisson observations. The geometry of the expander graphs and the positivity of the corresponding sensing matrices play a crucial role in establishing the bounds on the signal reconstruction error of the proposed algorithm. We support our results with experimental demonstrations of reconstructing average packet arrival rates and instantaneous packet counts at a router in a communication network, where the arrivals of packets in each flow follow a Poisson process. [ABSTRACT FROM AUTHOR]