Search

A matching in a bipartite graph with parts X and Y is called envy-free, if no unmatched vertex in X is a adjacent to a matched vertex in Y. Every perfect matching is envy-free, but envy-free matchings exist even when perfect matchings do not. We prove that every bipartite graph has a unique partition such that all envy-free matchings are contained in one of the partition sets. Using this structural theorem, we provide a polynomial-time algorithm for finding an envy-free matching of maximum cardinality. For edge-weighted bipartite graphs, we provide a polynomial-time algorithm for finding a maximum-cardinality envy-free matching of minimum total weight. We show how envy-free matchings can be used in various fair division problems with either continuous resources ("cakes") or discrete ones. In particular, we propose a symmetric algorithm for proportional cake-cutting, an algorithm for 1 -out-of- (2 n - 2) maximin-share allocation of discrete goods, and an algorithm for 1 -out-of- ⌊ 2 n / 3 ⌋ maximin-share allocation of discrete bads among n agents. [ABSTRACT FROM AUTHOR]

A fundamental quest in the theory of computing is to understand the power of randomness. It is not known whether every problem with an efficient randomized algorithm also has one that does not use randomness. One of the extensively studied problems under this theme is that of perfect matching. The perfect matching problem has a randomized parallel (NC) algorithm based on the Isolation Lemma of Mulmuley, Vazirani, and Vazirani. It is a long-standing open question whether this algorithm can be derandomized. In this article, we give an almost complete derandomization of the Isolation Lemma for perfect matchings in bipartite graphs. This gives us a deterministic parallel (quasi-NC) algorithm for the bipartite perfect matching problem. Derandomization of the Isolation Lemma means that we deterministically construct a weight assignment so that the minimum weight perfect matching is unique. We present three different ways of doing this construction with a common main idea. [ABSTRACT FROM AUTHOR]

In multi-label learning, label enhancement (LE) aims to recover label distributions from logical labels, thereby reinforcing supervision information in the training set. Existing LE algorithms mainly leverage pairwise similarities between instances to recover label distributions. However, symmetric similarities, which are widely used, are incapable of reflecting individual differences between instances. In this paper, we propose an asymmetric influence between instances to fully explore the information contained in logical labels. First, we build a bipartite network and employ the mass diffusion algorithm on it to calculate the asymmetric influence between instances. Such asymmetry distinguishes the influence of an instance on others from the influence it receives from others. Second, to cope with the new influence, we construct a graph with self-connections. In this way, we allow instances to be influenced by themselves. Extensive experiments on thirteen benchmark datasets demonstrate the superiority of the proposed method over six state-of-the-art LE algorithms. • We exploit asymmetric influence between instances when label enhancement. • This asymmetry distinguishes individual differences to better exploit the correlation between instances. • Results validate its effectiveness in comparison with several state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

For online service platforms such as Netflix, it is important to propose a list of high quality movies to their users. This type of problem can be regarded as a ranking problem in a bipartite network. This is a well-known problem, that can be solved by a ranking algorithm. However, many classical ranking algorithms share a common drawback: they tend to rank higher older movies rather than newer ones, though some new movies may be of higher quality. In the study, we develop a ranking method using a rebalance approach to decrease the time bias of the rankings in bipartite graphs. We then conduct experiments on three real datasets with ground truth benchmark. The results show that our proposed method not only reduces the time bias of the ranking scores, but also improves the prediction accuracy by at least 20%, and up to 80%. [ABSTRACT FROM AUTHOR]

The traditional projection models in the bipartite networks involve many node pairs that consist of weak relationships. These node pairs lead to poor quality predictions as well as high computation time. In this paper, to cope with these problems, we firstly propose a novel projection model, which is called "Strengthened Projection Model". Then, to predict the potential links in the future, we present a new link prediction approach based on the proposed projection model. Thanks to the proposed model, the computation time is shortened, and the high probability predictions are extracted. The majority of the previous works conducted in this area have used the classical proximity measure algorithms that only take into account the current network structure, regardless of when events occur in the network evolution. To overcome these limited methods, in this paper, we also propose a novel proximity measure algorithm that considers the bipartite network evolution. To the best of our knowledge, this is the first attempt that takes into account the time-awareness in bipartite networks. To evaluate the performance of our proposed approach, we conducted experiments on the academic information network. To construct this bipartite network, we collected data from IEEE Xplore. The experimental results show that the success of the proposed method is promising. [ABSTRACT FROM AUTHOR]

This paper describes efficient new heuristic methods to color the vertices of a graph which rely upon the comparison of the degrees and structure of a graph. A method is developed which is exact for bipartite graphs and is an important part of heuristic procedures to find maximal cliques in general graphs. Finally an exact method is given which performs better than the Randall-Brown algorithm and is able to color larger graphs, and the new heuristic methods, the classical methods, and the exact method are compared. [ABSTRACT FROM AUTHOR]

Data clustering is a fundamental problem in the field of machine learning. Among the numerous clustering techniques, matrix factorization-based methods have achieved impressive performances because they are able to provide a compact and interpretable representation of the input data. However, most of the existing works assume that each class has a global centroid, which does not hold for data with complicated structures. Besides, they cannot guarantee that the sample is associated with the nearest centroid. In this work, we present a concept factorization with the local centroids (CFLCs) approach for data clustering. The proposed model has the following advantages: 1) the samples from the same class are allowed to connect with multiple local centroids such that the manifold structure is captured; 2) the pairwise relationship between the samples and centroids is modeled to produce a reasonable label assignment; and 3) the clustering problem is formulated as a bipartite graph partitioning task, and an efficient algorithm is designed for optimization. Experiments on several data sets validate the effectiveness of the CFLC model and demonstrate its superior performance over the state of the arts. [ABSTRACT FROM AUTHOR]

The article presents an introduction to a paper regarding a deterministic parallel algorithm for bipartite matching.

An algorithm for link prediction in a bipartite network is presented. In the algorithm, we first map the bipartite network onto a unipartite network called a projected graph. Based on the projected graph, we define the concept of a candidate node pair (CNP). We perform link prediction only within the CNPs to reduce the computation time. We also define the patterns covered by the CNPs and weights of the patterns. By calculating the weights of the patterns that a CNP covers, the connectivity of the CNP can be obtained, which can be used as the final score of link prediction. For a bipartite network with n and m nodes in the two parts, the time complexity of the proposed algorithm is O( m ), whereas those of other algorithms are O( mn ) or O(( m + n ) 3 ). The experimental results show that our algorithm can achieve higher speed and superior quality link prediction results in bipartite networks compared with other methods. [ABSTRACT FROM AUTHOR]

This paper aims at solving the bipartite containment problem for linear singular multi-agent systems (MASs) with multiple dynamic leaders over general signed digraphs, where each leader can be autonomous or dynamically evolving via interactions with its neighboring leaders. To this end, we first establish some properties for the Laplacian matrices of signed digraphs. Then, three distributed observer-based bipartite containment protocols are proposed using different local output information. Multi-step algorithms for constructing the corresponding proposed protocols are also given. It is shown that under the proposed control protocols, bipartite containment can be achieved for any admissible initial states provided that the underlying signed digraph is weakly connected. Compared to the existing related works, the major contribution of present work is that the developed results are applicable for arbitrary weakly connected signed digraphs, no matter whether they are sign-symmetric or sign-asymmetric and whether they are structurally balanced or unbalanced. Two numerical examples are finally given to demonstrate the validity of our results. [ABSTRACT FROM AUTHOR]

Abstract: Many multi-class classification algorithms in statistics and machine learning typically combine several binary classifiers in order to construct an overall classifier. In the popular pairwise ensemble, one classifier is built for each pair of classes, resulting in pairwise bipartite rankings. In contrast, ordinal regression algorithms consider a single ranking function for several ordered classes. It is known in the literature that pairwise ensembles can be useful for ordinal regression. However, can single ranking models make a contribution to multi-class classification? The answer to this question should be affirmative, as supported by theoretical results presented in this article. We conduct a formal analysis of the consistency of pairwise bipartite rankings by uncovering the conditions under which they can be equivalently expressed in terms of a single ranking. Similar to the utility representability of pairwise preference relations, it turns out that transitivity plays a crucial role in the characterization of the ranking representability of pairwise bipartite rankings. To this end, we introduce the new concepts of strict ranking representability, a restrictive condition that can be verified easily, and AUC ranking representability, a practically more useful condition that is more difficult to verify. However, the link between pairwise bipartite rankings and dice games allows us to formulate necessary transitivity conditions for AUC ranking representability. A sufficient condition on the other hand is obtained by introducing a new type of transitivity that can be verified by solving an integer quadratic program. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we introduce the incremental assignment problem. In this problem, a new pair of vertices and their incident edges are added to a weighted bipartite graph whose maximum-weighted matching is already known, and the maximum-weighted matching of the extended graph is sought. We propose an algorithm for the problem. [Copyright &y& Elsevier]

• We analytically derive the structure entropy, which is equivalent to the compression limit, for arbitrary random bipartite networks without node labeling. • We theoretically show that the compression length of random bipartite networks resulted from the compression algorithm, BSZIP, asymptotically achieves the theoretical limit. • The compression algorithm BSZIP for random bipartite networks outperforms the majority of compression algorithms in existence from perspectives including the encoding length and the computational time. Bipartite network is crucial for recommendation systems as user-product behaviors are thoroughly described by bipartite interactions. Almost all of the state-of-the-art network compression algorithms are designed for general networks without harnessing the unique bipartite structure. Until 2017, Basu and Varshney proposed a compression algorithm, BSZIP , selectively for bipartite networks. However, the performance of this algorithm is not clear. Here, we derive the structural entropy which is equivalent to the compression limit for unlabeled random bipartite networks. Theoretically, we show that BSZIP algorithm asymptotically achieves the analytical limit. [ABSTRACT FROM AUTHOR]

Let G(V,E,W) denote a graph with vertex-set V and edge-set E, and each vertex v is associated with a cost W(v). For any set V′⊆V, the bottleneck cost of V′ is defined as max{W(x)|x∈V′}. This paper considers the bottleneck independent dominating set problem (the BIDS problem) which determines an independent dominating set of G such that its bottleneck cost is minimized.This paper studies the problem on the classes of bipartite graphs and block graphs. This paper first proves that the problem is NP-hard on chordal-bipartite graphs. Second, a linear-time algorithm on convex-bipartite graphs is proposed. Next, a linear-time algorithm on trees is designed. Then, we generalize the algorithmic result to block graphs. All algorithms are designed by the dynamic programming strategy. [Copyright &y& Elsevier]

We present new results on the synthesis of safe, non-blocking, and maximally permissive supervisors for partially observed discrete event systems. We consider the case where the legal language is a non-prefix-closed sublanguage of the system language, i.e., non-blockingness must be ensured in addition to safety. To solve this problem, we define a new bipartite transition system, called the Non-blocking All Inclusive Controller (NB-AIC), that embeds all safe and non-blocking supervisors. We present an algorithm for the construction of the NB-AIC and discuss its properties. We obtain the necessary and sufficient conditions for the solvability of the maximally permissive control problem. We then provide a synthesis algorithm, based on the NB-AIC, that constructs a supervisor that is safe, non-blocking and maximally permissive, if one exists. This is the first algorithm with such properties. [ABSTRACT FROM AUTHOR]

We present a novel framework for answering complex questions that relies on question decomposition. Complex questions are decomposed by a procedure that operates on a Markov chain, by following a random walk on a bipartite graph of relations established between concepts related to the topic of a complex question and subquestions derived from topic-relevant passages that manifest these relations. Decomposed questions discovered during this random walk are then submitted to a state-of-the-art Question Answering (Q/A) system in order to retrieve a set of passages that can later be merged into a comprehensive answer by a Multi-Document Summarization (MDS) system. In our evaluations, we show that access to the decompositions generated using this method can significantly enhance the relevance and comprehensiveness of summary length answers to complex questions. [ABSTRACT FROM AUTHOR]

Community detection in complex networks is a topic of high interest in many scientific fields. A bipartite network is a special type of complex network whose nodes are decomposed into two disjoint sets such that no two nodes within the same set are adjacent. Many relationships in real-world systems can be represented by a bipartite network, such as predator-prey relationships, plant-pollinator interactions, and drug-target interactions. While community detection in unipartite networks has been extensively studied in the past decade, identification of modules or communities in bipartite networks is still in its early stage. Several quantitative functions have been developed for evaluating the quality of bipartite network divisions, however, these functions were designed based on null model comparisons and thus are subject to certain resolution limits. In this paper, we propose a new quantitative function called bipartite partition density for community detection in bipartite networks, and use some network examples to demonstrate that this quantitative function is superior to the widely used Barber’s bipartite modularity and other functions. Based on the bipartite partition density, the bipartite network community detection problem is formulated into an integer nonlinear programming model in which a bipartite network can be partitioned into reasonable overlapping communities by maximizing the quantitative function. We further develop a heuristic adapted label propagation algorithm (BiLPA) to optimize the bipartite partition density in large-scale bipartite networks. BiLPA is efficient and does not require any prior knowledge about the number of communities in the networks. We conduct extensive experiments on simulated and real-world networks and demonstrate that BiLPA can successfully identify the community structures of bipartite networks. [ABSTRACT FROM AUTHOR]

This paper studies the issue of assigning orientations to all links of an undirected network, which is called the link-orientation problem (LOP). First, we describe some practical variations and address some complexity analysis in LOPs for general networks. Then, we design efficient algorithms to solve these LOPs issues. The proposed approach employs the recursive shortest path rules and the efficient cost cores scheme to resolve the LOP issues for some weighted network systems. These classes of networks include multi-square, convex-bipartite, and convex-split networks. Next, we use the cost core algorithm for adjusting LOP and obtain the more efficient LOP for the weighted convex-bipartite and convex-split networks. In general, the LOP scheme can support the actual applications requirements to realize a WFQ (weighted fair queuing) task for multicast routing in real networks. Finally, the findings of this paper can be mainly applied to some network applications, including efficient revision of load balancing in a ATM switch network, quick selection of a firm's PCS (Proxy Cache Server) on the Web, and dynamic adjusting of link's changing conditions in a workflow system on the Internet. [ABSTRACT FROM AUTHOR]

We introduce a half-filled Hamiltonian of spin-half lattice fermions that can be studied with the efficient meron-cluster algorithm in any dimension. As with the usual bipartite half-filled Hubbard models, the naïve U(2) symmetry is enhanced to SO(4). On the other hand, our model has a novel spin-charge flip ZC2 symmetry which is an important ingredient of free massless fermions. In this work we focus on one spatial dimension and show that our model can be viewed as a lattice-regularized two-flavor chiral-mass Gross-Neveu model. Our model remains solvable in the presence of the Hubbard coupling U, which maps to a combination of Gross-Neveu and Thirring couplings in one dimension. Using the meron-cluster algorithm we find that the ground state of our model is a valence bond solid when U=0. From our field theory analysis, we argue that the valence bond solid forms inevitably because of an interesting frustration between spin and charge sectors in the renormalization group flow enforced by the ZC2 symmetry. This state spontaneously breaks translation symmetry by one lattice unit, which can be identified with a Zχ2 chiral symmetry in the continuum. We show that increasing U induces a quantum phase transition to a critical phase described by the SU(2)1 Wess-Zumino-Witten theory. The quantum critical point between these two phases is known to exhibit a novel symmetry enhancement between spin and dimer. Here we verify the scaling relations of these correlation functions near the critical point numerically. Our study opens up the exciting possibility of numerical access to similar novel phase transitions in higher dimensions in fermionic lattice models using the meron-cluster algorithm. [ABSTRACT FROM AUTHOR]

This article details the creation of two algorithms to improve upon Annie Moore optimization software to aid refugees in finding resettlement locations with employment opportunities. The authors apply the new algorithms to the United States resettlement agency HIAS’ data from 2014 to 2019 in comparison to Annie’s baseline hindsight-optimal employment. The new algorithms take future employment of new arrivals into account and are incorporated into an updated version of the Annie software.

The article discusses an algorithm designed to compute maximum flow and minimum-cost flows. It builds on the works of prior researchers to propose new theorems and provides formulas and graphs to illustrate these theorems and schemes.

The threshold theorem is a seminal result in the field of quantum computing asserting that arbitrarily long quantum computations can be performed on a faulty quantum computer provided that the noise level is below some constant threshold. This remarkable result comes at the price of increasing the number of qubits (quantum bits) by a large factor that scales polylogarithmically with the size of the quantum computation we wish to realize. Minimizing the space overhead for fault-tolerant quantum computation is a pressing challenge that is crucial to benefit from the computational potential of quantum devices. In this paper, we study the asymptotic scaling of the space overhead needed for fault-tolerant quantum computation. We show that the polylogarithmic factor in the standard threshold theorem is in fact not needed and that there is a fault-tolerant construction that uses a number of qubits that is only a constant factor more than the number of qubits of the ideal computation. This result was conjectured by Gottesman who suggested to replace the concatenated codes from the standard threshold theorem by quantum error-correcting codes with a constant encoding rate. The main challenge was then to find an appropriate family of quantum codes together with an efficient classical decoding algorithm working even with a noisy syndrome. The efficiency constraint is crucial here: bear in mind that qubits are inherently noisy and that faults keep accumulating during the decoding process. The role of the decoder is therefore to keep the number of errors under control during the whole computation. On a technical level, our main contribution is the analysis of the small-set-flip decoding algorithm applied to the family of quantum expander codes. We show that it can be parallelized to run in constant time while correcting sufficiently many errors on both the qubits and the syndrome to keep the error under control. These tools can be seen as a quantum generalization of the bit-flip algorithm applied to the (classical) expander codes of Sipser and Spielman. [ABSTRACT FROM AUTHOR]

Reversible one-dimensional cellular automata are studied from the perspective of Welch Sets. This paper presents an algorithm to generate random Welch sets that define a reversible cellular automaton. Then, properties of Welch sets are used in order to establish two bipartite graphs describing the evolution rule of reversible cellular automata. The first graph gives an alternative representation for the dynamics of these systems as block mappings and shifts. The second graph offers a compact representation for the evolution rule of reversible cellular automata. Both graphs and their matrix representations are illustrated by the generation of random reversible cellular automata with 6 and 18 states. [ABSTRACT FROM AUTHOR]

Finding a consensus embedding from multiple views is the mainstream task in multiview graph-based clustering, in which the key problem is to handle the inconsistence among multiple views. In this article, we consider clustering effectiveness and practical applicability collectively, and propose a parameter-free model to alleviate the inconsistence of multiple views cleverly. To be specific, the proposed model considers the diversities of multiple views as two-layers. The first layer considers the inconsistence among different features of each view and the second layer considers linking the preembeddings of multiple views attentively. By this way, a consensus embedding can be learned via kernel method effectively and the whole learning procedure is parameter-free. To solve the optimization problem involved in the proposed model, we propose an alternative algorithm which is efficient and easy to implement in practice. In the experiments, we evaluate the proposed model on synthetic and real datasets and the experimental results demonstrate its effectiveness. [ABSTRACT FROM AUTHOR]

The study and analysis of social graphs impacts on a wide range of applications, such as community decision making support and recommender systems. With the boom of online social networks, such analyses are benefiting from a massive collection and publication of social graphs at large scale. Unfortunately, individuals’ privacy right might be inadvertently violated when publishing this type of data. In this article, we introduce ( k , ℓ)-anonymity; a novel privacy measure aimed at evaluating the resistance of social graphs to active attacks. ( k , ℓ)-anonymity is based on a new problem in Graph Theory, the k-metric antidimension defined as follows. Let G = ( V , E ) be a simple connected graph and S = { w 1 , … , w t } ⊆ V an ordered subset of vertices. The metric representation of a vertex u ∈ V with respect to S is the t -vector r ( u | S ) = ( d G ( u , w 1 ) , … , d G ( u , w t ) ) , where d G ( u, v ) represents the length of a shortest u − v path in G . We call S a k -antiresolving set if k is the largest positive integer such that for every vertex v ∈ V − S there exist other k − 1 different vertices v 1 , … , v k − 1 ∈ V − S with r ( v | S ) = r ( v 1 | S ) = ⋯ = r ( v k − 1 | S ) . The k -metric antidimension of G is the minimum cardinality among all the k -antiresolving sets for G . We address the k -metric antidimension problem by proposing a true-biased algorithm with success rate above 80% when considering random graphs of size at most 100. The proposed algorithm is used to determine the privacy guarantees offered by two real-life social graphs with respect to ( k , ℓ)-anonymity. We also investigate theoretical properties of the k -metric antidimension of graphs. In particular, we focus on paths, cycles, complete bipartite graphs and trees. [ABSTRACT FROM AUTHOR]

Detecting anomalies on graph data has two types of methods. One is pattern mining that discovers strange structures globally such as quasi-cliques, bipartite cores, or dense blocks in the graph’s adjacency matrix. The other is feature learning that mainly uses graph neural networks (GNNs) to aggregate information from local neighborhood into node representations. However, there is a lack of study that utilizes both the global and local information for graph anomaly detection. In this article, we propose a synergistic approach that leverages pattern mining to inform the GNN algorithms on how to aggregate local information through connections to capture the global patterns. Specifically, it uses a GNN encoder to perform feature aggregation, and the pattern mining algorithms supervise the GNN training process through a novel loss function. We provide theoretical analysis on the effectiveness of the loss function, as well as empirical analysis on the proposed approach across a variety of GNN algorithms and pattern mining methods. Experiments on real-world data show that the synergistic approach performs significantly better than existing graph anomaly detection methods. [ABSTRACT FROM AUTHOR]

Query log analysis has received substantial attention in recent years, in which the click graph is an important technique for describing the relationship between queries and URLs. State-of-the-art approaches based on the raw click frequencies for modeling the click graph, however, are not noise-eliminated. Nor do they handle heterogeneous query- URL pairs well. In this paper, we investigate and develop a novel entropy-biased framework for modeling click graphs. The intuition behind this model is that various query-URL pairs should be treated differently, i.e., common clicks on less frequent but more specific URLs are of greater value than common clicks on frequent and general URLs. Based on this intuition, we utilize the entropy information of the URLs and introduce a new concept, namely the inverse query frequency (IQF), to weigh the importance (discriminative ability) of a click on a certain URL. The IQF weighting scheme is never explicitly explored or statistically examined for any bipartite graphs in the information retrieval literature. We not only formally define and quantify this scheme, but also incorporate it with the click frequency and user frequency information on the click graph for an effective query representation. To illustrate our methodology, we conduct experiments with the AOL query log data for query similarity analysis and query suggestion tasks. Experimental results demonstrate that considerable improvements in performance are obtained with our entropy-biased models. [ABSTRACT FROM AUTHOR]

We present an approach to improving the precision of an initial document ranking wherein we utilize cluster information within a graph-based framework. The main idea is to perform re-ranking based on centrality within bipartite graphs of documents (on one side) and clusters (on the other side), oil the premise that these are mutually reinforcing entities. Links between entities are created via consideration of language models induced from them. We find that our cluster-document graphs give rise to much better retrieval performance than previously proposed document-only graphs do. For example, authority-based re-ranking of documents via a HITS-style cluster-based approach outperforms a previously-proposed PageRank-inspired algorithm applied to solely-document graphs. Moreover, we also show that computing authority scores for clusters constitutes an effective method for identifying clusters containing a large percentage of relevant documents [ABSTRACT FROM AUTHOR]

The article looks at developments in parameterized algorithms. Particular focus is given to the algebraization of problems and the algebraic detection of monomials. Details on algebraic fingerprints are presented. Other topics include NP-complete problems, research on the Hamiltonian path problem by mathematician Andreas Björklund, and the k-path problem.

A generalized family of adversary robust consensus protocols is proposed and analyzed. These are distributed algorithms for multiagent systems seeking to agree on a common value of a shared variable, even in the presence of faulty or malicious agents, which are updating their local state according to the protocol rules. In particular, we adopt monotone joint-agent interactions, a very general mechanism for processing locally available information and allowing cross-comparisons between state-values of multiple agents simultaneously. The salient features of the proposed class of algorithms are abstracted as a Petri net and convergence criteria for the resulting time evolutions formulated by employing structural invariants of the net. [ABSTRACT FROM AUTHOR]

Network data show the relationship among one kind of objects, such as social networks and hyperlinks on the Web. Many statistical models have been proposed for analyzing these data. For modeling cluster structures of networks, the infinite relational model (IRM) was proposed as a Bayesian nonparametric extension of the stochastic block model. In this brief, we derive the inference algorithms for the IRM of network data based on the variational Bayesian (VB) inference methods. After showing the standard VB inference, we derive the collapsed VB (CVB) inference and its variant called the zeroth-order CVB inference. We compared the performances of the inference algorithms using six real network datasets. The CVB inference outperformed the VB inference in most of the datasets, and the differences were especially larger in dense networks. [ABSTRACT FROM AUTHOR]

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2005.08.009 Byline: Vardges Melkonian Abstract: We present new primal-dual algorithms for several network design problems. The problems considered are the generalized Steiner tree problem (GST), the directed Steiner tree problem (DST), and the set cover problem (SC) which is a subcase of DST. All our problems are NP-hard; so we are interested in their approximation algorithms. First, we give an algorithm for DST which is based on the traditional approach of designing primal-dual approximation algorithms. We show that the approximation factor of the algorithm is k, where k is the number of terminals, in the case when the problem is restricted to quasi-bipartite graphs. We also give pathologically bad examples for the algorithm performance. To overcome the problems exposed by the bad examples, we design a new framework for primal-dual algorithms which can be applied to all of our problems. The main feature of the new approach is that, unlike the traditional primal-dual algorithms, it keeps the dual solution in the interior of the dual feasible region. The new approach allows us to avoid including too many arcs in the solution, and thus achieves a smaller-cost solution. Our computational results show that the interior-point version of the primal-dual most of the time performs better than the original primal-dual method. Author Affiliation: Department of Mathematics, Ohio University, Athens, Ohio 45701, USA

Abstract: Searching and mining biomedical literature databases are common ways of generating scientific hypotheses by biomedical researchers. Clustering can assist researchers to form hypotheses by seeking valuable information from grouped documents effectively. Although a large number of clustering algorithms are available, this paper attempts to answer the question as to which algorithm is best suited to accurately cluster biomedical documents. Non-negative matrix factorization (NMF) has been widely applied to clustering general text documents. However, the clustering results are sensitive to the initial values of the parameters of NMF. In order to overcome this drawback, we present the ensemble NMF for clustering biomedical documents in this paper. The performance of ensemble NMF was evaluated on numerous datasets generated from the TREC Genomics track dataset. With respect to most datasets, the experimental results have demonstrated that the ensemble NMF significantly outperforms classical clustering algorithms of bisecting K-means, and hierarchical clustering. We compared four different methods for constructing an ensemble NMF. For clustering biomedical documents, this research is the first to compare ensemble NMF with typical classical clustering algorithms, and validates ensemble NMF constructed from different graph-based ensemble algorithms. This is also the first work on ensemble NMF with Hybrid Bipartite Graph Formulation for clustering biomedical documents. [Copyright &y& Elsevier]

Abstract: Stocks with similar financial ratio values across years have similar price movements. We investigate this hypothesis by clustering groups of stocks that exhibit homogeneous financial ratio values across years, and then study their price movements. We propose using cross-graph quasi-biclique (CGQB) subgraphs to cluster stocks, as they can define the three dimensional (3D) subspaces of financial ratios that the stocks are homogeneous in across the years, and they can also handle missing values that are rampant in the stock data. Furthermore, investors can easily analyze these 3D subspaces to explore the relations between the stocks and financial ratios. We develop a novel algorithm, CGQBminer, which mines the complete set of CGQB subgraphs from the stock data. Through experimental analysis, we show that the hypothesis is valid. Furthermore, we demonstrate that having an investment strategy which uses groups of stocks mined by CGQB subgraphs have higher returns than one that does not. We also conducted an extensive performance analysis on CGQBminer, and show that it is efficient across different 3D datasets and parameter settings. [Copyright &y& Elsevier]

Consider an equal number of mobile robotic agents and distinct target locations dispersed in an environment. Each agent has a limited communication range and either: 1) knowledge of every target position or 2) a finite-range sensor capable of acquiring target positions and no a priori knowledge of target positions. In this paper we study the following target assignment problem: design a distributed algorithm with which the agents divide the targets among themselves and, simultaneously, move to their unique target. We evaluate an algorithm's performance by characterizing its worst-case asymptotic time to complete the target assignment; that is the task completion time as the number of agents (and targets) increases, and the size of the environment scales to accommodate them. We introduce the intuitive class of monotonic algorithms, and give a lower bound on its worst-case completion time. We design and analyze two algorithms within this class: the ETSP ASSGMT algorithm which works under assumption 1), and the GRID ASSGMT algorithm which works under either assumption 1) or 2). In "sparse environments," where communication is infrequent, the ETSP ASSGMT algorithm is within a constant factor of the optimal monotonic algorithm for worst-case initial conditions. In "dense environments," where communication is more prevalent, the GRID ASSGMT algorithm is within a constant factor of the optimal monotonic algorithm for worst-case initial conditions. In addition we characterize the performance of the GRID ASSGMT algorithm for uniformly distributed targets and agents, and for the case when there are more agents than targets. [ABSTRACT FROM AUTHOR]

Abstract-In this paper, the problem of designing robust supervisory controllers for uncertain discrete event systems is studied. It is assumed that both the plant behavior and the design specifications can be represented by regular languages. It is also assumed that the unknown model of the uncertain plant belongs to a finite set of possibilities. To solve the problem, a modular approach based on a general recursive robust control scheme is developed. The contribution of the present paper consists in deriving a maximally permissive modular robust supervisory controller for the case of prefix.closed languages, having the advantage of linear complexity in the number of models as opposed to the exponential complexity of the worstcase scenario in the direct implementation of standard supervisors for aug. mented systems. [ABSTRACT FROM AUTHOR]

Abstract-This paper is concerned with the study of observability in a structural framework. It turns out that the system is structurally observable if and only if the system is output connected and contains no contraction. We focus our attention on the observability preservation under sensor failure. We consider linear observable systems and we wonder if a given system remains observable in case of sensor failure. More precisely, we will characterize among the sensors those which are critical, i.e., which failure leads to observability loss, those which are useless for observability purpose and the set of those which are useful without being critical. Using a graph approach we classify the sensors with respect to their importance for output connection preservation, contraction avoidance and then observability preservation under sensor failure. [ABSTRACT FROM AUTHOR]

Lithography-based integrated circuit fabrication is rapidly approaching its limit in terms of feature size. The current alternative is nanotechnology-based fabrication, which relies on self-assembly of nanotubes or nanowires. Such a process is subject to a high defect rate, which can be tolerated using carefully crafted defect tolerance techniques. This paper presents an algorithm for reconfiguration-based defect tolerance in nanotechnology switches. The algorithm offers an average switch density improvement of 50% to 100% to most recently published techniques. The algorithm is also consistent in improving the yield through minimizing false rejects as the results show over a large sample. The improvement percentage varies depending on the manufactured switch size and the desired defect-free size with the improvement in efficiency directly proportional to the size of the switch. [ABSTRACT FROM AUTHOR]

Sharing the common spectrum among the links in a vicinity is a fundamental problem in wireless ad-hoc networks. Lately, some scheduling approaches have been proposed that guarantee fair share of bandwidth among the links. The quality of service perceived by the applications however depends on the end-to-end bandwidth allocated to the multihop sessions. We propose an algorithm that provides provably maxmin fair end-to-end bandwidth to sessions. The algorithm combines a link scheduling that avoids collisions, a fair session service discipline per link, and a hop-by-hop window flow control. All the stages of the algorithm are implementable based on local information, except the link scheduling part that needs some network-wide coordination. [ABSTRACT FROM AUTHOR]

Abstract: In Toroslu and Üçoluk [I.H. Toroslu, G. Üçoluk, Incremental assignment problem, Information Sciences 177 (2007) 1523–1529] the incremental assignment problem is defined as follows. A new pair of vertices and their incident edges are added to a weighted bipartite graph whose maximum-weighted matching is already known, and the maximum-weighted matching of the extended graph is sought. An O(n 2) algorithm for the problem has been derived, with n the size of a partition in the bipartite graph. We point out that such a result can be found in literature. [Copyright &y& Elsevier]