Search

The problem of finding a maximum size matching in a graph (known as the maximum matching problem) is one of the most classical problems in computer science. Despite a significant body of work dedicated to the study of this problem in the data stream model, the state-of-the-art single-pass semi-streaming algorithm for it is still a simple greedy algorithm that computes a maximal matching, and this way obtains 1 / 2 -approximation. Some previous works described two/three-pass algorithms that improve over this approximation ratio by using their second and third passes to improve the above mentioned maximal matching. One contribution of this paper continues this line of work by presenting new three-pass semi-streaming algorithms that work along these lines and obtain improved approximation ratios of 0.6111 and 0.5694 for triangle-free and general graphs, respectively. Unfortunately, a recent work Konrad and Naidu (Approximation, randomization, and combinatorial optimization. Algorithms and techniques, APPROX/RANDOM 2021, August 16–18, 2021. LIPIcs, vol 207, pp 19:1–19:18, 2021. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.19) shows that the strategy of constructing a maximal matching in the first pass and then improving it in further passes has limitations. Additionally, this technique is unlikely to get us closer to single-pass semi-streaming algorithms obtaining a better than 1 / 2 -approximation. Therefore, it is interesting to come up with algorithms that do something else with their first pass (we term such algorithms non-maximal-matching-first algorithms). No such algorithms were previously known, and the main contribution of this paper is describing such algorithms that obtain approximation ratios of 0.5384 and 0.5555 in two and three passes, respectively, for general graphs. The main significance of our results is not in the numerical improvements, but in demonstrating the potential of non-maximal-matching-first algorithms. [ABSTRACT FROM AUTHOR]

Cluster analysis is one of the most fundamental methods in data mining, and it has been widely used in economics, social sciences and computer science. However, with the rapid development of Internet technology, the volume of data required for various web applications has grown rapidly, making the traditional clustering analysis methods face technical challenges. How to obtain useful information in a large amount of data quickly and efficiently is an urgent problem in many industrial fields. With the continuous development of cloud computing technology, large amounts of data can be performed quickly and efficiently. Hadoop is an open source distributed cloud computing platform with HDFS (Digital File System) and MapReduce as its core. HDFS provides massive data storage, while MapReduce uses the MapReduce programming model to achieve parallel processing. Compared with the traditional parallel programming model, it contains basic functions such as data partitioning, task scheduling, and parallel processing, making it possible for users to develop distributed applications on their own without understanding the basics of distributed basics, thus facilitating the design of parallel programs. K-means algorithm is a typical clustering analysis method, which is widely used in industry, but the number of iterations will increase significantly due to the growth of data volume, thus reducing the efficiency of computation. In order to better apply to the cluster analysis of large-scale data, this paper firstly implements a parallelization algorithm based on MapReduce on Hadoop platform using the basic idea of MapReduce and improves the K-means algorithm for the problems of blindness and easy to fall into local optimum when selecting randomly in clusters. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new effective algorithm for the categorical syllogisms by using a calculus system Syllogistic Logic with Carroll Diagrams, which determines a formal approach to logical reasoning with diagrams, for representations of the fundamental Aristotelian categorical syllogisms. We show that this logical reasoning is closed under the syllogistic criterion of inference. Therefore, the calculus system is implemented to let the formalism which comprises synchronically bilateral and trilateral diagrammatical appearance and naive algorithmic nature. And also, there is no need specific knowledge or exclusive ability to understand this decision procedure as well as to use it in an algorithmic system. Consequently, the empirical contributions of this paper are to design a polynomial-time algorithm at the first time in the literature to conduce to researchers getting into the act in different areas of science used categorical syllogisms such as artificial intelligence, engineering, computer science and etc. [ABSTRACT FROM AUTHOR]

We study a security game over a network played between a defender and kattackers. Every attacker chooses, probabilistically, a node of the network to damage. The defender chooses, probabilistically as well, a connected induced subgraph of the network of λ nodes to scan and clean. Each attacker wishes to maximize the probability of escaping her cleaning by the defender. On the other hand, the goal of the defender is to maximize the expected number of attackers that she catches. This game is a generalization of the model from the seminal paper of Mavronicolas et al. Mavronicolas et al. (in: International symposium on mathematical foundations of computer science, MFCS, pp 717–728, 2006). We are interested in Nash equilibria of this game, as well as in characterizing defense-optimal networks which allow for the best equilibrium defense ratio; this is the ratio of k over the expected number of attackers that the defender catches in equilibrium. We provide a characterization of the Nash equilibria of this game and defense-optimal networks. The equilibrium characterizations allow us to show that even if the attackers are centrally controlled the equilibria of the game remain the same. In addition, we give an algorithm for computing Nash equilibria. Our algorithm requires exponential time in the worst case, but it is polynomial-time for λ constantly close to 1 or n. For the special case of tree-networks, we further refine our characterization which allows us to derive a polynomial-time algorithm for deciding whether a tree is defense-optimal and if this is the case it computes a defense-optimal Nash equilibrium. On the other hand, we prove that it is NP -hard to find a best-defense strategy if the tree is not defense-optimal. We complement this negative result with a polynomial-time constant-approximation algorithm that computes solutions that are close to optimal ones for general graphs. Finally, we provide asymptotically (almost) tight bounds for the Price of Defense for any λ ; this is the worst equilibrium defense ratio over all graphs. [ABSTRACT FROM AUTHOR]

Algorithmic statistics looks for models of observed data that are good in the following sense: a model is simple (i.e., has small Kolmogorov complexity) and captures all the algorithmically discoverable regularities in the data. However, this idea can not be used in practice as is because Kolmogorov complexity is not computable. In this paper we develop an algorithmic version of algorithmic statistics that uses space-bounded Kolmogorov complexity. We prove a space-bounded version of a basic result from "classical" algorithmic statistics, the connection between optimality and randomness deficiences. The main tool is the Nisan–Wigderson pseudo-random generator. An extended abstract of this paper was presented at the 12th International Computer Science Symposium in Russia (Milovanov 10). [ABSTRACT FROM AUTHOR]

Searching for all occurrences of a pattern in a text is a fundamental problem in computer science with applications in many other fields, like natural language processing, information retrieval and computational biology. Sampled string matching is an efficient approach recently introduced in order to overcome the prohibitive space requirements of an index construction, on the one hand, and drastically reduce searching time for the online solutions, on the other hand. In this paper we present a new algorithm for the sampled string matching problem, based on a characters distance sampling approach. The main idea is to sample the distances between consecutive occurrences of a given pivot character and then to search online the sampled data for any occurrence of the sampled pattern, before verifying the original text. From a theoretical point of view we prove that, under suitable conditions, our solution can achieve both linear worst-case time complexity and optimal average-time complexity. From a practical point of view it turns out that our solution shows a sub-linear behaviour in practice and speeds up online searching by a factor of up to 9, using limited additional space whose amount goes from 11 to 2.8% of the text size, with a gain up to 50% if compared with previous solutions. [ABSTRACT FROM AUTHOR]

In this paper, we prove that, given a clique-width k-expression of an n-vertex graph, Hamiltonian Cycle can be solved in time n O (k) . This improves the naive algorithm that runs in time n O (k 2) by Espelage et al. (Graph-theoretic concepts in computer science, vol 2204. Springer, Berlin, 2001), and it also matches with the lower bound result by Fomin et al. that, unless the Exponential Time Hypothesis fails, there is no algorithm running in time n o (k) (Fomin et al. in SIAM J Comput 43:1541–1563, 2014). We present a technique of representative sets using two-edge colored multigraphs on k vertices. The essential idea is that, for a two-edge colored multigraph, the existence of an Eulerian trail that uses edges with different colors alternately can be determined by two information: the number of colored edges incident with each vertex, and the connectedness of the multigraph. With this idea, we avoid the bottleneck of the naive algorithm, which stores all the possible multigraphs on k vertices with at most n edges. [ABSTRACT FROM AUTHOR]

Let B = (X , Y , E) be a bipartite graph. A half-square of B has one color class of B as vertex set, say X; two vertices are adjacent whenever they have a common neighbor in Y. Every planar graph is a half-square of a planar bipartite graph, namely of its subdivision. Until recently, only half-squares of planar bipartite graphs, also known as map graphs (Chen et al., in: Proceedings of the thirtieth annual ACM symposium on the theory of computing, STOC '98, pp 514–523. 10.1145/276698.276865, 1998; J ACM 49(2):127–138. 10.1145/506147.506148, 2002), have been investigated, and the most discussed problem is whether it is possible to recognize these graphs faster and simpler than Thorup's O (n 120) -time algorithm (Thorup, in: Proceedings of the 39th IEEE symposium on foundations of computer science (FOCS), pp 396–405. 10.1109/SFCS.1998.743490, 1998). In this paper, we identify the first hardness case, namely that deciding if a graph is a half-square of a balanced bisplit graph is NP-complete. (Balanced bisplit graphs form a proper subclass of star convex bipartite graphs). For classical subclasses of tree convex bipartite graphs such as biconvex, convex, and chordal bipartite graphs, we give good structural characterizations of their half-squares that imply efficient recognition algorithms. As a by-product, we obtain new characterizations of unit interval graphs, interval graphs, and of strongly chordal graphs in terms of half-squares of biconvex bipartite, convex bipartite, and of chordal bipartite graphs, respectively. Good characterizations of half-squares of star convex and star biconvex bipartite graphs are also given, giving linear-time recognition algorithms for these half-squares. [ABSTRACT FROM AUTHOR]

Research on graph searching has recently gained interest in computer science, mathematics, and physics. This paper studies fast searching of a fugitive in a graph, a model that was introduced by Dyer et al. (in: Fleischer, Xu (eds.) Algorithmic aspects in information and management, Springer, New York, 2008). We provide lower bounds and upper bounds on the fast search number (i.e., the minimum number of searchers required for capturing the fugitive) of complete k-partite graphs. We also investigate some special classes of complete k-partite graphs, such as complete bipartite graphs and complete split graphs. We solve the open problem of determining the fast search number of complete bipartite graphs, and present upper and lower bounds on the fast search number of complete split graphs. [ABSTRACT FROM AUTHOR]

Recently, as a result of the popularity of online social networks, the analysis and comparison of their contents are in an incremental need. The study of social network and social interaction including both positive and negative connections, which is obviously significant. Our finding denotes that the contacts in the basic social networks, including their accuracy, are predictable. The trust of numerous users' imparting on a node accounts for the form of networks. In this paper, We propose a model in this article to figure out the prestige on nodes in a network based on trust. This network also lays more emphasis to on trustworthy nodes. In the beginning, to achieve this goal, we try to indicate signed advantages in networks to predict an user's opinion to another. After that, we present an algorithm, which can compute the prestige and trustworthiness. In their edge weight, we can find out the trust score. According to our experiments on the public dataset, we demonstrate the validity and efficiency of our algorithm. [ABSTRACT FROM AUTHOR]

In the paper, the non-separability relation for finite state machines with time-outs is studied. A specific feature of such machines is integer-valued delays, or time-outs, which determine how long the finite state machine will stay in one or another state if there are no input actions. If the time-out is over and no input symbol has been applied, then the TFSM state is changed according to the transition under time delay. In the paper, an algorithm for constructing a separating sequence for such finite state machines is presented. Here, the separating sequence is a timed input sequence for which sets of input sequences of the TFSM do not intersect; hence, it is sufficient to apply the separating sequence once in order to distinguish the TFSMs by their output reactions. This algorithm underlies the algorithm for construction of test suites with respect to non-separability relation in the case where the fault domain is specified by means of a mutation machine. Test suite derivation with respect to non-separability relation by way of 'TFSM to FSM' transformation is discussed. [ABSTRACT FROM AUTHOR]

We first consider the problem of finding a maximum size stable matching if incomplete lists and ties are both allowed, but ties are on one side only. For this problem we give a simple, linear time 3/2-approximation algorithm, improving on the best known approximation factor 5/3 of Irving and Manlove (J. Comb. Optim., doi:, ). Next, we show how this extends to the Hospitals/Residents problem with the same ratio if the residents have strict orders. We also give a simple linear time algorithm for the general problem with approximation factor 5/3, improving the best known 15/8-approximation algorithm of Iwama, Miyazaki and Yamauchi (SODA '07: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 288-297, ). For the cases considered in this paper it is NP-hard to approximate within a factor of 21/19 by the result of Halldórsson et al. (ACM Transactions on Algorithms 3(3):30, ). Our algorithms not only give better approximation ratios than the cited ones, but are much simpler and run significantly faster. Also we may drop a restriction used in (J. Comb. Optim., doi:, ) and the analysis is substantially more moderate. Preliminary versions of this paper appeared in (Király, Egres Technical Report TR-2008-04, , ; Király in Proceedings of MATCH-UP 2008: Matching Under Preferences-Algorithms and Complexity, Satellite Workshop of ICALP, July 6, 2008, Reykjavík, Iceland, pp. 36-45, ; Király in ESA 2008, Lecture Notes in Computer Science, vol. 5193, pp. 623-634, ). For the related results obtained thenceforth see Sect. 5. [ABSTRACT FROM AUTHOR]

In this paper, we discuss one of the most important issues in Sensor-Grid, i.e., to develop a fast and flexible content-based publish/subscribe information dissemination (CBPSID) system for automatic fusion, interpretation, sharing and delivery of huge sensor data to consumers as the entire Sensor-Grid environment is very dynamic. Existing works to develop the CBPSID system in Sensor-Grid mostly focus on reducing the effort to define and maintain subscriptions and to handle the difficulty of dynamic changes of publishers and consumers data. However, the performance of a CBPSID system in Sensor-Grid is bounded by the expensive matching/evaluation cost of events. Existing event-matching algorithms are not very efficient, especially for interval range predicates or overlapping predicates in subscriptions which are practical in Sensor-Grid as well as other application areas. So in this paper we discuss the above challenge and propose a dynamic and fast event-matching algorithm called CGIM for the CBPSID system in Sensor-Grid. The algorithm supports range predicates or overlapping predicates very well and provides single and composite event matching. It uses two approaches, called SGIM and DGIM, to group the subscriptions by the predicates and dynamically identifies appropriate number of groups considering different statistical distributions of subscriptions at run time. Also, we present an experimental evaluation of the proposed algorithm in a Sensor-Grid based u-Healthcare scenario using synthetic workloads and compare its performance with existing algorithms. The experimental results show that our algorithm significantly reduces the evaluation cost (on average using SGIM by 79% and DGIM by 88%) comparing with others and guarantees the scalability with respect to the number of subscriptions as well as the number of predicates and events. In addition, further experiments were conducted by applying the CGIM algorithm in other application areas, e.g. in the publish/subscribe system for online job sites, to show its diverse utilization and scalability. [ABSTRACT FROM AUTHOR]

There is rapidly increasing interest in Location Based Service (LBS) which utilizes location data of moving objects. To efficiently manage the huge amounts of location data in LBS, the GALIS (Gracefully Aging Location Information System) architecture, a cluster-based distributed computing architecture, is proposed. The GALIS using the non-uniform 2-level grid algorithm performs load balancing and indexing for nodes. However, the non-uniform 2-level grid algorithm has a problem creating unnecessary nodes when moving objects are crowded in a certain region. Therefore, a new node split algorithm, which is more efficient for various distribution of moving objects, is proposed in this paper. Because the algorithm proposed in this paper considers spatial distribution for the current location of moving objects, it can perform efficient load balancing without creating unnecessary nodes even when moving objects are congested in a certain region. Besides, the various data distribution configuration for moving objects has been experimented by implementing node split simulators and it’s been verified that the proposed algorithm can split nodes more efficiently than the existing algorithm. [ABSTRACT FROM AUTHOR]

Software pipelining is an efficient method of loop optimization that allows for parallelism of operations related to different loop iterations. Currently, most commercial compilers use loop pipelining methods based on modulo scheduling algorithms. This paper reviews these algorithms and considers algorithmic solutions designed for overcoming the negative effects of software pipelining of loops (a significant growth in code size and increase in the register pressure) as well as methods making it possible to use some hardware features of a target architecture. The paper considers global-scheduling mechanisms allowing one to pipeline loops containing a few basic blocks and loops in which the number of iterations is not known before the execution. [ABSTRACT FROM AUTHOR]

Pseudo-kernelization is introduced in this paper as a new strategy for improving fixed-parameter algorithms. This new technique works for bounded search tree algorithms by identifying favorable branching conditions whose absence could be used to reduce the size of corresponding problem instances. Pseudo-kernelization applies well to hitting set problems. It can be used either to improve the search tree size of a 3-Hitting-Set algorithm from O*(2.179k) to O*(2.05k), or to improve the kernel size from k3 to 27k. In this paper the parameterized 3-Hitting-Set and Face Cover problems are used as typical examples. [ABSTRACT FROM AUTHOR]

Both average-case complexity and the study of the approximability of NP optimisation problems are well established and active fields of research. Many results concerning the average behaviour of approximation algorithms for NP optimisation problems exist, both with respect to their running time and their performance ratio, but a theoretical framework to examine their structural properties with respect to their average-case approximability is not yet established. With this paper we hope to fill the gap and provide not only the necessary definitions, but show that: 1. The class of NP optimisation problems with p-computable input distributions has complete problems with respect to an average-approximability preserving reduction. 2. The average-time variants of worst-case approximation classes form a strict hierarchy if NP is not easy on average. By linking average-ratio approximation algorithms to polynomial-time algorithms schemes, we can prove similar hierarchy results for the average-ratio versions of the approximation classes. This is done under the premise that not all NP-problems with p-computable input distributions have polynomial-time algorithm schemes. 3. The question whether NP is easy on average is equivalent to the question whether every NP optimisation problem with a p-computable input distribution has an average polynomial-time approximation scheme. An extended abstract of this paper appeared in [28]. [ABSTRACT FROM AUTHOR]

Grover’s search algorithm can be applied to a wide range of problems; even problems not generally regarded as searching problems, can be reformulated to take advantage of quantum parallelism and entanglement, and lead to algorithms which show a square root speedup over their classical counterparts. In this paper, we discuss a systematic way to formulate such problems and give as an example a quantum scheduling algorithm for an R||Cmax problem. R||Cmax is representative for a class of scheduling problems whose goal is to find a schedule with the shortest completion time in an unrelated parallel machine environment. Given a deadline, or a range of deadlines, the algorithm presented in this paper allows us to determine if a solution to an R||Cmax problem with N jobs and M machines exists, and if so, it provides the schedule. The time complexity of the quantum scheduling algorithm is $${\mathcal{O}(\sqrt{M^N})}$$ while the complexity of its classical counterpart is $${\mathcal{O}(M^N)}$$ . [ABSTRACT FROM AUTHOR]

The main objective of this paper is to describe a realistic framework to understand parallel performance of high-dimensional image processing algorithms in the context of heterogeneous networks of workstations (NOWs). As a case study, this paper explores techniques for mapping hyperspectral image analysis techniques onto fully heterogeneous NOWs. Hyperspectral imaging is a new technique in remote sensing that has gained tremendous popularity in many research areas, including satellite imaging and aerial reconnaissance. The automation of techniques able to transform massive amounts of hyperspectral data into scientific understanding in valid response times is critical for space-based Earth science and planetary exploration. Using an evaluation strategy which is based on comparing the efficiency achieved by an heterogeneous algorithm on a fully heterogeneous NOW with that evidenced by its homogeneous version on a homogeneous NOW with the same aggregate performance as the heterogeneous one, we develop a detailed analysis of parallel algorithms that integrate the spatial and spectral information in the image data through mathematical morphology concepts. For comparative purposes, performance data for the tested algorithms on Thunderhead (a large-scale Beowulf cluster at NASA’s Goddard Space Flight Center) are also provided. Our detailed investigation of the parallel properties of the proposed morphological algorithms provides several intriguing findings that may help image analysts in selection of parallel techniques and strategies for specific applications. [ABSTRACT FROM AUTHOR]

This paper discusses the multicast routing problem with QoS constraints, and describes a network model that is suitable to research such routing problem. The paper mainly presents a distributed QoS-aware multicast routing protocol (QMRP). The QMRP can operate on top of the unicast routing protocol. It only requires the local state information of the link (or the node), but does not require any global network state to be maintained. The QMRP can significantly reduce the overhead for constructing a multicast tree with QoS constraints. In QMRP, a multicast group member can join or leave the multicast session dynamically, which can support dynamic membership. The protocol can search multiple feasible tree branches, and select the optimal or near-optimal branch for connecting the new receiver to the multicast tree if it exists. In this paper, the proof of correctness and complexity analysis of the QMRP are given, and the performance measures of the protocol are evaluated using simulation. The study shows that QMRP provides an available approach to multicast routing with QoS constraints and dynamic membership support. [ABSTRACT FROM AUTHOR]

Overlapping communication with computation is a well-known approach to improving performance. Previous research has focused on optimizations performed by the programmer. This paper presents a compiler algorithm that automatically determines the appropriate loop indices of a given nested loop and applies loop interchange and tiling in order to overlap communication with computation. The algorithm avoids generating redundant communication by providing a framework for combining information on data dependence, communication, and reuse. It also describes a method of generating messages to exchange data between processors for tiled loops on distributed memory machines. The algorithm has been implemented in our High Performance Fortran (HPF) compiler, and experimental results have shown its effectiveness on distributed memory machines, such as the RISC System/6000 Scalable POWERparallel System. This paper also discusses the architectural problems of efficient optimization. [ABSTRACT FROM AUTHOR]

In this paper we find a connection between constructive number fields and computable reals. This connection is applied to prove the computability in the rigorous sense of computable analysis) of solutions of some important systems of partial differential equations, by means of algorithms which are really used in numerical analysis. [ABSTRACT FROM AUTHOR]

The dynamic trie is a fundamental data structure with applications in many areas of computer science. This paper proposes a new technique for maintaining a dynamic trie T of size at most 2 nodes under the unit-cost RAM model with a fixed word size w. It is based on the idea of partitioning T into a set of linked small tries, each of which can be maintained efficiently. Our method is not only space-efficient, but also allows the longest common prefix between any query pattern P and the strings currently stored in T to be computed in o(| P|) time for small alphabets, and allows any leaf to be inserted into or deleted from T in o(log| T|) time. To demonstrate the usefulness of our new data structure, we apply it to LZ-compression. Significantly, we obtain the first algorithm for generating the lz78 encoding of a given string of length n over an alphabet of size σ in sublinear ( o( n)) time and sublinear ( o( nlog σ) bits) working space for small alphabets ( $\sigma= 2^{o(\log n \frac{\log\log\log n}{(\log\log n)^{2}})}$). Moreover, the working space for our new algorithm is asymptotically less than or equal to the space for storing the output compressed text, regardless of the alphabet size. [ABSTRACT FROM AUTHOR]

In the temporal database literature, every fact stored in a database may be equipped with two temporal dimensions: the valid time, which describes the time when the fact is true in the modeled reality, and the transaction time, which describes the time when the fact is current in the database and can be retrieved. Temporal functional dependencies (TFDs) add valid time to classical functional dependencies (FDs) in order to express database integrity constraints over the flow of time. Currently, proposals dealing with TFDs adopt a point-based approach, where tuples hold at specific time points, to express integrity constraints such as ' for each month, the salary of an employee depends only on his role'. To the best of our knowledge, there are no proposals dealing with interval-based temporal functional dependencies (ITFDs), where the associated valid time is represented by an interval and there is the need of representing both point-based and interval-based data dependencies. In this paper, we propose ITFDs based on Allen's interval relations and discuss their expressive power with respect to other TFDs proposed in the literature: ITFDs allow us to express interval-based data dependencies, which cannot be expressed through the existing point-based TFDs. ITFDs allow one to express constraints such as ' employees starting to work the same day with the same role get the same salary' or ' employees with a given role working on a project cannot start to work with the same role on another project that will end before the first one'. Furthermore, we propose new algorithms based on B-trees to efficiently verify the satisfaction of ITFDs in a temporal database. These algorithms guarantee that, starting from a relation satisfying a set of ITFDs, the updated relation still satisfies the given ITFDs. [ABSTRACT FROM AUTHOR]

The quantum Fourier transform, the quantum wavelet transform, etc., have been shown to be a powerful tool in developing quantum algorithms. However, in classical computing, there is another kind of transforms, image scrambling, which are as useful as Fourier transform, wavelet transform, etc. The main aim of image scrambling, which is generally used as the preprocessing or postprocessing in the confidentiality storage and transmission, and image information hiding, was to transform a meaningful image into a meaningless or disordered image in order to enhance the image security. In classical image processing, Arnold and Fibonacci image scrambling are often used. In order to realize these two image scrambling in quantum computers, this paper proposes the scrambling quantum circuits based on the flexible representation for quantum images. The circuits take advantage of the plain adder and adder modulo $$N$$ to factor the classical transformations into basic unitary operators such as Control-NOT gates and Toffoli gates. Theoretical analysis indicates that the network complexity grows linearly with the size of the number to be operated. [ABSTRACT FROM AUTHOR]

The paper presents a clutter detection and removal algorithm for complex document images. This distance transform based technique aims to remove irregular and independent unwanted clutter while preserving the text content. The novelty of this approach is in its approximation to the clutter–content boundary when the clutter is attached to the content in irregular ways. As an intermediate step, a residual image is created, which forms the basis for clutter detection and removal. Clutter detection and removal are independent of clutter’s position, size, shape, and connectivity with text. The method is tested on a collection of highly degraded and noisy, machine-printed and handwritten Arabic and English documents, and results show pixel-level accuracies of 99.18 and 98.67 % for clutter detection and removal, respectively. This approach is also extended to documents having a mix of clutter and salt-and-pepper noise. [ABSTRACT FROM AUTHOR]

Semi-supervised learning has become one of the hotspots in the field of machine learning in recent years. It is successfully applied in clustering and improves the clustering performance. This paper proposes a new clustering algorithm, called semi-supervised spectral clustering based on constraints expansion (SSCCE). This algorithm expands the known constraints set, changes the similarity relation of the sample points through the density-sensitive path distance, and then combines with semi-supervised spectral clustering to cluster. The experimental results prove that SSCCE algorithm has good clustering effect. [ABSTRACT FROM AUTHOR]

Many practical problems in computer science require the knowledge of the most frequently occurring items in a data set. Current state-of-the-art algorithms for frequent items discovery are either fully centralized or rely on node hierarchies which are inflexible and prone to failures in massively distributed systems. In this paper we describe a family of gossip-based algorithms that efficiently approximate the most frequent items in large-scale distributed datasets. We show, both analytically and using real-world datasets, that our algorithms are fast, highly scalable, and resilient to node failures. [ABSTRACT FROM AUTHOR]

A new parallel chaotic Hash function, based on four-dimensional cellular neural network, is proposed in this paper. The message is expanded by iterating chaotic logistic map and then divided into blocks with a length of 512 bits each. All blocks are processed in a parallel mode, which is one of the significant characteristics of the proposed algorithm. Each 512-bit block is divided into four 128-bit sub-blocks, each of which is further separated into four 32-bit values and then the four values are mixed into four new values generated by chaotic cat map. The obtained four new values are performed by the bit-wise exclusive OR operation with four initial values or previously generated four values, and then, they are used as the inputs of cellular neural network. By iterating cellular neural network, another four values as the middle Hash value are generated. The generated values of all blocks are inputted into the compression function to produce the final 128-bit Hash value. Theoretical analysis and computer simulation indicate that the proposed algorithm satisfies the requirements of a secure Hash function. [ABSTRACT FROM AUTHOR]

In this paper, we consider Steiner forest and its generalizations, prize-collecting Steiner forest and k- Steiner forest, when the vertices of the input graph are points in the Euclidean plane and the lengths are Euclidean distances. First, we present a simpler analysis of the polynomial-time approximation scheme (PTAS) of Borradaile et al. (Proceedings of the 49th annual IEEE symposium on foundations of computer science, FOCS, pp. 115-124, ) for the Euclidean Steiner forest problem. This is done by proving a new structural property and modifying the dynamic programming by adding a new piece of information to each dynamic programming state. Next we develop a PTAS for a well-motivated case, i.e., the multiplicative case, of prize-collecting and budgeted Steiner forest. The ideas used in the algorithm may have applications in design of a broad class of bicriteria PTASs; see Sect. 1.3. At the end, we demonstrate why PTASs for these problems can be hard in the general Euclidean case (and thus for PTASs we cannot go beyond the multiplicative case). In fact, this conjecture was later proved by Bateni, Hajiaghayi and Marx ( [abs], ). [ABSTRACT FROM AUTHOR]

This paper presents a learnable tabu search (TS) guided by estimation of distribution algorithm (EDA), called LTS-EDA, for maximum diversity problem. The LTS-EDA introduces knowledge model and can extract knowledge during the search process of TS, and thus it adopts dual or cooperative evolution/search structure, consisting of probabilistic model space in clustered EDA and solution space searched by TS. The clustered EDA, as a learnable constructive method, is used to create a new starting solution, and the simple TS, as an improvement method, attempts to improve the solution created by the clustered EDA in the LTS-EDA. A distinguishing feature of the LTS-EDA is the usage of the clustered EDA with effective linkage learning to guide TS. In the clustered EDA, different clusters (models) focus on different substructures, and the combination of information from different clusters (models) effectively combines substructures. The LTS-EDA is tested on 50 large size benchmark problems with the size ranging from 2,000 to 5,000. Simulation results show that the LTS-EDA is better than the advanced algorithms proposed recently. [ABSTRACT FROM AUTHOR]

The Topological Active Volumes is an active model focused on 3D segmentation tasks. It is based on the 2D Topological Active Nets model and provides information about the surfaces and the inside of the detected objects in the scene. This paper proposes new optimization approaches based on Genetic Algorithms that improve the results of the 3D segmentations and overcome some drawbacks of the model related to parameter tuning or noise conditions. The hybridization of the genetic algorithm with a greedy local search allows the treatment of topological changes in the model, with the possibility of an automatic subdivision of the Topological Active Volume. This combination integrates the advantages of the global and local search procedures in the segmentation process. [ABSTRACT FROM AUTHOR]

Property testing is a rapid growing field in theoretical computer science. It considers the following task: given a function f over a domain D, a property ℘ and a parameter 0< ε<1, by examining function values of f over o(| D|) elements in D, determine whether f satisfies ℘ or differs from any one which satisfies ℘ in at least ε| D| elements. An algorithm that fulfills this task is called a property tester. We focus on tree-likeness of quartet topologies, which is a combinatorial property originating from evolutionary tree construction. The input function is f, which assigns one of the three possible topologies for every quartet over an n-taxon set S. We say that f satisfies tree-likeness if there exists an evolutionary tree T whose induced quartet topologies coincide with f. In this paper, we prove the existence of a set of quartet topologies of error number at least $c{n\choose 4}$ for some constant c>0, and present the first property tester for tree-likeness of quartet topologies. Our property tester makes at most O( n/ ε) queries, and is of one-sided error and non-adaptive. [ABSTRACT FROM AUTHOR]

In its simplest form, the longest common substring problem is to find a longest substring common to two or multiple strings. Using (generalized) suffix trees, this problem can be solved in linear time and space. A first generalization is the k -common substring problem: Given m strings of total length n, for all k with 2≤ k≤ m simultaneously find a longest substring common to at least k of the strings. It is known that the k-common substring problem can also be solved in O( n) time (Hui in Proc. 3rd Annual Symposium on Combinatorial Pattern Matching, volume 644 of Lecture Notes in Computer Science, pp. 230-243, Springer, Berlin, ). A further generalization is the k -common repeated substring problem: Given m strings T, T,..., T of total length n and m positive integers x,..., x, for all k with 1≤ k≤ m simultaneously find a longest string ω for which there are at least k strings $T^{(i_{1})},T^{(i_{2})},\ldots,T^{(i_{k})}$ (1≤ i< i< ⋅⋅⋅< i≤ m) such that ω occurs at least $x_{i_{j}}$ times in $T^{(i_{j})}$ for each j with 1≤ j≤ k. (For x= ⋅⋅⋅= x=1, we have the k-common substring problem.) In this paper, we present the first O( n) time algorithm for the k-common repeated substring problem. Our solution is based on a new linear time algorithm for the k-common substring problem. [ABSTRACT FROM AUTHOR]

Weighted timed automata (WTA), introduced in Alur et al. (Proceedings of HSCC'01, LNCS, vol. 2034, pp. 49-62, Springer, Berlin, ), Behrmann et al. (Proceedings of HSCC'01, LNCS, vol. 2034, pp. 147-161, Springer, Berlin, ) are an extension of Alur and Dill (Theor. Comput. Sci. 126(2):183-235, ) timed automata, a widely accepted formalism for the modelling and verification of real time systems. Weighted timed automata extend timed automata by allowing costs on the locations and edges. There has been a lot of interest Bouyer et al. (Inf. Process. Lett. 98(5):188-194, ), Bouyer et al. (Log. Methods Comput. Sci. 4(2):9, ), Brihaye et al. (Proceedings of FORMATS/FTRTFT'04, LNCS, vol. 3253, pp. 277-292, Springer, Berlin, ), Brihaye et al. (Inf. Comput. 204(3):408-433, ) in studying the model checking problem of weighted timed automata. The properties of interest are written using logic weighted CTL (WCTL), an extension of CTL with costs. It has been shown Bouyer et al. (Log. Methods Comput. Sci. 4(2):9, ) that the problem of model checking WTAs with a single clock using WCTL with no external cost variables is decidable, while 3 clocks render the problem undecidable Bouyer et al. (Inf. Process. Lett. 98(5):188-194, ). The question of 2 clocks is open. In this paper, we introduce a subclass of weighted timed automata called weighted integer reset timed automata (WIRTA) and study the model checking problem. We give a clock reduction technique for WIRTA. Given a WIRTA $\mathcal{A}$ with n≥1 clocks, we show that a single clock WIRTA $\mathcal{A}'$ preserving the paths and costs of $\mathcal{A}$ can be obtained. This gives us the decidability of model checking WIRTA with n≥1 clocks and m≥1 costs using WCTL with no external cost variables. We then show that for a restricted version of WCTL with external cost variables, the model checking problem is undecidable for WIRTA with 3 stopwatch costs and 1 clock. Finally, we show that model checking WTA with 2 clocks and 1 stopwatch cost against WCTL with no external cost variables is undecidable, thereby answering a question that has remained long open. [ABSTRACT FROM AUTHOR]

Image authentication is an important topic in image forensics, which tells whether an image is tampered or not or even tells the tampered regions. To implement image authentication, image hash techniques have been reported recently. In this paper, we investigate existing image hash algorithms, and design an novel image hash based on human being's visual system. In this algorithm, we capture the perceptual characters of the image using Gabor filter which can sense the directions in the image just like human's primary visual cortex. For a given image, we compute the reference scale, direction and block to make sure the final hash can resist against rotation, scale, and translation attacks while maintain the sensitivity to local malicious manipulations. In addition, it has another promising ability to locate the tampered image blocks, and approximately determining the type of tampering methods (delete, add, modify) and the original direction of each block. This ability is very useful in forensics. The experimental results show that the strategy of the reference metrics works quite well and our method is much more effective than the other state of art image hash methods. Moreover, our method can still locate the content-altering changes even undergo some content-preserving manipulations. [ABSTRACT FROM AUTHOR]

The performance of a process engine is one of the key factors that contribute to the successful deployment of systems, based on a service-oriented architecture. A novel service process engine that can be self-configured dynamically is introduced in the paper. It is based on the Jini platform, and leverages of Jini services to provide key functionalities. It automatically maintains the global performance by performing load balancing and configuring the system structure dynamically. A heuristic algorithm is applied to indicate every client’s request with a workload tag after a service process model is designed. Based on workload tags of client requests and the status of available services in the engine, a controller allocates the requests to appropriate services and dynamically reconfigures the engine based on fuzzy control algorithms. Algorithms and the architecture for the engine are discussed in detail; in addition, performance experiments are performed to show the effectiveness and feasibility of the proposed approach. [ABSTRACT FROM AUTHOR]

Given a tree T=( V, E) of n nodes such that each node v is associated with a value-weight pair ( val, w), where value val is a real number and weight w is a non-negative integer, the density of T is defined as $\frac{\sum_{v\in V}{\mathit{val}}_{v}}{\sum_{v\in V}w_{v}}$. A subtree of T is a connected subgraph ( V′, E′) of T, where V′⊆ V and E′⊆ E. Given two integers w and w, the weight-constrained maximum-density subtree problem on T is to find a maximum-density subtree T′=( V′, E′) satisfying w≤∑ w≤ w. In this paper, we first present an O( w n)-time algorithm to find a weight-constrained maximum-density path in a tree T, and then present an O( w n)-time algorithm to find a weight-constrained maximum-density subtree in T. Finally, given a node subset S⊂ V, we also present an O( w n)-time algorithm to find a weight-constrained maximum-density subtree in T which covers all the nodes in S. [ABSTRACT FROM AUTHOR]

The single source shortest paths problem with positive edge weights (SSSPP) is one of the more widely studied problems in operations research and theoretical computer science, on account of its wide applicability to practical situations. This problem was first solved in polynomial time by Dijkstra, who showed that by extracting vertices with the smallest distance from the source and relaxing its outgoing edges, the shortest path to each vertex is obtained. Variations of this general theme have led to a number of algorithms which work well in practice. At the heart of a Dijkstra implementation is the technique used to implement a priority queue. It is well known that using Dijkstra's approach requires Ω( n log n) steps on a graph having n vertices, since it essentially sorts vertices based on their distances from the source. Accordingly, the fastest implementation of Dijkstra's algorithm on a graph with n vertices and m edges should take Ω( m + n · log n) time, and consequently, the Dijkstra procedure for SSSPP using Fibonacci Heaps is optimal in the comparison-based model. In this paper, we introduce a new data structure to implement priority queues called two-level heap (TLH) and a new variant of Dijkstra's algorithm called Phased Dijkstra. We contrast the performance of Dijkstra's algorithm (both the simple and the phased variants) using a number of data structures to implement the priority queue and empirically establish that TLH are far superior to Fibonacci heaps on every graph family considered. It is to be noted that our profiling includes both sparse and dense graphs. [ABSTRACT FROM AUTHOR]

First-Come-First-Served (FCFS) mutual exclusion (ME) is the problem of ensuring that processes attempting to concurrently access a shared resource do so one by one, in a fair order. In this paper, we close the complexity gap between FCFS ME and ME in the asynchronous shared memory model where processes communicate using atomic reads and writes only, and do not fail. Our main result is the first known FCFS ME algorithm that makes O(log N) remote memory references (RMRs) per passage and uses only atomic reads and writes. Our algorithm is also adaptive to point contention. More precisely, the number of RMRs a process makes per passage in our algorithm is Θ(min( k, log N)), where k is the point contention. Our algorithm matches known RMR complexity lower bounds for the class of ME algorithms that use reads and writes only, and beats the RMR complexity of prior algorithms in this class that have the FCFS property. [ABSTRACT FROM AUTHOR]

Initialization of self-organizing maps is typically based on random vectors within the given input space. The implicit problem with random initialization is the overlap (entanglement) of connections between neurons. In this paper, we present a new method of initialization based on a set of self-similar curves known as Hilbert curves. Hilbert curves can be scaled in network size for the number of neurons based on a simple recursive (fractal) technique, implicit in the properties of Hilbert curves. We have shown that when using Hilbert curve vector (HCV) initialization in both classical SOM algorithm and in a parallel-growing algorithm (ParaSOM), the neural network reaches better coverage and faster organization. [ABSTRACT FROM AUTHOR]

In this paper, a novel robust training algorithm of multi-input multi-output recurrent neural network and its application in the fault tolerant control of a robotic system are investigated. The proposed scheme optimizes the gradient type training on basis of three new adaptive parameters, namely, dead-zone learning rate, hybrid learning rate, and normalization factor. The adaptive dead-zone learning rate is employed to improve the steady state response. The normalization factor is used to maximize the gradient depth in the training, so as to improve the transient response. The hybrid learning rate switches the training between the back-propagation and the real-time recurrent learning mode, such that the training is robust stable. The weight convergence and L stability of the algorithm are proved via Lyapunov function and the Cluett's law, respectively. Based upon the theoretical results, we carry out simulation studies of a two-link robot arm position tracking control system. A computed torque controller is designed to provide a specified closed-loop performance in a fault-free condition, and then the RNN compensator and the robust training algorithm are employed to recover the performance in case that fault occurs. Comparisons are given to demonstrate the advantages of the control method and the proposed training algorithm. [ABSTRACT FROM AUTHOR]

This paper deals with direction-of-arrival (DOA) estimation based on iterative searching technique for code-division multiple access signals. It has been shown that the iterative searching technique is more likely to converge to a local maximum, causing errors in DOA estimation. In conjunction with a genetic algorithm for selecting initial search angle, we present an efficient approach to achieve the advantages of iterative DOA estimation with fast convergence and more accuracy estimate over existing conventional spectral searching methods. Finally, several computer simulation examples are provided for illustration and comparison. [ABSTRACT FROM AUTHOR]

The Chained-Cubic Tree (CCT) interconnection network topology was recently proposed as a continuation for the extended efforts in the area of interconnection networks’ performance improvement. This topology, which promises to exhibit the best properties of the hypercube and tree topologies, needs to be deeply investigated in order to evaluate its performance among other interconnection networks’ topologies. This work comes as a complementary effort, in which the load balancing technique is investigated as one of the most important aspects of performance improvement. This paper proposes a new load balancing algorithm on CCT interconnection networks. The proposed algorithm, which is called Hybrid Dynamic Parallel Scheduling Algorithm (HD-PSA), is a combination of two common load balancing strategies; dynamic load balancing and parallel scheduling. The performance of the proposed algorithm is evaluated both, analytically and experimentally, in terms of various performance metrics; including, execution time, load balancing accuracy, communication cost, number of tasks hops, and tasks locality. [ABSTRACT FROM AUTHOR]

The paper presents a novel approach to formal algorithm design for a typical class of discrete optimization problems. Using a concise set of program calculation rules, our approach reduces a problem into subproblems with less complexity based on function decompositions, constructs the problem reduction graph that describes the recurrence relations between the problem and subproblems, from which a provably correct algorithm can be mechanically derived. Our approach covers a large variety of algorithms and bridges the relationship between conventional methods for designing efficient algorithms (including dynamic programming and greedy) and some effective methods for coping with intractability (including approximation and parameterization). [ABSTRACT FROM AUTHOR]

In this paper we establish a fundamental link between the search for weighing matrices constructed from two circulants and the operation of sorting strings, an operation that has been studied extensively in computer science. In particular, we demonstrate that the search for weighing matrices constructed from two circulants using the power spectral density criterion and exploiting structural patterns for the locations of the zeros in candidate solutions, can be viewed as a string sorting problem together with a linear time algorithm to locate common strings in two sorted arrays. This allows us to bring into bear efficient algorithms from the string sorting literature. We also state and prove some new enhancements to the power spectral density criterion, that allow us to treat successfully the rounding error effect and speed up the algorithm. Finally, we use these ideas to find new weighing matrices of order 2 n and weights 2 n – 13, 2 n – 17 constructed from two circulants. [ABSTRACT FROM AUTHOR]

This paper examines the constructive Hausdorff and packing dimensions of Turing degrees. The main result is that every infinite sequence S with constructive Hausdorff dimension dim H( S) and constructive packing dimension dim P( S) is Turing equivalent to a sequence R with dim H( R)≥(dim H( S)/dim P( S))− ε, for arbitrary ε>0. Furthermore, if dim P( S)>0, then dim P( R)≥1− ε. The reduction thus serves as a randomness extractor that increases the algorithmic randomness of S, as measured by constructive dimension. A number of applications of this result shed new light on the constructive dimensions of Turing degrees. A lower bound of dim H( S)/dim P( S) is shown to hold for the Turing degree of any sequence S. A new proof is given of a previously-known zero-one law for the constructive packing dimension of Turing degrees. It is also shown that, for any regular sequence S (that is, dim H( S)=dim P( S)) such that dim H( S)>0, the Turing degree of S has constructive Hausdorff and packing dimension equal to 1. Finally, it is shown that no single Turing reduction can be a universal constructive Hausdorff dimension extractor, and that bounded Turing reductions cannot extract constructive Hausdorff dimension. We also exhibit sequences on which weak truth-table and bounded Turing reductions differ in their ability to extract dimension. [ABSTRACT FROM AUTHOR]

As a framework for simple but basic statistical inference problems we introduce the genetic Most Likely Solution problem, the task of finding a most likely solution (MLS in short) for a given problem instance under some given probability model. Although many MLS problems are NP-hard, we propose for these problems, to study their average-case complexity under their assumed probability models. We show three examples of MLS problems, and show that “message passing algorithms” (e.g., belief propagation) work reasonably well for these problems. Some of the technical results of this paper are from the author’s recent work (Watanabe and Yamamoto in Lecture Notes in Computer Science, vol. 4142, pp. 277–282, , and Onsjö and Watanabe in Lecture Notes in Computer Science, vol. 4288, pp. 507–516, ). [ABSTRACT FROM AUTHOR]

The authors’ $\mathsf{ATR}$ programming formalism is a version of call-by-value $\mathsf{PCF}$ under a complexity-theoretically motivated type system. $\mathsf{ATR}$ programs run in type-2 polynomial-time and all standard type-2 basic feasible functionals are $\mathsf{ATR}$ -definable ( $\mathsf{ATR}$ types are confined to levels 0, 1, and 2). A limitation of the original version of $\mathsf{ATR}$ is that the only directly expressible recursions are tail-recursions. Here we extend $\mathsf{ATR}$ so that a broad range of affine recursions are directly expressible. In particular, the revised $\mathsf{ATR}$ can fairly naturally express the classic insertion- and selection-sort algorithms, thus overcoming a sticking point of most prior implicit-complexity-based formalisms. The paper’s main work is in refining the original time-complexity semantics for $\mathsf{ATR}$ to show that these new recursion schemes do not lead out of the realm of feasibility. [ABSTRACT FROM AUTHOR]

The Longest Common Subsequence (LCS) problem is a classic and well-studied problem in computer science. The LCS problem is a common task in DNA sequence analysis with many applications to genetics and molecular biology. In this paper, we present a new and efficient algorithm for solving the LCS problem for two strings. Our algorithm runs in O(ℛlog log n+ n) time, where ℛ is the total number of ordered pairs of positions at which the two strings match. [ABSTRACT FROM AUTHOR]