Search

The 33rd International Workshop On Combinatorial Algorithms (IWOCA 2022) was held at the University of Trier in Germany. This workshop covers a wide range of topics related to combinatorial algorithms. The special issue of the journal Algorithmica contains extended versions of selected papers from IWOCA 2022, which were nominated by the Program Committee and underwent a rigorous reviewing process. The special issue includes nine papers on various topics such as perfect matchings, algorithmic questions, and winner determination algorithms. One paper was chosen as the Best Paper of IWOCA 2022 and another as the Best Student Paper. The special issue is recommended for readers interested in exploring more papers from IWOCA 2022. [Extracted from the article]

The 26th International Conference on Developments in Language Theory (DLT 2022) took place in Tampa, Florida, USA in May 2022. The conference, organized by the Department of Mathematics and Statistics of the University of South Florida, focused on formal languages and automata. This special issue of Theory of Computing Systems contains extended versions of selected papers presented at DLT 2022, as well as papers based on invited talks. The papers cover a range of topics in the field of formal languages and automata, and underwent a rigorous review process. The preface expresses gratitude to the authors and reviewers involved in the publication. [Extracted from the article]

In this paper we study the classical problem of throughput maximization. In this problem we have a collection J of n jobs, each having a release time r j , deadline d j , and processing time p j . They have to be scheduled non-preemptively on m identical parallel machines. The goal is to find a schedule which maximizes the number of jobs scheduled entirely in their [ r j , d j ] window. This problem has been studied extensively (even for the case of m = 1 ). Several special cases of the problem remain open. Bar-Noy et al. (Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1–4, 1999, Atlanta, Georgia, USA, pp. 622–631. ACM, 1999, https://doi.org/10.1145/301250.301420) presented an algorithm with ratio 1 - 1 / (1 + 1 / m) m for m machines, which approaches 1 - 1 / e as m increases. For m = 1 , Chuzhoy et al. (42nd Annual Symposium on Foundations of Computer Science (FOCS) 2001, 14–17 October 2001, Las Vegas, Nevada, USA, pp. 348–356. IEEE Computer Society, 2001) presented an algorithm with approximation with ratio 1 - 1 e - ε (for any ε > 0 ). Recently Im et al. (SIAM J Discrete Math 34(3):1649–1669, 2020) presented an algorithm with ratio 1 - 1 / e + ε 0 for some absolute constant ε 0 > 0 for any fixed m. They also presented an algorithm with ratio 1 - O (log m / m) - ε for general m which approaches 1 as m grows. The approximability of the problem for m = O (1) remains a major open question. Even for the case of m = 1 and c = O (1) distinct processing times the problem is open (Sgall in: Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012. Proceedings, pp 2–11, 2012). In this paper we study the case of m = O (1) and show that if there are c distinct processing times, i.e. p j 's come from a set of size c, then there is a randomized (1 - ε) -approximation that runs in time O (n m c 7 ε - 6 log T) , where T is the largest deadline. Therefore, for constant m and constant c this yields a PTAS. Our algorithm is based on proving structural properties for a near optimum solution that allows one to use a dynamic programming with pruning. [ABSTRACT FROM AUTHOR]

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]

The approximate uniform sampling of graph realizations with a given degree sequence is an everyday task in several social science, computer science, engineering etc. projects. One approach is using Markov chains. The best available current result about the well-studied switch Markov chain is that it is rapidly mixing on P-stable degree sequences (see DOI:10.1016/j.ejc.2021.103421). The switch Markov chain does not change any degree sequence. However, there are cases where degree intervals are specified rather than a single degree sequence. (A natural scenario where this problem arises is in hypothesis testing on social networks that are only partially observed.) Rechner, Strowick, and Müller–Hannemann introduced in 2018 the notion of degree interval Markov chain which uses three (separately well studied) local operations (switch, hinge-flip and toggle), and employing on degree sequence realizations where any two sequences under scrutiny have very small coordinate-wise distance. Recently, Amanatidis and Kleer published a beautiful paper (DOI:10.4230/LIPIcs.STACS.2023.7), showing that the degree interval Markov chain is rapidly mixing if the sequences are coming from a system of very thin intervals which are centered not far from a regular degree sequence. In this paper, we substantially extend their result, showing that the degree interval Markov chain is rapidly mixing if the intervals are centered at P-stable degree sequences. [ABSTRACT FROM AUTHOR]

Deep neural networks are extensively used in text mining and Natural Language Processing is to enable computers to understand, analyze, and generate natural language data, such as text or speech, but semantic resources, such as taxonomies and ontologies, are not fully included in deep learning. In this paper, we use Deep Convolutional Neural Network (Deep CNN) to classify research papers using the Computer Science Ontology, an ontology of research areas in the field of computer science. It takes as input the abstract and keywords of a particular research paper and returns the relevant research topic. To evaluate our ontology, we used a gold standard dataset that includes research articles. To further improve text classification results, we propose to design a Deep CNN model. We then used ontology matching to reduce the classes and get better results. Experimental results show that the proposed approach outperforms the one with the highest precision, recall, and F1-score. [ABSTRACT FROM AUTHOR]

Computer system resilience refers to the ability of a computer system to continue functioning even in the face of unexpected events or disruptions. These disruptions can be caused by a variety of factors, such as hardware failures, software glitches, cyber attacks, or even natural disasters. Modern computational environments need applications that can recover quickly from major disruptions while also being environmentally sustainable. Balancing system resilience with energy efficiency is challenging, as efforts to improve one can harm the other. This paper presents a method to enhance disaster survivability in microservice architectures, particularly those using Kubernetes in cloud-based environments, focusing on optimizing electrical energy use. Aiming to save energy, our work adopt the consolidation strategy that means grouping multiple microservices on a single host. Our aproach uses a widely adopted analytical model, the Generalized Stochastic Petri Net (GSPN). GSPN are a powerful modeling technique that is widely used in various fields, including engineering, computer science, and operations research. One of the primary advantages of GSPN is its ability to model complex systems with a high degree of accuracy. Additionally, GSPN allows for the modeling of both logical and stochastic behavior, making it ideal for systems that involve a combination of both. Our GSPN models compute a number of metrics such as: recovery time, system availability, reliability, Mean Time to Failure, and the configuration of cloud-based microservices. We compared our approach against others focusing on survivability or efficiency. Our approach aligns with Recovery Time Objectives during sudden disasters and offers the fastest recovery, requiring 9% less warning time to fully recover in cases of disaster with alert when compared to strategies with similar electrical consumption. It also saves about 27% energy compared to low consolidation strategies and 5% against high consolidation under static conditions. [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]

Computer science is often integrated within early childhood education (ECE) through the use of educational robots. This requires adequate preparation of ECE teachers to program and debug, which can be done with scaffolding. In this paper, we use a QUANT + qual mixed method approach incorporating lag sequential analysis, ICAP framework coding, sentiment analysis, and supplementary qualitative analysis. Students tended to engage more with tasks in the revision and evaluation phases than in the exploration phase, and became less dependent on scaffolding prompts and more competent in debugging, as debugging task complexity increased. This study addresses a key gap in the scaffolding literature in that it examined learners' interactions with scaffolding for evidence of decreased reliance on scaffolding. [ABSTRACT FROM AUTHOR]

In the present paper, we propose a new approach on 'distributed systems': the processes are represented through total orders and the communications are characterized by means of biorders. The resulting distributed systems capture situations met in various fields (such as computer science, economics and decision theory). We investigate questions associated to the numerical representability of order structures, relating concepts of economics and computing to each other. The concept of 'quasi-finite partial orders' is introduced as a finite family of chains with a communication between them. The representability of this kind of structure is studied, achieving a construction method for a finite (continuous) Richter–Peleg multi-utility representation. [ABSTRACT FROM AUTHOR]

One of the most widely referenced Swarm Intelligence (SI) algorithms is the Grey Wolf Optimizer (GWO), which is based on the pack hunting and natural leadership organization of grey wolves. The GWO algorithm offers several significant benefits, including simple implementation, rapid convergence, and superior convergence outcomes, leading to its effective application in diverse fields for solving optimization issues. Consequently, the GWO has rapidly garnered substantial research interest and a broad audience across numerous areas. To better understand the literature on this algorithm, this review paper aims to consolidate and summarize research publications that utilized the GWO. The paper begins with a concise introduction to the GWO, providing insight into its natural establishment and conceptual framework for optimization. It then lays out the theoretical foundation and key procedures involved in the GWO, following which it comprehensively examines the most recent iterations of the algorithm and categorizes them into parallel, modified, and hybridized variations. Subsequently, the primary applications of the GWO are thoroughly explored, spanning various fields such as computer science, engineering, energy, physics and astronomy, materials science, environmental science, and chemical engineering, among others. This review paper concludes by summarizing the key arguments in favour of GWO and outlining potential lines of inquiry in the future research. [ABSTRACT FROM AUTHOR]

Portfolio optimization has been studied extensively by researchers in computer science and finance, with new and novel work frequently published. Traditional methods, such as quadratic programming, are not computationally effective for solving complex portfolio models. For example, portfolio models with constraints that introduce nonlinearity and non-convexity (such as boundary constraints and cardinality constraints) are NP-Hard. As a result, researchers often use meta-heuristic approaches to approximate optimal solutions in an efficient manner. This paper conducts a comprehensive review of over 140 papers that have applied evolutionary and swarm intelligence algorithms to the portfolio optimization problem. These papers are categorized by the type of portfolio optimization problem considered, i.e., unconstrained or constrained, and are further categorized by single-objective and multi-objective approaches. Furthermore, the various portfolio models used, as well as the constraints, objectives, and properties in which they differ, are also discussed in a detailed analysis. Based on the findings of the reviewed work, guidance for future research in portfolio optimization is given. Possible areas for future work include dynamic portfolio optimization, predictive pricing, the further investigation of multi-objective approaches. [ABSTRACT FROM AUTHOR]

Open peer review is a growing trend in academic publications. Public access to peer review data can benefit both the academic and publishing communities. It also serves as a great support to studies on review comment generation and further to the realization of automated scholarly paper review. However, most of the existing peer review datasets do not provide data that cover the whole peer review process. Apart from this, their data are not diversified enough as the data are mainly collected from the field of computer science. These two drawbacks of the currently available peer review datasets need to be addressed to unlock more opportunities for related studies. In response, we construct MOPRD, a multidisciplinary open peer review dataset. This dataset consists of paper metadata, multiple version manuscripts, review comments, meta-reviews, author's rebuttal letters, and editorial decisions. Moreover, we propose a modular guided review comment generation method based on MOPRD. Experiments show that our method delivers better performance as indicated by both automatic metrics and human evaluation. We also explore other potential applications of MOPRD, including meta-review generation, editorial decision prediction, author rebuttal generation, and scientometric analysis. MOPRD is a strong endorsement for further studies in peer review-related research and other applications. [ABSTRACT FROM AUTHOR]

The security that resides in the public-key cryptosystems relies on the presumed computational hardness of mathematical problems behind the systems themselves (e.g. the semiprime factorization problem in the RSA cryptosystem), that is because there is not known any polynomial time (classical) algorithm to solve them. The paper focuses on the computing paradigm of virus machines within the area of Unconventional Computing and Natural Computing. Virus machines, which incorporate concepts of virology and computer science, are considered as number computing devices with the environment. The paper designs a virus machine that solves a generalization of the semiprime factorization problem and verifies it formally. [ABSTRACT FROM AUTHOR]

This document is a guest editorial for the special section on SEFM 2020 and 2021 in the journal Software & Systems Modeling. The International Conference on Software Engineering and Formal Methods (SEFM) aims to bring together practitioners and researchers to advance the state of the art in formal methods and their application in the software industry. This special section includes selected papers from SEFM 2020 and 2021, which were held virtually during the COVID pandemic. Each article in this section has undergone rigorous peer review and has been revised and extended compared to its conference version. The selected papers cover topics such as embedded software portability and verification, nontermination inference, quantitative modeling and analysis of BDI agents, lazy model checking for recursive state machines, P-stable abstractions of hybrid systems, fairness and guarantees for extended bounded response LTL+P synthesis, counterexample classification, analyzing the impact of human errors on interactive service robotic scenarios, and active model learning of stochastic reactive systems. [Extracted from the article]

A drug molecule is a substance that changes an organism's mental or physical state. Every approved drug has an indication, which refers to the therapeutic use of that drug for treating a particular medical condition. While the Large Language Model (LLM), a generative Artificial Intelligence (AI) technique, has recently demonstrated effectiveness in translating between molecules and their textual descriptions, there remains a gap in research regarding their application in facilitating the translation between drug molecules and indications (which describes the disease, condition or symptoms for which the drug is used), or vice versa. Addressing this challenge could greatly benefit the drug discovery process. The capability of generating a drug from a given indication would allow for the discovery of drugs targeting specific diseases or targets and ultimately provide patients with better treatments. In this paper, we first propose a new task, the translation between drug molecules and corresponding indications, and then test existing LLMs on this new task. Specifically, we consider nine variations of the T5 LLM and evaluate them on two public datasets obtained from ChEMBL and DrugBank. Our experiments show the early results of using LLMs for this task and provide a perspective on the state-of-the-art. We also emphasize the current limitations and discuss future work that has the potential to improve the performance on this task. The creation of molecules from indications, or vice versa, will allow for more efficient targeting of diseases and significantly reduce the cost of drug discovery, with the potential to revolutionize the field of drug discovery in the era of generative AI. [ABSTRACT FROM AUTHOR]

The concept of book embedding, originating in computer science, has found extensive applications in various problem domains. A book embedding of a graph G involves arranging the vertices of G in an order along a line and assigning the edges to one or more half-planes. The page number of a graph is the smallest possible number of half-planes for any book embedding of the graph. Determining the page number is a key aspect of book embedding and carries significant importance. This paper aims to investigate the non-trivial lower bound of the page number for both a graph G and a random graph G ∈ G (n , p) by incorporating two seemingly unrelated concepts: edge-arboricity and Euler's Formula. Our analysis reveals that for a graph G, which is not a path, p n (G) ≥ ⌈ 1 3 a 1 (G) ⌉ , where a 1 (G) denotes the edge-arboricity of G, and for an outerplanar graph, the lower bound is optimal. For G ∈ G (n , p) , p n (G) ≥ ⌈ 1 6 n p (1 - o (1)) ⌉ with high probability, as long as c n ≤ p ≤ 3 (n - 1) 2 n log n . [ABSTRACT FROM AUTHOR]

Trust can be considered as a multidisciplinary concept, which is strongly related to the context and it falls in different fields such as Philosophy, Psychology or Computer Science. Trust is fundamental in every relationship, because without it, an entity will not interact with other entities. This aspect is very important especially in the Internet of Things (IoT), where many entities produced by different vendors and created for different purposes have to interact among them through the internet often under uncertainty. Trust can overcome this uncertainty, creating a strong basis to ease the process of interaction among these entities. We believe that considering trust in the IoT is fundamental, and in order to implement it in any IoT entity, it is fundamental to consider it through the whole System Development Life Cycle. In this paper, we propose an analysis of different works that consider trust for the IoT. We will focus especially on the analysis of frameworks that have been developed in order to include trust in the IoT. We will make a classification of them providing a set of parameters that we believe are fundamental in order to properly consider trust in the IoT. Thus, we will identify important aspects to be taken into consideration when developing frameworks that implement trust in the IoT, finding gaps and proposing possible solutions. [ABSTRACT FROM AUTHOR]

Our world is turbulent: ecological, social, political, technological, economic, and competitive business environments change constantly. Consumers have changing preferences, learn, build trust in brands, adopt new products, and are persuaded by advertising. Firms innovate and engage in and respond to competition. Exogenous events, such as changes in economic conditions and regulations, as well as human crises, also cause major shifts in markets. This special issue focuses on novel Marketing data and modern methodologies from different fields (e.g., Operations Research (OR), Statistics, Econometrics, and Computer Science), which help firms understand, utilize, and respond to market dynamics more efficiently. Here we propose a framework comprising analytical methods and data for dynamic markets that is useful for structuring research in this domain. Next, we summarize the history of the Marketing/OR interface. We highlight studies at the Marketing/OR interface from the last decade focusing specifically on dynamic markets and use our proposed framework to identify trends and gaps in the extant literature. After that, we present and summarize the papers of the current special issue and their contributions to the field against the backdrop of our framework and the trends in the literature. Finally, we conclude and discuss which future Marketing/OR research could tackle important issues in dynamic markets. [ABSTRACT FROM AUTHOR]

The performance of a permissioned blockchain, namely, Hyperledger Fabric, is modeled and analyzed in a quantitative manner in this paper. Various types of nodes contribute to the performance of Hyperledger Fabric, and each of those is modeled and tracked along the operational flow of the permissioned blockchain. There are nodes for endorsement, ordering, and commitment to realize the due decentralized network operations. A quantitative model for each type of nodes has been proposed in Ke and Park (Performance study on various Hyperledger Fabric node types and transaction flow, IEEE BCCA, 2021) along with numerical analysis. Each type of the nodes is characterized in terms of transaction/block queue size and waiting time, and the transaction/block arrival rates and the transaction/block service rates are considered for simulation purposes. The analysis is extended beyond the analysis in Ke and Park (Performance study on various Hyperledger Fabric node types and transaction flow, IEEE BCCA, 2021) in this paper to particularly demonstrate how the arrival rates and the service rates co-influence the performance and how the number of channels impacts the performance, in order to ultimately facilitate a more dynamic way of optimization, taking the co-relation across different types of nodes into account. The major contribution of this paper to the field of computer science by creating a series of queuing models to evaluate the performance of different types of nodes: Chaincode Execution and Endorsement, Block Creation and Delivery, Transaction Validation and Block Committing, and Transaction Processing. [ABSTRACT FROM AUTHOR]

The words "Programming is the second literacy" were coined more than 40 years ago [13], but never came to life. The paper develops and details that old slogan by proposing that the mainstream mathematics education in schools should merge with education in computer science/programming. Of course, this means a deep structural reform of school mathematics education. We are not talking about adapting the 20th century mathematics to the 21st century—as it outlined in [10, 19], we mean the 21st century mathematics education for the 21st century mathematics. To the best of our knowledge, this paper is perhaps the first known attempt to start a proper feasibility study for this reform. The scope of the paper does not allow us to touch the delicate socio-political (and financial) sides of the reform, we are looking only at general curricular and didactic aspects and possible directions of the reform. In particular, we indicate approaches to development of a Domain Specifiic Language (DSL) as a basis for all programming aspects of a new course. [ABSTRACT FROM AUTHOR]

With the increase interest and number of the users in Social media, the file handling has also increased. To manage the load, cloud servers are being used by the service providers. To identify and cluster file is a difficult task that is important in the domain of computer science. Various traditional approaches for identification exists that uses design features. The problem with these methods is get that they can be easily spoofed. To resolve the issue, in this paper, a hybrid algorithm combining the features of Random Forest with AdaBoost is proposed. The algorithm Internet of Thing (IoT) data file formatting (IDFF) classifies data as (text, image, audio and video) and gives better accuracy. Our proposed research obtains better Accuracy (93%), Precision (95%), Recall (95%), F-Measure (95%), and G-Mean (96%). [ABSTRACT FROM AUTHOR]

Let d-claw (or d-star) stand for K 1 , d , the complete bipartite graph with 1 and d ≥ 1 vertices on each part. The d-claw vertex deletion problem, d -claw-vd, asks for a given graph G and an integer k if one can delete at most k vertices from G such that the resulting graph has no d-claw as an induced subgraph. Thus, 1 -claw-vd and 2 -claw-vd are just the famous vertex cover problem and the cluster vertex deletion problem, respectively. In this paper, we strengthen a hardness result recently proved in Jena and Subramani (in: Du, Du, Wu, and Zhu (eds) Theory and applications of models of computation - 17th annual conference, TAMC 2022, Tianjin, China, September 16–18, 2022, Proceedings, 2022), by showing that cluster vertex deletion remains NP -complete even when restricted to planar bipartite graphs of maximum degree 3 and arbitrary large girth. Moreover, for every d ≥ 3 , we show that d -claw-vd is NP -complete even when restricted to planar bipartite graphs of maximum degree d. These hardness results are optimal with respect to degree constraint. By extending the hardness result in Bonomo-Braberman et al (in: Computing and combinatorics - 26th international conference, COCOON 2020, Proceedings, Lecture Notes in Computer Science, vol 12273, Springer, 2020, pp 14–26, 2020), we show that, for every d ≥ 3 , d -claw-vd is NP -complete even when restricted to split graphs without (d + 1) -claws, and split graphs of diameter 2. On the positive side, we prove that d -claw-vd is polynomially solvable on what we call d-block graphs, a class properly contains all block graphs. This result extends the polynomial-time algorithm in Cao et al (Theor Comput Sci, 2018) for 2 -claw-vd on block graphs to d -claw-vd for all d ≥ 2 and improves the polynomial-time algorithm proposed by Bonomo-Brabeman et al. for (unweighted) 3 -claw-vd on block graphs to 3-block graphs. [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]

What is computational explanation? Many accounts treat it as a kind of causal explanation. I argue against two more specific versions of this view, corresponding to two popular treatments of causal explanation. The first holds that computational explanation is mechanistic, while the second holds that it is interventionist. However, both overlook an important class of computational explanations, which I call limitative explanations. Limitative explanations explain why certain problems cannot be solved computationally, either in principle or in practice. I argue that limitative explanations are not plausibly understood in either mechanistic or interventionist terms. One upshot of this argument is that there are causal and non-causal kinds of computational explanation. I close the paper by suggesting that both are grounded in the notion of computational implementation. [ABSTRACT FROM AUTHOR]

This article argues that existing approaches to programming ethical AI fail to resolve a serious moral-semantic trilemma, generating interpretations of ethical requirements that are either too semantically strict, too semantically flexible, or overly unpredictable. This paper then illustrates the trilemma utilizing a recently proposed 'general ethical dilemma analyzer,' GenEth. Finally, it uses empirical evidence to argue that human beings resolve the semantic trilemma using general cognitive and motivational processes involving 'mental time-travel,' whereby we simulate different possible pasts and futures. I demonstrate how mental time-travel psychology leads us to resolve the semantic trilemma through a six-step process of interpersonal negotiation and renegotiation, and then conclude by showing how comparative advantages in processing power would plausibly cause AI to use similar processes to solve the semantic trilemma more reliably than we do, leading AI to make better moral-semantic choices than humans do by our very own lights. [ABSTRACT FROM AUTHOR]

In this paper, we study quantum Ordered Binary Decision Diagrams(OBDD ) model; it is a restricted version of read-once quantum branching programs, with respect to "width" complexity. It is known that the maximal gap between deterministic and quantum complexities is exponential. But there are few examples of functions with such a gap. We present a new technique ("reordering") for proving lower bounds and upper bounds for OBDD with an arbitrary order of input variables if we have similar bounds for the natural order. Using this transformation, we construct a total function REQ such that the deterministic OBDD complexity of it is at least 2 Ω (n / log n) , and the quantum OBDD complexity of it is at most O (n 2 / log n) . It is the biggest known gap for explicit functions not representable by OBDD s of a linear width. Another function(shifted equality function) allows us to obtain a gap 2 Ω (n) vs O (n 2) . Moreover, we prove the bounded error quantum and probabilistic OBDD width hierarchies for complexity classes of Boolean functions. Additionally, using "reordering" method we extend a hierarchy for read-k-times Ordered Binary Decision Diagrams ( k - OBDD ) of polynomial width, for k = o (n / log 3 n) . We prove a similar hierarchy for bounded error probabilistic k - OBDD s of polynomial, superpolynomial and subexponential width. The extended abstract of this work was presented on International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8 – 12, 2017 Khadiev and Khadieva (2017) [ABSTRACT FROM AUTHOR]

This document is a guest editorial for a special section in the journal "Software & Systems Modeling." The special section features revised and extended versions of selected papers from the 20th International Conference on Software Engineering and Formal Methods (SEFM'22), which was held in Berlin, Germany in September 2022. The SEFM conference series aims to advance the state of the art in formal methods and their integration into practical software engineering methods and tools. The special section includes papers on topics such as user-centric analysis, automated generation of finite automata, formal specifications of smart contracts, distributed verification of programs, and abstraction-based verification of neural networks. The authors express their gratitude to the authors and reviewers for their contributions and thank Springer for their support in publishing the special section. [Extracted from the article]

Handwriting recognition and analysis has been an active area of research in the last two decades. Handwriting analysis is being studied in various fields of science, such as graphology, neurology, psychology, and computer science. Furthermore, automated handwriting analysis has several applications, including forensic, security, medical, and disease prediction. This paper presents the most recent handwriting analysis techniques and advancements available in the literature for age and gender classification/detection. Different steps, including feature extraction and classification, frequently used in the literature for age and gender detection, are discussed, and the presented works are classified according to the applied feature extraction and classification methods. The online and offline benchmark databases are also reviewed. We used a text mining technique to perform a quantitative content analysis of the presented research and better understand the co-occurrence network diagrams of age and gender classification/detection. This study is a valuable resource that provides new research directions to students and researchers interested in this field for further research and investigation. [ABSTRACT FROM AUTHOR]

Inverting a matrix is time-consuming, and many works focus on accelerating the inversion of a single large matrix by GPU. However, the problem of parallelizing the inversion of a large number of small matrices has received little attention. These problems are widely applied in computer science, including accelerating cryptographic algorithms and image processing algorithms. In this paper, we propose a Revised In-Place Inversion algorithm for inverting a large number of small matrices on the CUDA platform, which adopts a more refined parallelization scheme and outperforms other algorithms, achieving a speedup of up to 20.9572 times over the batch matrix inverse kernel in CUBLAS. Additionally, we found that there is an upper bound on the input data size for each GPU device, and the performance will degrade if the input data size is too large. Therefore, we propose the Saturation Size Curve based on this finding to divide matrices into batches and improve the algorithm performance. Experimental results show that this strategy increases the algorithm's performance by 1.75 times and effectively alleviates the problem of performance degradation. [ABSTRACT FROM AUTHOR]

Image recognition based on computers is something human beings have been working on for many years. It is one of the most difficult tasks in the field of computer science, and improvements to this system are made when we speak. In this paper, we propose a methodology to automatically propose an appropriate title and add a specific sound to the image. Two models have been extensively trained and combined to achieve this effect. Sounds are recommended based on the image scene and the headings are generated using a combination of natural language processing and state-of-the-art computer vision models. A Top 5 accuracy of 67% and a Top 1 accuracy of 53% have been achieved. It is also worth mentioning that this is also the first model of its kind to make this forecast. [ABSTRACT FROM AUTHOR]

In this paper, we formalize precisely the sense in which the application of a cellular automaton to partial configurations is a natural extension of its local transition function through the categorical notion of Kan extension. In fact, the two possible ways to do such an extension and the ingredients involved in their definition are related through Kan extensions in many ways. These relations provide additional links between computer science and category theory, and also give a new point of view on the famous Curtis–Hedlund theorem of cellular automata from the extended topological point of view provided by category theory. These links also allow to relatively easily generalize concepts pioneered by cellular automata to arbitrary kinds of possibly evolving spaces. No prior knowledge of category theory is assumed for the most part. [ABSTRACT FROM AUTHOR]

Linear equations are commonly used in various fields of science such as engineering, physics, computer science, technology, business, and economics. A recent and promising extension of fuzzy set theory is represented by hesitant fuzzy sets (HFSs). The promising characteristic of HFSs is that they permit to model a type of imprecise human knowledge that cannot be captured by classical fuzzy sets. As no research has been performed in the field of hesitant fuzzy equations, in this paper, hesitant parametric fuzzy set (HPFS) is introduced and operations on this set are investigated. Also, fully hesitant parametric fuzzy equation (FHPFE) in form of a x = b is solved for the first time in which a and b are known HPFS and x is an unknown HPFS. Then, the existence of different approximate solutions of FHPFE is investigated and proved. Finally, some numerical examples are presented that verify the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

A control flow graph (CFG) is a type of directed graph that shows the execution paths of the programs. It is a mathematical structure that is actively used in software testing. It can be constructed from the source or the executable of the program. Construction of the CFG from the executable is called CFG reconstruction. CFG reconstruction is used in many areas of computer science, like reverse engineering, security analysis, and worst-case execution time analysis. CFG reconstruction can be performed using a static, dynamic, or hybrid approach. This paper introduces a new CFG reconstruction tool named Turna that uses a hybrid approach. Turna works on programs that are compiled for RISC-V architecture. One of the main phases of CFG reconstruction is basic block detection. Therefore, together with Turna, a new rule set and an algorithm for basic block detection from RISC-V executables are also introduced. The CFG reconstruction process and the outputs of Turna are shared and discussed. [ABSTRACT FROM AUTHOR]

In this paper we consider coloring problems on graphs and other combinatorial structures on standard Borel spaces. Our goal is to obtain sufficient conditions under which such colorings can be made well-behaved in the sense of topology or measure. To this end, we show that such well-behaved colorings can be produced using certain powerful techniques from finite combinatorics and computer science. First, we prove that efficient distributed coloring algorithms (on finite graphs) yield well-behaved colorings of Borel graphs of bounded degree; roughly speaking, deterministic algorithms produce Borel colorings, while randomized algorithms give measurable and Baire-measurable colorings. Second, we establish measurable and Baire-measurable versions of the Symmetric Lovász Local Lemma (under the assumption p (d + 1) 8 ⩽ 2 − 15 , which is stronger than the standard LLL assumption p (d + 1) ⩽ e − 1 but still sufficient for many applications). From these general results, we derive a number of consequences in descriptive combinatorics and ergodic theory. [ABSTRACT FROM AUTHOR]

Metaphors in gesture and speech play a pivotal role in the way that programming concepts are presented in the classroom. However, little is known about the function of teachers' metaphors in practice. This study aims to explore teachers' use of metaphors in gesture and speech in a lecture on programming. Based on video observations of three upper secondary teachers, we employ Metaphor Identification Procedure (MIP) and Metaphor Identification for Gesture Guidelines (MIG-G) as methodological tools for identifying metaphoric speech and gestures related to programming concepts. The results of the study reveal that the gestures of the three teachers mainly function in two ways: (1) to add spatial properties to a programming concept and (2) to provide additional imagery for a programming concept. Consequently, the gestures identified in this study reduce the communicative burden of teachers' speech. Furthermore, the study reveals that teachers' gestures serve as means for making abstract concepts more tangible. For example, gestures concerning the abstract term "data" can generally be related to an object that could be received or moved. Hence, despite its metaphorical origin, data could be considered a graspable aspect of programming. Furthermore, spatial gestures enable the teachers to communicate programming processes in a tangible way, for example assigning programming processes a forward direction. Theoretical implications, potential implications for teaching and future research are discussed in the paper. [ABSTRACT FROM AUTHOR]

This document is a special issue of Mathematical Programming, Series B (MPB) that focuses on integer programming and combinatorial optimization. It contains 23 high-quality articles that were previously presented at the 23rd Conference on Integer Programming and Combinatorial Optimization (IPCO) in 2022. The IPCO conference is held annually and provides a platform for researchers and practitioners to share developments in theory, computation, and applications in these areas. The papers in this special issue underwent a rigorous refereeing process and represent the best of the field. The document also acknowledges the authors, referees, and the Editor-in-Chief of MPB for their contributions. [Extracted from the article]

Classifying scientific articles, patents, and other documents according to the relevant research topics is an important task, which enables a variety of functionalities, such as categorising documents in digital libraries, monitoring and predicting research trends, and recommending papers relevant to one or more topics. In this paper, we present the latest version of the CSO Classifier (v3.0), an unsupervised approach for automatically classifying research papers according to the Computer Science Ontology (CSO), a comprehensive taxonomy of research areas in the field of Computer Science. The CSO Classifier takes as input the textual components of a research paper (usually title, abstract, and keywords) and returns a set of research topics drawn from the ontology. This new version includes a new component for discarding outlier topics and offers improved scalability. We evaluated the CSO Classifier on a gold standard of manually annotated articles, demonstrating a significant improvement over alternative methods. We also present an overview of applications adopting the CSO Classifier and describe how it can be adapted to other fields. [ABSTRACT FROM AUTHOR]

In this paper we establish the complexity map for the Group Activity Selection Problem (GASP), along with two of its prominent variants called sGASP and gGASP, focusing on the case when the number of types of agents is the parameter. In all these problems, one is given a set of agents (each with their own preferences) and a set of activities, and the aim is to assign agents to activities in a way which satisfies certain global as well as preference-based conditions. Our positive results, consisting of one fixed-parameter algorithm and one XP algorithm, rely on a combination of novel Subset Sum machinery (which may be of general interest) and identifying certain compression steps that allow us to focus on solutions with a simpler, well-defined structure (in particular, they are "acyclic"). These algorithms are complemented by matching lower bounds, which among others close a gap to a recently obtained tractability result of Gupta et al. (in: Algorithmic game theory—10th international symposium, SAGT 2017, vol 10504 of lecture notes in computer science, Springer, 2017). In this direction, the techniques used to establish W[1]-hardness of sGASP are of particular interest: as an intermediate step, we use Sidon sequences to show the W[1]-hardness of a highly restricted variant of multi-dimensional Subset Sum, which may find applications in other settings as well. [ABSTRACT FROM AUTHOR]

The global coal industry, as an important basic industry, has strongly supported the stable and rapid development of the international economy and society. Although the level of automation in the context of coal mining has reached a very high degree, coal mine accidents such as roof collapse, side falling accidents, gas outburst potential, etc. continue to take place. Therefore, lots of intelligent systems are installed into collieries. For example, intelligent safety analysis technology represented by deep learning has been widely implemented in coal mine safety. The intelligent coal mining applications are always computing resource sensitive. They are usually deployed in the cloud centres that are located on the ground. As we all know, coal mining applications such as coal mine safety requires a comprehensive consideration of the mining, transportation, ventilation, hydrology, geology and other integrated factors. The transmission of all detecting data about these factors especially for multimedia from the underground face to the cloud computing centre is time-consuming. However, coal mine accidents always happen in a short span of time. This long transmission time is unacceptable for coal mine safety. In this paper, we propose a novel edge computing based intelligent processing architecture that integrates Internet of Things (IoT), fifth generation (5G), and Edge computing technologies for the coal mining intelligent system. Experiments are conducted on a deep learning based video fire prediction algorithm to prove the effectiveness of the architecture [ABSTRACT FROM AUTHOR]

Covering a graph with cohesive subgraphs is a classical problem in theoretical computer science, for example when the cohesive subgraph model considered is a clique. In this paper, we consider as a model of cohesive subgraph the 2-clubs, which are induced subgraphs of diameter at most 2. We prove new complexity results on the Min 2 - Club Cover problem, a variant recently introduced in the literature which asks to cover the vertices of a graph with a minimum number of 2-clubs. First, we answer an open question on the decision version of Min 2 - Club Cover that asks if it is possible to cover a graph with at most two 2-clubs, and we prove that it is W[1]-hard when parameterized by the distance to a 2-club. Then, we consider the complexity of Min 2 - Club Cover on some graph classes. We prove that Min 2 - Club Cover remains NP-hard on subcubic planar graphs, W[2]-hard on bipartite graphs when parameterized by the number of 2-clubs in a solution, and fixed-parameter tractable on graphs having bounded treewidth. [ABSTRACT FROM AUTHOR]

This document is a foreword for a special issue of the journal Microsystem Technologies. The special issue features selected papers from the 11th International Conference on Computing, Communication and Sensor Network (CCSN) held in September 2022 at Utkal University in Bhubaneswar, Odisha, India. The conference covered various interdisciplinary areas such as computing, communication, sensor networks, and circuit designs. The papers included in this special issue have undergone a rigorous review process and were selected for publication. The foreword expresses the hope that readers will find the papers informative. [Extracted from the article]

A way to improve energy management is to perform balancing both at the Peer-to-peer (P2P) level and then at the Virtual Microgrid-to-Virtual Microgrid (VMG2VMG) level, while considering the intermittency of available Renewable Energy Source (RES). This paper proposes an interdisciplinary analytics-based approach for the formation of VMGs addressing energy balancing. Our approach incorporates Computer Science methods to address an Energy sector problem, utilizing data preprocessing techniques and Machine Learning concepts. It features P2P balancing, where each peer is a prosumer perceived as an individual entity, and Virtual Microgrids (VMGs) as clusters of peers. We conducted several simulations utilizing clustering and binning algorithms for preprocessing energy data. Our approach offers options for generating VMGs of prosumers, prior to using a customized Exhaustive brute-force Balancing Algorithm (EBA). EBA performs balancing at the cluster-to-cluster level, perceived as VMG2VMG balancing. To that end, the study simulates on data from 94 prosumers, and reports outcomes, biases, and prospects for scaling up and expanding this work. Finally, this paper outlines potential ideal usages for the approach, either standalone or integrated with other toolkits and technologies. [ABSTRACT FROM AUTHOR]

This paper traces the empiricist program from early debates between nativism and behaviorism within philosophy, through debates about early connectionist approaches within the cognitive sciences, and up to their recent iterations within the domain of deep learning. We demonstrate how current debates on the nature of cognition via deep network architecture echo some of the core issues from the Chomsky/Quine debate and investigate the strength of support offered by these various lines of research to the empiricist standpoint. Referencing literature from both computer science and philosophy, we conclude that the current state of deep learning does not offer strong encouragement to the empiricist side despite some arguments to the contrary. [ABSTRACT FROM AUTHOR]

In the non-uniform k-center problem, the objective is to cover points in a metric space with specified number of balls of different radii. Chakrabarty, Goyal, and Krishnaswamy [ICALP 2016, Trans. on Algs. 2020] (CGK, henceforth) give a constant factor approximation when there are two types of radii. In this paper, we give a constant factor approximation for the two radii case in the presence of outliers. To achieve this, we need to bypass the technical barrier of bad integrality gaps in the CGK approach. We do so using "the ellipsoid method inside the ellipsoid method": use an outer layer of the ellipsoid method to reduce to stylized instances and use an inner layer of the ellipsoid method to solve these specialized instances. This idea is of independent interest and could be applicable to other problems. [ABSTRACT FROM AUTHOR]

Every year, around 28,100 journals publish 2.5 million research publications. Search engines, digital libraries, and citation indexes are used extensively to search these publications. When a user submits a query, it generates a large number of documents among which just a few are relevant. Due to inadequate indexing, the resultant documents are largely unstructured. Publicly known systems mostly index the research papers using keywords rather than using subject hierarchy. Numerous methods reported for performing single-label classification (SLC) or multi-label classification (MLC) are based on content and metadata features. Content-based techniques offer higher outcomes due to the extreme richness of features. But the drawback of content-based techniques is the unavailability of full text in most cases. The use of metadata-based parameters, such as title, keywords, and general terms, acts as an alternative to content. However, existing metadata-based techniques indicate low accuracy due to the use of traditional statistical measures to express textual properties in quantitative form, such as BOW, TF, and TFIDF. These measures may not establish the semantic context of the words. The existing MLC techniques require a specified threshold value to map articles into predetermined categories for which domain knowledge is necessary. The objective of this paper is to get over the limitations of SLC and MLC techniques. To capture the semantic and contextual information of words, the suggested approach leverages the Word2Vec paradigm for textual representation. The suggested model determines threshold values using rigorous data analysis, obviating the necessity for domain expertise. Experimentation is carried out on two datasets from the field of computer science (JUCS and ACM). In comparison to current state-of-the-art methodologies, the proposed model performed well. Experiments yielded average accuracy of 0.86 and 0.84 for JUCS and ACM for SLC, and 0.81 and 0.80 for JUCS and ACM for MLC. On both datasets, the proposed SLC model improved the accuracy up to 4%, while the proposed MLC model increased the accuracy up to 3%. [ABSTRACT FROM AUTHOR]

Developing efficient graph algorithms implementations is an extremely important problem of modern computer science, since graphs are frequently used in various real-world applications. Graph algorithms typically belong to the data-intensive class, and thus using architectures with high-bandwidth memory potentially allows to solve many graph problems significantly faster compared to modern multicore CPUs. Among other supercomputer architectures, vector systems, such as the SX family of NEC vector supercomputers, are equipped with high-bandwidth memory. However, the highly irregular structure of many real-world graphs makes it extremely challenging to implement graph algorithms on vector systems, since these implementations are usually bulky and complicated, and a deep understanding of vector architectures hardware features is required. This paper presents the world first attempt to develop an efficient and simultaneously simple graph processing framework for modern vector systems. Our vector graph library (VGL) framework targets NEC SX-Aurora TSUBASA as a primary vector architecture and provides relatively simple computational and data abstractions. These abstractions incorporate many vector-oriented optimization strategies into a high-level programming model, allowing quick implementation of new graph algorithms with a small amount of code and minimal knowledge about features of vector systems. In this paper, we evaluate the VGL performance on four widely used graph processing problems: breadth-first search, single source shortest paths, connected components, and page rank. The provided comparative performance analysis demonstrates that the VGL-based implementations achieve significant acceleration over the existing high-performance frameworks and libraries: up to 14 times speedup over multicore CPUs (Ligra, Galois, GAPBS) and up to 3 times speedup compared to NVIDIA GPU (Gunrock, NVGRAPH) implementations. [ABSTRACT FROM AUTHOR]

The importance of measuring the complexity of shapes can be seen by the wide range of its application such as computer vision, robotics, cognitive studies, eye tracking, and psychology. However, it is very challenging to define an accurate and precise metric to measure the complexity of the shapes. In this paper, we explore different notions of shape complexity, drawing from established work in mathematics, computer science, and computer vision. We integrate results from user studies with quantitative analyses to identify three measures that capture important axes of shape complexity, out of a list of almost 300 measures previously considered in the literature. We then explore the connection between specific measures and the types of complexity that each one can elucidate. Finally, we contribute a dataset of both abstract and meaningful shapes with designated complexity levels both to support our findings and to share with other researchers. [ABSTRACT FROM AUTHOR]

In recent decades, there has been a proliferation among the scientific community of works that focus on Alan Turing's contributions to the design and development of the modern computer. However, there are significant discrepancies among these studies, to such a point that some of them cast serious doubts on Alan Turing's work with respect to today's computer, and there are others that staunchly defend his leading role, as well as other studies that set out more well-balanced opinions. Faced with this situation, the aim of this paper is to analyse the evidence existing today in order to be able to draw a conclusion about whether or not Turing anticipated the trivialisation of the modern computer memory and, likewise, if his universal a-machine is the precursor of the general-purpose computer so omnipresent today. As a result of our research, the authors conclude that Turing did indeed play a leading role in the appearance of the modern computer, although he was not the only one or the first in the field of Computing Science, albeit he was the most influential, both in scope and in depth. [ABSTRACT FROM AUTHOR]