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 recent years, artificial intelligence has become an important discipline in the field of computer science. Students, in the absence of basic prior knowledge, may have difficulty tracking materials when they first encounter complex and abstract artificial intelligence algorithms. Numerous researchers and educators point out that the use of simulation systems and software tools to illustrate the dynamic behavior of the algorithm can prove to be an effective solution. The introduction and adoption of new technologies in learning and teaching has evolved rapidly. This conceptual review paper aims to explore the emergence of innovative educational technologies in the teaching and learning of artificial intelligence. The aim of this paper is to analyze the existing representative educational tools for learning topics in the field of artificial intelligence to highlight their characteristics and areas they cover, so that readers can more easily draw conclusions about the possible use of some of the analyzed systems. [ABSTRACT FROM AUTHOR]

The theory of Formal Concept Analysis (FCA) finds diverse applications in fields like knowledge extraction, cognitive concept learning and data mining. The construction of a concept lattice significantly influences the effectiveness of formal concept analysis; hence, the development of high-performance algorithms for concept construction is crucial. In this paper, we introduce a novel algorithm called "Bit-Close" for formal concept construction. Bit-Close leverages bit representation and operations, fundamental to computer science, to enhance the In-Close algorithm. Furthermore, we explore the parallel method of Bit-Close. Our experimental results, obtained from multiple public and random datasets, demonstrate that Bit-Close outperforms In-Close by approximately 20% and is significantly better than other competing algorithms. [ABSTRACT FROM AUTHOR]

In our paper, we consider the following general problems: check feasibility, count the number of feasible solutions, find an optimal solution, and count the number of optimal solutions in P ∩ Z n , assuming that P is a polyhedron, defined by systems A x ≤ b or A x = b , x ≥ 0 with a sparse matrix A. We develop algorithms for these problems that outperform state-of-the-art ILP and counting algorithms on sparse instances with bounded elements in terms of the computational complexity. Assuming that the matrix A has bounded elements, our complexity bounds have the form s O (n) , where s is the minimum between numbers of non-zeroes in columns and rows of A, respectively. For s = o (log n) , this bound outperforms the state-of-the-art ILP feasibility complexity bound (log n) O (n) , due to Reis & Rothvoss (in: 2023 IEEE 64th Annual symposium on foundations of computer science (FOCS), IEEE, pp. 974–988). For s = ϕ o (log n) , where ϕ denotes the input bit-encoding length, it outperforms the state-of-the-art ILP counting complexity bound ϕ O (n log n) , due to Barvinok et al. (in: Proceedings of 1993 IEEE 34th annual foundations of computer science, pp. 566–572, https://doi.org/10.1109/SFCS.1993.366830, 1993), Dyer, Kannan (Math Oper Res 22(3):545–549, https://doi.org/10.1287/moor.22.3.545, 1997), Barvinok, Pommersheim (Algebr Combin 38:91–147, 1999), Barvinok (in: European Mathematical Society, ETH-Zentrum, Zurich, 2008). We use known and new methods to develop new exponential algorithms for Edge/Vertex Multi-Packing/Multi-Cover Problems on graphs and hypergraphs. This framework consists of many different problems, such as the Stable Multi-set, Vertex Multi-cover, Dominating Multi-set, Set Multi-cover, Multi-set Multi-cover, and Hypergraph Multi-matching problems, which are natural generalizations of the standard Stable Set, Vertex Cover, Dominating Set, Set Cover, and Maximum Matching problems. [ABSTRACT FROM AUTHOR]

We consider the weighted k-set packing problem, where, given a collection S of sets, each of cardinality at most k, and a positive weight function w : S → Q > 0 , the task is to find a sub-collection of S consisting of pairwise disjoint sets of maximum total weight. As this problem does not permit a polynomial-time o (k log k) -approximation unless P = N P (Hazan et al. in Comput Complex 15:20–39, 2006. https://doi.org/10.1007/s00037-006-0205-6), most previous approaches rely on local search. For twenty years, Berman's algorithm SquareImp (Berman, in: Scandinavian workshop on algorithm theory, Springer, 2000. https://doi.org/10.1007/3-540-44985-X%5f19), which yields a polynomial-time k + 1 2 + ϵ -approximation for any fixed ϵ > 0 , has remained unchallenged. Only recently, it could be improved to k + 1 2 - 1 63 , 700 , 993 by Neuwohner (38th International symposium on theoretical aspects of computer science (STACS 2021), Leibniz international proceedings in informatics (LIPIcs), 2021. https://doi.org/10.4230/LIPIcs.STACS.2021.53). In her paper, she showed that instances for which the analysis of SquareImp is almost tight are "close to unweighted" in a certain sense. But for the unit weight variant, the best known approximation guarantee is k + 1 3 + ϵ (Fürer and Yu in International symposium on combinatorial optimization, Springer, 2014. https://doi.org/10.1007/978-3-319-09174-7%5f35). Using this observation as a starting point, we conduct a more in-depth analysis of close-to-tight instances of SquareImp. This finally allows us to generalize techniques used in the unweighted case to the weighted setting. In doing so, we obtain approximation guarantees of k + ϵ k 2 , where lim k → ∞ ϵ k = 0 . On the other hand, we prove that this is asymptotically best possible in that local improvements of logarithmically bounded size cannot produce an approximation ratio below k 2 . [ABSTRACT FROM AUTHOR]

Many researchers have recently considered patients' health and provided an optimal and appropriate solution. With the advent of technologies such as cloud computing, Internet of Things and 5G, information can be exchanged faster and more securely. The Internet of things (IoT) offers many opportunities in the field of e-health. This technology can improve health services and lead to various innovations in this regard. Using cloud computing and IoT in this process can significantly improve the monitoring of patients. Therefore, it is important to provide a useful method in the medical industry and computer science to monitor the status of patients using connected sensors. Thus, due to its optimal efficiency, speed, and accuracy of data processing and classification, the use of cloud computing to process the data collected from remote patient sensors and IoT platform has been suggested. In this paper, a prioritization system is used to prioritize sensitive information in IoT, and in cloud computing, LSTM deep neural network is applied to classify and monitor patients' condition remotely, which can be considered as an important innovative aspect of this paper. Sensor data in the IoT platform is sent to the cloud with the help of the 5th generation Internet. The core of cloud computing uses the LSTM (long short-term memory) deep neural network algorithm. By simulating the proposed method and comparing the obtained results with other methods, it is observed that the accuracy of the proposed method is 97.13%, which has been improved by 10.41% in average over the other methods. [ABSTRACT FROM AUTHOR]

Knowledge graph has wide applications in the field of computer science. In the knowledge service environment, the information is large and explosive, and it is difficult to find knowledge of common phenomena. The urban traffic knowledge graph is a knowledge system that formally describes urban traffic concepts, entities and their interrelationships. It has great application potential in application scenarios such as user travel, route planning, and urban planning. This paper first defines the urban traffic knowledge graph and the star subgraph query of the urban traffic knowledge graph. Then, the road network data and trajectory data are collected to extract the urban traffic knowledge, and the urban traffic knowledge graph is constructed with this knowledge. Finally, a star subgraph query algorithm on the urban traffic knowledge graph is proposed. The discussion of the star subgraph query mode gives the corresponding application scenarios of our method in the urban traffic knowledge graph. Experimental results verify the performance advantages of this method. [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]

This problem can benefit from machine learning techniques, thanks to their capability of finding "hidden" relationships among the available data and therefore generate placement actions. In society, data producers and data consumers continuously exchange their roles. Since the very beginning, there has been a fruitful exchange between machine learning (ML) and optimization. [Extracted from the article]

Correction to: Multimedia Systems https://doi.org/10.1007/s00530-021-00858-7 In the original publication of the article, the third author affiliation was erroneously published; the correct affiliation should read as: School of Computer Science, University of Technology Sydney, Sydney, Australia. Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. [Extracted from the article]

Identification of influential spreaders is still a challenging issue in network science. Therefore, it attracts increasing attention from both computer science and physical societies, and many algorithms to identify influential spreaders have been proposed so far. Degree centrality, as the most widely used neighborhood-based centrality, was introduced into the network world to evaluate the spreading ability of nodes. However, degree centrality always assigns too many nodes with the same value, so it leads to the problem of resolution limitation in distinguishing the real influences of these nodes, which further affects the ranking efficiency of the algorithm. The k-shell decomposition method also faces the same problem. In order to solve the resolution limit problem, we propose a high-resolution index combining both degree centrality and the k-shell decomposition method. Furthermore, based on the proposed index and the well-known gravity law, we propose an improved gravity model to measure the importance of nodes in propagation dynamics. Experiments on ten real networks show that our model outperforms most of the state-of-the-art methods. It has a better performance in terms of ranking performance as measured by the Kendall's rank correlation, and in terms of ranking efficiency as measured by the monotonicity value. [ABSTRACT FROM AUTHOR]