ALBERT

Beschreibung: We present a threaded parallel adaptation of a state-of-the-art maximum clique algorithm for dense, computationally challenging graphs. We show that near-linear speedups are achievable in practice and that superlinear speedups are common. We include results for several previously unsolved benchmark problems.

Beschreibung: The stable marriage (SM) problem has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools or, more generally, to any two-sided market. In the classical formulation, n men and n women express their preferences (via a strict total order) over the members of the other sex. Solving an SM problem means finding a stable marriage where stability is an envy-free notion: no man and woman who are not married to each other would both prefer each other to their partners or to being single. We consider both the classical stable marriage problem and one of its useful variations (denoted SMTI (Stable Marriage with Ties and Incomplete lists)) where the men and women express their preferences in the form of an incomplete preference list with ties over a subset of the members of the other sex. Matchings are permitted only with people who appear in these preference lists, and we try to find a stable matching that marries as many people as possible. Whilst the SM problem is polynomial to solve, the SMTI problem is NP-hard. We propose to tackle both problems via a local search approach, which exploits properties of the problems to reduce the size of the neighborhood and to make local moves efficiently. We empirically evaluate our algorithm for SM problems by measuring its runtime behavior and its ability to sample the lattice of all possible stable marriages. We evaluate our algorithm for SMTI problems in terms of both its runtime behavior and its ability to find a maximum cardinality stable marriage. Experimental results suggest that for SM problems, the number of steps of our algorithm grows only as O(n log(n)), and that it samples very well the set of all stable marriages. It is thus a fair and efficient approach to generate stable marriages. Furthermore, our approach for SMTI problems is able to solve large problems, quickly returning stable matchings of large and often optimal size, despite the NP-hardness of this problem.

Beschreibung: The deterministic and restricted nature of industrial control system networks sets them apart from more open networks, such as local area networks in office environments. This improves the usability of network security, monitoring approaches that would be less feasible in more open environments. One of such approaches is machine learning based anomaly detection. Without proper customization for the special requirements of the industrial control system network environment, many existing anomaly or misuse detection systems will perform sub-optimally. A machine learning based approach could reduce the amount of manual customization required for different industrial control system networks. In this paper we analyze a possible set of features to be used in a machine learning based anomaly detection system in the real world industrial control system network environment under investigation. The network under investigation is represented by architectural drawing and results derived from network trace analysis. The network trace is captured from a live running industrial process control network and includes both control data and the data flowing between the control network and the office network. We limit the investigation to the IP traffic in the traces.

Beschreibung: Due to widespread adoption of mobile communications devices and increasingly high throughput capacity of cellular networks, Third-Generation (3G) and Long Term Evolution (LTE) are becoming ever more popular. Millions of smart phones with 3G capabilities are sold every year and used for mostly browsing the Internet. Hence, mobile operators have been heavily investing in their packet switched networks to meet customer demand and stay ahead in the market. The widespread use of broadband mobile Internet bring along also some IP based threats such as the Denial of Service (DoS) attacks, botnets and malwares. In this paper, we performed DoS and flooding attacks on 3G mobile networks and measured their effect on the most critical elements of a network such as the Radio Network Controller (RNC) and the Serving GPRS Support Node (SGSN) devices. We carried out our experiments on a real mobile network, not just a simulation environment, and hence our findings depict a realistic picture of the vulnerabilities existent in 3G mobile networks. We propose alternative solutions to avoid these vulnerabilities and mitigate the issues raised.

Beschreibung: The Internet of Things (IoT) refers to the Internet-like structure of billions of interconnected constrained devices, denoted as “smart objects”. Smart objects have limited capabilities, in terms of computational power and memory, and might be battery-powered devices, thus raising the need to adopt particularly energy efficient technologies. Among the most notable challenges that building interconnected smart objects brings about, there are standardization and interoperability. The use of IP has been foreseen as the standard for interoperability for smart objects. As billions of smart objects are expected to come to life and IPv4 addresses have eventually reached depletion, IPv6 has been identified as a candidate for smart-object communication. The deployment of the IoT raises many security issues coming from (i) the very nature of smart objects, e.g., the adoption of lightweight cryptographic algorithms, in terms of processing and memory requirements; and (ii) the use of standard protocols, e.g., the need to minimize the amount of data exchanged between nodes. This paper provides a detailed overview of the security challenges related to the deployment of smart objects. Security protocols at network, transport, and application layers are discussed, together with lightweight cryptographic algorithms proposed to be used instead of conventional and demanding ones, in terms of computational resources. Security aspects, such as key distribution and security bootstrapping, and application scenarios, such as secure data aggregation and service authorization, are also discussed.

Beschreibung: In this paper, we present a method to provide proactive assistance in text checking, based on usage relationships between words structuralized on the Web. For a given sentence, the method builds a connectionist structure of relationships between word n-grams. Such structure is then parameterized by means of an unsupervised and language agnostic optimization process. Finally, the method provides a representation of the sentence that allows emerging the least prominent usage-based relational patterns, helping to easily find badly-written and unpopular text. The study includes the problem statement and its characterization in the literature, as well as the proposed solving approach and some experimental use.

Beschreibung: Cyber-Physical-Human Systems (CPHS) combine sensing, communication and control to obtain desirable outcomes in physical environments for human beings, such as buildings or vehicles. A particularly important application area is emergency management. While recent work on the design and optimisation of emergency management schemes has relied essentially on discrete event simulation, which is challenged by the substantial amount of programming or reprogramming of the simulation tools and by the scalability and the computing time needed to obtain useful performance estimates, this paper proposes an approach that offers fast estimates based on graph models and probability models. We show that graph models can offer insight into the critical areas in an emergency evacuation and that they can suggest locations where sensor systems are particularly important and may require hardening. On the other hand, we also show that analytical models based on queueing theory can provide useful estimates of evacuation times and for routing optimisation. The results are illustrated with regard to the evacuation of a real-life building.

Beschreibung: In this paper, a natural probabilistic model for motif discovery has been used to experimentally test the quality of motif discovery programs. In this model, there are k background sequences, and each character in a background sequence is a random character from an alphabet, Σ. A motif G = g1g2 ... gm is a string of m characters. In each background sequence is implanted a probabilistically-generated approximate copy of G. For a probabilistically-generated approximate copy b1b2 ... bm of G, every character, bi, is probabilistically generated, such that the probability for bi ≠ gi is at most α. We develop two new randomized algorithms and one new deterministic algorithm. They make advancements in the following aspects: (1) The algorithms are much faster than those before. Our algorithms can even run in sublinear time. (2) They can handle any motif pattern. (3) The restriction for the alphabet size is a lower bound of four. This gives them potential applications in practical problems, since gene sequences have an alphabet size of four. (4) All algorithms have rigorous proofs about their performances. The methods developed in this paper have been used in the software implementation. We observed some encouraging results that show improved performance for motif detection compared with other software.

Beschreibung: Emergency rescues require that first responders provide support to evacuate injured and other civilians who are obstructed by the hazards. In this case, the emergency personnel can take actions strategically in order to rescue people maximally, efficiently and quickly. The paper studies the effectiveness of a random neural network (RNN)-based task assignment algorithm involving optimally matching emergency personnel and injured civilians, so that the emergency personnel can aid trapped people to move towards evacuation exits in real-time. The evaluations are run on a decision support evacuation system using the Distributed Building Evacuation Simulator (DBES) multi-agent platform in various emergency scenarios. The simulation results indicate that the RNN-based task assignment algorithm provides a near-optimal solution to resource allocation problems, which avoids resource wastage and improves the efficiency of the emergency rescue process.

Beschreibung: Online collaboration and web-based knowledge sharing have gained momentum as major components of the Web 2.0 movement. Consequently, knowledge embedded in such platforms is no longer static and continuously evolves through experts’ micro-contributions. Traditional Information Retrieval and Social Network Analysis techniques take a document-centric approach to expertise modeling by creating a macro-perspective of knowledge embedded in large corpus of static documents. However, as knowledge in collaboration platforms changes dynamically, the traditional macro-perspective is insufficient for tracking the evolution of knowledge and expertise. Hence, Expertise Profiling is presented with major challenges in the context of dynamic and evolving knowledge. In our previous study, we proposed a comprehensive, domain-independent model for expertise profiling in the context of evolving knowledge. In this paper, we incorporate Language Modeling into our methodology to enhance the accuracy of resulting profiles. Evaluation results indicate a significant improvement in the accuracy of profiles generated by this approach. In addition, we present our profile visualization tool, Profile Explorer, which serves as a paradigm for exploring and analyzing time-dependent expertise profiles in knowledge-bases where content evolves overtime. Profile Explorer facilitates comparative analysis of evolving expertise, independent of the domain and the methodology used in creating profiles.

Beschreibung: We suggest a user-oriented approach to combinatorial data anonymization. A data matrix is called k-anonymous if every row appears at least k times—the goal of the NP-hard k-ANONYMITY problem then is to make a given matrix k-anonymous by suppressing (blanking out) as few entries as possible. Building on previous work and coping with corresponding deficiencies, we describe an enhanced k-anonymization problem called PATTERN-GUIDED k-ANONYMITY, where the users specify in which combinations suppressions may occur. In this way, the user of the anonymized data can express the differing importance of various data features. We show that PATTERN-GUIDED k-ANONYMITY is NP-hard. We complement this by a fixed-parameter tractability result based on a “data-driven parameterization” and, based on this, develop an exact integer linear program (ILP)-based solution method, as well as a simple, but very effective, greedy heuristic. Experiments on several real-world datasets show that our heuristic easily matches up to the established “Mondrian” algorithm for k-ANONYMITY in terms of the quality of the anonymization and outperforms it in terms of running time.

Beschreibung: The technology of Security Information and Event Management (SIEM) becomes one of the most important research applications in the area of computer network security. The overall functionality of SIEM systems depends largely on the quality of solutions implemented at the data storage level, which is purposed for the representation of heterogeneous security events, their storage in the data repository, and the extraction of relevant data for analytical modules of SIEM systems. The paper discusses the key issues of design and implementation of a hybrid SIEM data repository, which combines relational and ontological data representations. Based on the analysis of existing SIEM systems and standards, the ontological approach is chosen as a core component of the repository, and an example of the ontological data model for vulnerabilities representation is outlined. The hybrid architecture of the repository is proposed for implementation in SIEM systems. Since the most of works on the repositories of SIEM systems is based on the relational data model, the paper focuses mainly on the ontological part of the hybrid approach. To test the repository we used the data model intended for attack modeling and security evaluation, which includes both ontological and relational dimensions.

Beschreibung: This study examines the participation of African Americans on social networking sites (SNS), and evaluates the degree to which African Americans engage in activities in the online environment to mitigate social capital deficits. Prior literature suggests that compared with whites, African Americans have less social capital that can enhance their socio-economic mobility. As such, my research question is: do African Americans enhance their social capital through their participation on SNS? I use nationally representative data collected from the Pew Internet and American Life Project to explore the research question. The results suggest that the online environment is potentially a space in which African Americans can lessen social capital deficits.

Beschreibung: A graph is said to be an intersection graph if there is a set of objects such that each vertex corresponds to an object and two vertices are adjacent if and only if the corresponding objects have a nonempty intersection. There are several natural graph classes that have geometric intersection representations. The geometric representations sometimes help to prove tractability/intractability of problems on graph classes. In this paper, we show some results proved by using geometric representations.

Beschreibung: The dominating set problem is a core NP-hard problem in combinatorial optimization and graph theory, and has many important applications. Baker [JACM 41,1994] introduces a k-outer planar graph decomposition-based framework for designing polynomial time approximation scheme (PTAS) for a class of NP-hard problems in planar graphs. It is mentioned that the framework can be applied to obtain an O(2ckn) time, c is a constant, (1+1/k)-approximation algorithm for the planar dominating set problem. We show that the approximation ratio achieved by the mentioned application of the framework is not bounded by any constant for the planar dominating set problem. We modify the application of the framework to give a PTAS for the planar dominating set problem. With k-outer planar graph decompositions, the modified PTAS has an approximation ratio (1 + 2/k). Using 2k-outer planar graph decompositions, the modified PTAS achieves the approximation ratio (1+1/k) in O(22ckn) time. We report a computational study on the modified PTAS. Our results show that the modified PTAS is practical.

Beschreibung: We study the problem of finding the minimum-length curvature constrained closed path through a set of regions in the plane. This problem is referred to as the Dubins Traveling Salesperson Problem with Neighborhoods (DTSPN). An algorithm is presented that uses sampling to cast this infinite dimensional combinatorial optimization problem as a Generalized Traveling Salesperson Problem (GTSP) with intersecting node sets. The GTSP is then converted to an Asymmetric Traveling Salesperson Problem (ATSP) through a series of graph transformations, thus allowing the use of existing approximation algorithms. This algorithm is shown to perform no worse than the best existing DTSPN algorithm and is shown to perform significantly better when the regions overlap. We report on the application of this algorithm to route an Unmanned Aerial Vehicle (UAV) equipped with a radio to collect data from sparsely deployed ground sensors in a field demonstration of autonomous detection, localization, and verification of multiple acoustic events.

Beschreibung: Random graphs are matrices with independent 0–1 elements with probabilities determined by a small number of parameters. One of the oldest models is the Rasch model where the odds are ratios of positive numbers scaling the rows and columns. Later Persi Diaconis with his coworkers rediscovered the model for symmetric matrices and called the model beta. Here we give goodness-of-fit tests for the model and extend the model to a version of the block model introduced by Holland, Laskey and Leinhard.

Beschreibung: A zero-suppressed binary decision diagram (ZDD) is a graph representation suitable for handling sparse set families. Given a ZDD representing a set family, we present an efficient algorithm to discover a hidden structure, called a co-occurrence relation, on the ground set. This computation can be done in time complexity that is related not to the number of sets, but to some feature values of the ZDD. We furthermore introduce a conditional co-occurrence relation and present an extraction algorithm, which enables us to discover further structural information.

Beschreibung: The C library libkww provides functions to compute the Kohlrausch–Williams– Watts function, i.e., the Laplace–Fourier transform of the stretched (or compressed) exponential function exp(-tβ ) for exponents β between 0.1 and 1.9 with double precision. Analytic error bounds are derived for the low and high frequency series expansions. For intermediate frequencies, the numeric integration is enormously accelerated by using the Ooura–Mori double exponential transformation. The primitive of the cosine transform needed for the convolution integrals is also implemented. The software is hosted at http://apps.jcns.fz-juelich.de/kww; version 3.0 is deposited as supplementary material to this article.

Beschreibung: The problem of finding the maximum number of vertex-disjoint uni-color paths in an edge-colored graph has been recently introduced in literature, motivated by applications in social network analysis. In this paper we investigate the approximation and parameterized complexity of the problem. First, we show that, for any constant ε > 0, the problem is not approximable within factor c1-ε, where c is the number of colors, and that the corresponding decision problem is W[1]-hard when parametrized by the number of disjoint paths. Then, we present a fixed-parameter algorithm for the problem parameterized by the number and the length of the disjoint paths.

Beschreibung: The maximum common connected edge subgraph problem is to find a connected graph with the maximum number of edges that is isomorphic to a subgraph of each of the two input graphs, where it has applications in pattern recognition and chemistry. This paper presents a dynamic programming algorithm for the problem when the two input graphs are outerplanar graphs of a bounded vertex degree, where it is known that the problem is NP-hard, even for outerplanar graphs of an unbounded degree. Although the algorithm repeatedly modifies input graphs, it is shown that the number of relevant subproblems is polynomially bounded, and thus, the algorithm works in polynomial time.

Beschreibung: The wide utilization of Wireless Sensor Networks (WSNs) is obstructed by the severely limited energy constraints of the individual sensor nodes. This is the reason why a large part of the research in WSNs focuses on the development of energy efficient routing protocols. In this paper, a new protocol called Equalized Cluster Head Election Routing Protocol (ECHERP), which pursues energy conservation through balanced clustering, is proposed. ECHERP models the network as a linear system and, using the Gaussian elimination algorithm, calculates the combinations of nodes that can be chosen as cluster heads in order to extend the network lifetime. The performance evaluation of ECHERP is carried out through simulation tests, which evince the effectiveness of this protocol in terms of network energy efficiency when compared against other well-known protocols.

Beschreibung: Principal Component Analysis (PCA) is widely used for identifying the major components of statistically distributed point clouds. Robust versions of PCA, often based in part on the ℓ1 norm (rather than the ℓ2 norm), are increasingly used, especially for point clouds with many outliers. Neither standard PCA nor robust PCAs can provide, without additional assumptions, reliable information for outlier-rich point clouds and for distributions with several main directions (spokes). We carry out a fundamental and complete reformulation of the PCA approach in a framework based exclusively on the ℓ1 norm and heavy-tailed distributions. The ℓ1 Major Component Detection and Analysis (ℓ1 MCDA) that we propose can determine the main directions and the radial extent of 2D data from single or multiple superimposed Gaussian or heavy-tailed distributions without and with patterned artificial outliers (clutter). In nearly all cases in the computational results, 2D ℓ1 MCDA has accuracy superior to that of standard PCA and of two robust PCAs, namely, the projection-pursuit method of Croux and Ruiz-Gazen and the ℓ1 factorization method of Ke and Kanade. (Standard PCA is, of course, superior to ℓ1 MCDA for Gaussian-distributed point clouds.) The computing time of ℓ1 MCDA is competitive with the computing times of the two robust PCAs.

Beschreibung: We extend the stable flow model of Fleiner to multicommodity flows. In addition to the preference lists of agents on trading partners for each commodity, every trading pair has a preference list on the commodities that the seller can sell to the buyer. A blocking walk (with respect to a certain commodity) may include saturated arcs, provided that a positive amount of less preferred commodity is traded along the arc. We prove that a stable multicommodity flow always exists, although it is PPAD-hard to find one.

Beschreibung: In this article, learning is studied in in situ applications that involve sensors. The main questions are how to conceptualize experiential learning involving sensors and what kinds of learning applications using sensors already exist or could be designed. It is claimed that experiential learning, context information and sensor data supports twenty first century learning. The concepts of context, technology-mediated experiences, shared felt experiences and experiential learning theory will be used to describe a framework for sensor-based mobile learning environments. Several scenarios and case examples using sensors and sensor data will be presented, and they will be analyzed using the framework. Finally, the article contributes to the discussion concerning the role of technology-mediated learning experiences and collective sensor data in developing twenty first century learning by characterizing what kinds of skills and competences are supported in learning situations that involve sensors.

Beschreibung: The eccentricity of a node in a graph is defined as the length of a longest shortest path starting at that node. The eccentricity distribution over all nodes is a relevant descriptive property of the graph, and its extreme values allow the derivation of measures such as the radius, diameter, center and periphery of the graph. This paper describes two new methods for computing the eccentricity distribution of large graphs such as social networks, web graphs, biological networks and routing networks.We first propose an exact algorithm based on eccentricity lower and upper bounds, which achieves significant speedups compared to the straightforward algorithm when computing both the extreme values of the distribution as well as the eccentricity distribution as a whole. The second algorithm that we describe is a hybrid strategy that combines the exact approach with an efficient sampling technique in order to obtain an even larger speedup on the computation of the entire eccentricity distribution. We perform an extensive set of experiments on a number of large graphs in order to measure and compare the performance of our algorithms, and demonstrate how we can efficiently compute the eccentricity distribution of various large real-world graphs.

Beschreibung: The aim of this work is the extraction of edges from Magnetic Resonance Imaging (MRI) and Diffusion Tensor Imaging (DTI) images by a deformable contour procedure, using an external force field derived from an anisotropic flow. Moreover, we introduce a divergence map in order to check the convergence of the process. As we know from vector calculus, divergence is a measure of the magnitude of a vector field convergence at a given point. Thus by means level curves of the divergence map, we have automatically selected an initial contour for the deformation process. If the initial curve includes the areas from which the vector field diverges, it will be able to push the curve towards the edges. Furthermore the divergence map highlights the presence of curves pointing to the most significant geometric parts of boundaries corresponding to high curvature values. In this way, the skeleton of the extracted object will be rather well defined and may subsequently be employed in shape analysis and morphological studies.

Beschreibung: Image reconstruction is a key component in many medical imaging modalities. The problem of image reconstruction can be viewed as a special inverse problem where the unknown image pixel intensities are estimated from the observed measurements. Since the measurements are usually noise contaminated, statistical reconstruction methods are preferred. In this paper we review some non-negatively constrained simultaneous iterative algorithms for maximum penalized likelihood reconstructions, where all measurements are used to estimate all pixel intensities in each iteration.

Beschreibung: This article presents and explains a methodology based on cryptanalytic and reverse engineering techniques that can be employed to quickly recover information from encrypted files generated by malware. The objective of the methodology is to minimize the effort with static and dynamic analysis, by using cryptanalysis and related knowledge as much as possible. In order to illustrate how it works, we present three case studies, taken from a big Brazilian company that was victimized by directed attacks focused on stealing information from a special purpose hardware they use in their environment.

Beschreibung: A highly efficient self-provisioning interference management scheme is derived for 3G Home Node-Bs (HNB). The proposed scheme comprises self-adjustment of the HNB transmission parameters to meet the targeted QoS (quality of service) requirements in terms of downlink and uplink guaranteed minimum throughput and coverage. This objective is achieved by means of an autonomous HNB solution, where the transmit power of pilot and data are adjusted separately, while also controlling the uplink interference pollution towards the macro-layer. The proposed scheme is evaluated by means of extensive system level simulations and the results show significant performance improvements in terms of user throughput outage probability, power efficiency, femtocell coverage, and impact on macro-layer performance as compared to prior art baseline techniques. The paper is concluded by also showing corresponding measurements from live 3G high-speed packet access (HSPA) HNB field-trials, confirming the validity of major simulation results and assumptions.

Beschreibung: The suffix tree is an extremely important data structure in bioinformatics. Classical implementations require much space, which renders them useless to handle large sequence collections. Recent research has obtained various compressed representations for suffix trees, with widely different space-time tradeoffs. In this paper we show how the use of range min-max trees yields novel representations achieving practical space/time tradeoffs. In addition, we show how those trees can be modified to index highly repetitive collections, obtaining the first compressed suffix tree representation that effectively adapts to that scenario.

Beschreibung: Data storage is a major and growing part of IT budgets for research since manyyears. Especially in biology, the amount of raw data products is growing continuously,and the advent of the so-called "next-generation" sequencers has made things worse.Affordable prices have pushed scientists to massively sequence whole genomes and to screenlarge cohort of patients, thereby producing tons of data as a side effect. The need formaximally fitting data into the available storage volumes has encouraged and welcomednew compression algorithms and tools. We focus here on state-of-the-art compression toolsand measure their compression performance on ABI SOLiD data.

Beschreibung: In biology, the notion of degenerate pattern plays a central role for describing various phenomena. For example, protein active site patterns, like those contained in the PROSITE database, e.g., [FY ]DPC[LIM][ASG]C[ASG], are, in general, represented by degenerate patterns with character classes. Researchers have developed several approaches over the years to discover degenerate patterns. Although these methods have been exhaustively and successfully tested on genomes and proteins, their outcomes often far exceed the size of the original input, making the output hard to be managed and to be interpreted by refined analysis requiring manual inspection. In this paper, we discuss a characterization of degenerate patterns with character classes, without gaps, and we introduce the concept of pattern priority for comparing and ranking different patterns. We define the class of underlying patterns for filtering any set of degenerate patterns into a new set that is linear in the size of the input sequence. We present some preliminary results on the detection of subtle signals in protein families. Results show that our approach drastically reduces the number of patterns in output for a tool for protein analysis, while retaining the representative patterns.

Beschreibung: As the internet has become an integral part of everyday life, it is understood that patterns of racial stereotyping and discrimination found in the offline world are often reproduced online. In our paper, we examine two exclusionary practices in an online environment for adult toy collectors: First, the exclusion of non-white individuals who are expected to form immediate friendships with other non-white members; and second, the essentializing of racial issues when concerns over the lack of racial diversity in the toys are discussed. This dismissal is often directly connected to non-white members’ decisions to no longer participate, resulting in a new form of segregation within virtual space.

Beschreibung: Energy saving in networks has traditionally focussed on reducing battery consumption through smart wireless network design. Recently, researchers have turned their attention to the energy cost and carbon emissions of the backbone network that both fixed and mobile communications depend on, proposing primarily mechanisms that turn equipments OFF or put them into deep sleep. This is an effective way of saving energy, provided that the nodes can return to working condition quickly, but it introduces increased delays and packet losses that directly affect the quality of communication experienced by the users. Here we investigate the associated tradeoffs between power consumption and quality of service in backbone networks that employ deep sleep energy savings. We examine these tradeoffs by conducting experiments on a real PC-based network topology, where nodes are put into deep sleep at random times and intervals, resulting in a continuously changing network with reduced total power consumption. The average power consumption, the packet loss and the average delay of this network are examined with respect to the average value of the ON rate and the ON/OFF cycle of the nodes.

Beschreibung: In the stable marriage problem, any instance admits the so-called man-optimal stable matching, in which every man is assigned the best possible partner. However, there are instances for which all men receive low-ranked partners even in the man-optimal stable matching. In this paper we consider the problem of improving the man-optimal stable matching by changing only one man’s preference list. We show that the optimization variant and the decision variant of this problem can be solved in time O(n3) and O(n2), respectively, where n is the number of men (women) in an input. We further extend the problem so that we are allowed to change k men’s preference lists. We show that the problem is W[1]-hard with respect to the parameter k and give O(n2k+1)-time and O(nk+1)-time exact algorithms for the optimization and decision variants, respectively. Finally, we show that the problems become easy when k = n; we give O(n2.5 log n)-time and O(n2)-time algorithms for the optimization and decision variants, respectively.

Beschreibung: In this contribution, a generic two-phase stochastic variable neighborhood approach is applied to nurse rostering problems. The proposed algorithm is used for creating feasible and efficient nurse rosters for many different nurse rostering cases. In order to demonstrate the efficiency and generic applicability of the proposed approach, experiments with real-world input data coming from many different nurse rostering cases have been conducted. The nurse rostering instances used have significant differences in nature, structure, philosophy and the type of hard and soft constraints. Computational results show that the proposed algorithm performs better than six different existing approaches applied to the same nurse rostering input instances using the same evaluation criteria. In addition, in all cases, it manages to reach the best-known fitness achieved in the literature, and in one case, it manages to beat the best-known fitness achieved till now.

Beschreibung: Volunteered Geographic Information (VGI) projects and their crowdsourced data have been the focus of a number of scientific analyses and investigations in recent years. Oftentimes the results show that the collaboratively collected geodata of one of the most popular VGI projects, OpenStreetMap (OSM), provides good coverage in urban areas when considering particular completeness factors. However, results can potentially vary significantly for different world regions. In this article, we conduct an analysis to determine similarities and differences in data contributions and community development in OSM between 12 selected urban areas of the world. Our findings showed significantly different results in data collection efforts and local OSM community sizes. European cities provide quantitatively larger amounts of geodata and number of contributors in OSM, resulting in a better representation of the real world in the dataset. Although the number of volunteers does not necessarily correlate with the general population density of the urban areas, similarities could be detected while comparing the percentage of different contributor groups and the number of changes they made to the OSM project. Further analyses show that socio-economic factors, such as income, can have an impact on the number of active contributors and the data provided in the analyzed areas. Furthermore, the results showed significant data contributions by members whose main territory of interest lies more than one thousand kilometers from the tested areas.

Beschreibung: Rooted triplets are becoming one of the most important types of input for reconstructing rooted phylogenies. A rooted triplet is a phylogenetic tree on three leaves and shows the evolutionary relationship of the corresponding three species. In this paper, we investigate the problem of inferring the maximum consensus evolutionary tree from a set of rooted triplets. This problem is known to be APX-hard. We present two new heuristic algorithms. For a given set of m triplets on n species, the FastTree algorithm runs in O(m + α(n)n2) time, where α(n) is the functional inverse of Ackermann’s function. This is faster than any other previously known algorithms, although the outcome is less satisfactory. The Best Pair Merge with Total Reconstruction (BPMTR) algorithm runs in O(mn3) time and, on average, performs better than any other previously known algorithms for this problem.

Beschreibung: A key property of overlay networks is the overlay nodes’ ability to establish connections (or be matched) to other nodes by preference, based on some suitability metric related to, e.g., the node’s distance, interests, recommendations, transaction history or available resources. When there are no preference cycles among the nodes, a stable matching exists in which nodes have maximized individual satisfaction, due to their choices, however no such guarantees are currently being given in the generic case. In this work, we employ the notion of node satisfaction to suggest a novel modeling for matching problems, suitable for overlay networks. We start by presenting a simple, yet powerful, distributed algorithm that solves the many-to-many matching problem with preferences. It achieves that by using local information and aggregate satisfaction as an optimization metric, while providing a guaranteed convergence and approximation ratio. Subsequently, we show how to extend the algorithm in order to support and adapt to changes in the nodes’ connectivity and preferences. In addition, we provide a detailed experimental study that focuses on the levels of achieved satisfaction, as well as convergence and reconvergence speed.

Beschreibung: We develop an efficient multicore algorithm, PMS6MC, for the (l; d)-motif discovery problem in which we are to find all strings of length l that appear in every string of a given set of strings with at most d mismatches. PMS6MC is based on PMS6, which is currently the fastest single-core algorithm for motif discovery in large instances. The speedup, relative to PMS6, attained by our multicore algorithm ranges from a high of 6.62 for the (17,6) challenging instances to a low of 2.75 for the (13,4) challenging instances on an Intel 6-core system. We estimate that PMS6MC is 2 to 4 times faster than other parallel algorithms for motif search on large instances.

Beschreibung: The stable matching problem (also known as the stable marriage problem) is a well-known problem of matching men to women, so that no man and woman, who are not married to each other, both prefer each other. Such a problem has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools or, more generally, to any two-sided market. In the classical stable marriage problem, both men and women express a strict preference order over the members of the other sex, in a qualitative way. Here, we consider stable marriage problems with weighted preferences: each man (resp., woman) provides a score for each woman (resp., man). Such problems are more expressive than the classical stable marriage problems. Moreover, in some real-life situations, it is more natural to express scores (to model, for example, profits or costs) rather than a qualitative preference ordering. In this context, we define new notions of stability and optimality, and we provide algorithms to find marriages that are stable and/or optimal according to these notions. While expressivity greatly increases by adopting weighted preferences, we show that, in most cases, the desired solutions can be found by adapting existing algorithms for the classical stable marriage problem. We also consider the manipulability properties of the procedures that return such stable marriages. While we know that all procedures are manipulable by modifying the preference lists or by truncating them, here, we consider if manipulation can occur also by just modifying the weights while preserving the ordering and avoiding truncation. It turns out that, by adding weights, in some cases, we may increase the possibility of manipulating, and this cannot be avoided by any reasonable restriction on the weights.

Beschreibung: We address the numerical solution of Lyapunov, algebraic and differential Riccati equations, via the matrix sign function, on platforms equipped with general-purpose multicore processors and, optionally, one or more graphics processing units (GPUs). In particular, we review the solvers for these equations, as well as the underlying methods, analyze their concurrency and scalability and provide details on their parallel implementation. Our experimental results show that this class of hardware provides sufficient computational power to tackle large-scale problems, which only a few years ago would have required a cluster of computers.

Beschreibung: The progressive consolidation of information technologies on a large scale has been facilitating and progressively increasing the production, collection, and diffusion of geographic data, as well as facilitating the integration of a large amount of external information into geographic information systems (GIS). Traditional GIS is transforming into a consolidated information infrastructure. This consolidated infrastructure is affecting more and more aspects of internet computing and services. Most popular systems (such as social networks, GPS, and decision support systems) involve complex GIS and significant amounts of information. As a web service, GIS is affected by exactly the same problems that affect the web as a whole. Therefore, next generation GIS solutions have to address further methodological and data engineering challenges in order to accommodate new applications’ extended requirements (in terms of scale, interoperability, and complexity). The conceptual and semantic modeling of GIS, as well as the integration of semantics into current GIS, provide highly expressive environments that are capable of meeting the needs and requirements of a wide range of applications.

Beschreibung: The term prosumer, first introduced by Toffler in the 1980s, has been developed by sociologists in response to Web 2.0 (the set of technologies that has transformed a predominantly static web into the collaborative medium initially envisaged by Tim Berners-Lee). The phenomena is now understood as a process involving the creation of meanings on the part of the consumer, who re-appropriates spaces that were dominated by institutionalized production, and this extends to the exploitation of consumer creativity on the production side. Recent consumption literature can be re-interpreted through the prosumer lens in order to understand whether prosumers are more creative or alienated in their activities. The peculiar typology of prosumption introduced by Web 2.0 leads us to analyze social capital as a key element in value creation, and to investigate its different online and offline forms. Our analysis then discusses the digital divide and critical consumerism as forms of empowerment impairment.

Beschreibung: This article speculates on the future of privacy and electronic identities on the Internet. Based on a short review of security models and the development of privacy-enhancing technology, privacy and electronic identities will be discussed as parts of a larger context—an ecosystem of personal information and electronic identities. The article argues for an ecosystem view of personal information and electronic identities, as both personal information and identity information are basic required input for many applications. Therefore, for both application owners and users, a functioning ecosystem of personal information and electronic identification is important. For the future of the Internet, high-quality information and controlled circulation of such information is therefore argued as decisive for the value of future Internet applications.

Beschreibung: The Quantitative Trait Loci (QTL) mapping problem aims to identify regions in the genome that are linked to phenotypic features of the developed organism that vary in degree. It is a principle step in determining targets for further genetic analysis and is key in decoding the role of specific genes that control quantitative traits within species. Applications include identifying genetic causes of disease, optimization of cross-breeding for desired traits and understanding trait diversity in populations. In this paper a new multi-objective evolutionary algorithm (MOEA) method is introduced and is shown to increase the accuracy of QTL mapping identification for both independent and epistatic loci interactions. The MOEA method optimizes over the space of possible partial least squares (PLS) regression QTL models and considers the conflicting objectives of model simplicity versus model accuracy. By optimizing for minimal model complexity, MOEA has the advantage of solving the over-fitting problem of conventional PLS models. The effectiveness of the method is confirmed by comparing the new method with Bayesian Interval Mapping approaches over a series of test cases where the optimal solutions are known. This approach can be applied to many problems that arise in analysis of genomic data sets where the number of features far exceeds the number of observations and where features can be highly correlated.

Beschreibung: In this paper, we address the implementation of physical layer network coding (PNC) based on compute and forward (CF) in relay networks. It is known that the maximum achievable rates in CF-based transmission is limited due to the channel approximations at the relay. In this work, we propose the integer forcing precoder (IFP), which bypasses this maximum rate achievability limitation. Our precoder requires channel state information (CSI) at the transmitter, but only that of the channel between the transmitter and the relay, which is a feasible assumption. The overall contributions of this paper are three-fold. Firstly, we propose an implementation of CF using IFP and prove that this implementation achieves higher rates as compared to traditional relaying schemes. Further, the probability of error from the proposed scheme is shown to have up to 2 dB of gain over the existent lattice network coding-based implementation of CF. Secondly, we analyze the two phases of transmission in the CF scheme, thereby characterizing the end-to-end behavior of the CF and not only one-phase behavior, as in previous proposals. Finally, we develop decoders for both the relay and the destination. We use a generalization of Bezout’s theorem to justify the construction of these decoders. Further, we make an analytical derivation of the end-to-end probability of error for cubic lattices using the proposed scheme.

Beschreibung: In this paper, the notion of stability is extended to network flows over time. As a useful device in our proofs, we present an elegant preflow-push variant of the Gale-Shapley algorithm that operates directly on the given network and computes stable flows in pseudo-polynomial time, both in the static flow and the flow over time case. We show periodical properties of stable flows over time on networks with an infinite time horizon. Finally, we discuss the influence of storage at vertices, with different results depending on the priority of the corresponding holdover edges.

Beschreibung: Lung cancer has been the largest cause of cancer deaths worldwide with an overall 5-year survival rate of only 15%. Its symptoms can be found exclusively in advanced stages where the chances for patients to survive are very low, thus making the mortality rate the highest among all other types of cancer. The present work deals with the attempt to design computer-aided detection or diagnosis (CAD) systems for early detection of lung cancer based on the analysis of sputum color images. The aim is to reduce the false negative rate and to increase the true positive rate as much as possible. The early detection of lung cancer from sputum images is a challenging problem, due to both the structure of the cancer cells and the stained method which are employed in the formulation of the sputum cells. We present here a framework for the extraction and segmentation of sputum cells in sputum images using, respectively, a threshold classifier, a Bayesian classification and mean shift segmentation. Our methods are validated and compared with other competitive techniques via a series of experimentation conducted with a data set of 100 images. The extraction and segmentation results will be used as a base for a CAD system for early detection of lung cancer which will improve the chances of survival for the patient.

Beschreibung: In an indoor firefighter mission, coordination and communication support are of the utmost importance. We present our experience from over five years of research with current firefighter support technology. In contrast to some large scale emergency response research, our work is focused on the frontline interaction between teams of firefighters and the incident commander on a single site. In this paper we investigate the flaws in firefighter communication systems. Frequent technical failures and the high cognitive costs incurred by communicating impede coordination. We then extract a list of requirements for an assistant emergency management technology from expert interviews. Thirdly, we provide a system concept and explore challenges for building a novel firefighter support system based on our previous work. The system has three key features: robust ad-hoc network, telemetry and text messaging, as well as implicit interaction. The result would provide a complementary mode of communication in addition to the current trunked radio.

Beschreibung: This paper is motivated by, but not limited to, the task of scheduling jobs organized in workflows to a computational grid. Due to the dynamic nature of grid computing, more or less permanent replanning is required so that only very limited time is available to come up with a revised plan. To meet the requirements of both users and resource owners, a multi-objective optimization comprising execution time and costs is needed. This paper summarizes our work over the last six years in this field, and reports new results obtained by the combination of heuristics and evolutionary search in an adaptive Memetic Algorithm. We will show how different heuristics contribute to solving varying replanning scenarios and investigate the question of the maximum manageable work load for a grid of growing size starting with a load of 200 jobs and 20 resources up to 7000 jobs and 700 resources. Furthermore, the effect of four different local searchers incorporated into the evolutionary search is studied. We will also report briefly on approaches that failed within the short time frame given for planning.

Beschreibung: The locator/identifier split is an approach for a new addressing and routing architecture to make routing in the core of the Internet more scalable. Based on this principle, we developed the GLI-Split framework, which separates the functionality of current IP addresses into a stable identifier and two independent locators, one for routing in the Internet core and one for edge networks. This makes routing in the Internet more stable and provides more flexibility for edge networks. GLI-Split can be incrementally deployed and it is backward-compatible with the IPv6 Internet. We describe its architecture, compare it to other approaches, present its benefits, and finally present a proof-of-concept implementation of GLI-Split.

Beschreibung: The Bitcoin network of decentralized payment transactions has attracted a lot of attention from both Internet users and researchers in recent years. Bitcoin utilizes a peer-to-peer network to issue anonymous payment transactions between different users. In the currently used Bitcoin clients, the full transaction history is available at each node of the network to prevent double spending without the need for a central authority, forming a valuable source for empirical research on network structure, network dynamics, and the implied anonymity challenges, as well as guidance on the future evolution of complex payment systems. We found dynamical effects of which some increase anonymity while others decrease it. Most importantly, several parameters of the Bitcoin transaction graph seem to have become stationary over the last 12–18 months. We discuss the implications.

Beschreibung: Emergency planners, first responders and relief workers increasingly rely on computational and communication systems that support all aspects of emergency management, from mitigation and preparedness to response and recovery. Failure of these systems, whether accidental or because of malicious action, can have severe implications for emergency management. Accidental failures have been extensively documented in the past and significant effort has been put into the development and introduction of more resilient technologies. At the same time researchers have been raising concerns about the potential of cyber attacks to cause physical disasters or to maximise the impact of one by intentionally impeding the work of the emergency services. Here, we provide a review of current research on the cyber threats to communication, sensing, information management and vehicular technologies used in emergency management. We emphasise on open issues for research, which are the cyber threats that have the potential to affect emergency management severely and for which solutions have not yet been proposed in the literature.

Beschreibung: Norwegian authorities’ policy aims at securing an information society for all, emphasizing the importance of accessible and usable Information and Communication Technology (ICT) for everyone. While the body of research on young people’s use of ICT is quite comprehensive, research addressing digital differentiation in young people with disabilities’ use of ICT is still in its early days. This article investigates how young people with disabilities’ use, or non-use, of assistive ICT creates digital differentiations. The investigation elaborates on how the anticipations and stereotypes of disability establish an authoritative definition of assistive ICT, and the consequence this creates for the use of the Web by young people with disabilities. The object of the article is to provide enhanced insight into the field of technology and disability by illuminating how assistive ICT sometimes eliminates and sometimes reproduces stereotypes and digital differentiations. The investigation draws on a qualitative interview study with 23 young Norwegians with disabilities, aged 15–20 years. I draw on a theoretical perspective to analyze the findings of the study, which employs the concept of identity multiplicity. The article’s closing discussion expands on technology’s significance in young people’s negotiations of impairment and of perceptions of disability

Beschreibung: Motivated by the observation that most companies are more likely to consider job applicants referred by their employees than those who applied on their own, Arcaute and Vassilvitskii modeled a job market that integrates social networks into stable matchings in an interesting way. We call their model HR+SN because an instance of their model is an ordered pair (I, G) where I is a typical instance of the Hospital/Residents problem (HR) and G is a graph that describes the social network (SN) of the residents in I. A matching p, of hospitals and residents has a local blocking pair (h, r) if (h, r) is a blocking pair of ii, and there is a resident r' such that r' is simultaneously an employee of h in the matching and a neighbor of r in G. Such a pair is likely to compromise the matching because the participants have access to each other through r': r can give her resume to r' who can then forward it to h. A locally stable matching is a matching with no local blocking pairs. The cardinality of the locally stable matchings of I can vary. This paper presents a variety of results on computing a locally stable matching with maximum cardinality.

Beschreibung: Given the increasingly popular use of socially interactive technology (SIT), it is believed that the way in which individuals communicate and experience relationships has drastically been changing. For those who partake in this electronic world, damaging behaviors akin to those found in the real world have emerged. Yet, we know little about the extent of these behaviors in the context of romantic relationships, especially from a gender or cultural standpoint. Research on dating violence generally indicates that women experience in-person victimization at higher rates than men, although some research has called this into question. It also suggests that some national groups experience higher rates of violence than others. However, research is almost non-existent when it comes to exploring violence in the digital world. This study investigated gender and nationality in (1) the nature and extent of socially interactive intimate violence, and (2) perceptions of the seriousness of virtual relationship violence. Using a sample of students from the United States and Poland, findings revealed that socially interactive technology may serve as a new avenue for aggressing against partners, as virtual relationship violence was not uncommon and reflected some patterns present in the real world. Some unexpected patterns also emerged. The results of this research signal a possible transferability of covert intimate violence and highlight ways in which inequalities may exist in our virtual worlds.

Beschreibung: Cyber-physical systems that include human beings and vehicles in a built environment, such as a building or a city, together with sensor networks and decision support systems have attracted much attention. In emergencies, which also include mobile searchers and rescuers, the interactions among civilians and the environment become much more diverse, and the complexity of the emergency response also becomes much greater. This paper surveys current research on sensor-assisted evacuation and rescue systems and discusses the related research issues concerning communication protocols for sensor networks, as well as several other important issues, such as the integrated asynchronous control of large-scale emergency response systems, knowledge discovery for rescue and prototyping platforms. Then, we suggest directions for further research.

Beschreibung: Recent vehicular networking activities include novel automotive applications, such as public vehicle to vehicle/infrastructure (V2X), large scale deployments, machine-to-machine (M2M) integration scenarios, and more. The platform described in this paper focuses on the integration of eHealth in a V2I setting. This is to allow the use of Internet from a vehicular setting to disseminate health-related information. From an eHealth viewpoint, the use of remote healthcare solutions to record and transmit a patient’s vital signs is a special telemedicine application that helps hospital resident health professionals to optimally prepare the patient’s admittance. From the automotive perspective, this is a typical vehicle-to-infrastructure (V2I) communication scenario. This proposal provides an IPv6 vehicular platform, which integrates eHealth devices and allows sending captured health-related data to a personal health record (PHR) application server in the IPv6 Internet. The collected data is viewed remotely by a doctor and supports his diagnostic decision. In particular, our work introduces the integration of vehicular and eHealth testbeds, describes related work and presents a lightweight auto-configuration method based on a DHCPv6 extension to provide IPv6 connectivity with a few numbers of messages.

Beschreibung: This paper reports on the design of an OPNET simulation platform to test the performance of sending real-time safety video over VANET (Vehicular Adhoc NETwork) using the WiMAX technology. To provide a more realistic environment for streaming real-time video, a video model was created based on the study of video traffic traces captured from a realistic vehicular camera, and different design considerations were taken into account. A practical controller over real-time streaming protocol is implemented to control data traffic congestion for future road safety development. Our driving video model was then integrated with the WiMAX OPNET model along with a mobility model based on real road maps. Using this simulation platform, different mobility cases have been studied and the performance evaluated in terms of end-to-end delay, jitter and visual experience.

Beschreibung: Inspired by many deadlock detection applications, the feedback vertex set is defined as a set of vertices in an undirected graph, whose removal would result in a graph without cycle. The Feedback Vertex Set Problem, known to be NP-complete, is to search for a feedback vertex set with the minimal cardinality to benefit the deadlock recovery. To address the issue, this paper presents NewkLS FVS(LS, local search; FVS, feedback vertex set), a variable depth-based local search algorithm with a randomized scheme to optimize the efficiency and performance. Experimental simulations are conducted to compare the algorithm with recent metaheuristics, and the computational results show that the proposed algorithm can outperform the other state-of-art algorithms and generate satisfactory solutions for most DIMACSbenchmarks.

Beschreibung: The aim of this research is to present a detailed step-by-step method for classification of very high resolution urban satellite images (VHRSI) into specific classes such as road, building, vegetation, etc., using fuzzy logic. In this study, object-based image analysis is used for image classification. The main problems in high resolution image classification are the uncertainties in the position of object borders in satellite images and also multiplex resemblance of the segments to different classes. In order to solve this problem, fuzzy logic is used for image classification, since it provides the possibility of image analysis using multiple parameters without requiring inclusion of certain thresholds in the class assignment process. In this study, an inclusive semi-automatic method for image classification is offered, which presents the configuration of the related fuzzy functions as well as fuzzy rules. The produced results are compared to the results of a normal classification using the same parameters, but with crisp rules. The overall accuracies and kappa coefficients of the presented method stand higher than the check projects.

Beschreibung: Although recent research suggests that the selective nature of new media helps foster issue specialists, little empirical evidence has been documented, mostly due to theoretical and methodological limitations. Extending the concept of issue publics, the present study proposes a method to estimate the degree to which an individual is a specialist- or a generalist-type citizen. Applying the method to the 2008 American National Election Studies data, the study reveals various characteristics of specialists and generalists. The results indicate that specialist-type citizens are positively associated with online news use, but negatively associated with conventional news media, such as television, newspaper, and radio. The implications of the growth of specialists as well as the validity of the proposed method are discussed.

Beschreibung: At the heart of many computations in science and engineering lies the need to efficiently and accurately solve large sparse linear systems of equations. Direct methods are frequently the method of choice because of their robustness, accuracy and potential for use as black-box solvers. In the last few years, there have been many new developments, and a number of new modern parallel general-purpose sparse solvers have been written for inclusion within the HSL mathematical software library. In this paper, we introduce and briefly review these solvers for symmetric sparse systems. We describe the algorithms used, highlight key features (including bit-compatibility and out-of-core working) and then, using problems arising from a range of practical applications, we illustrate and compare their performances. We demonstrate that modern direct solvers are able to accurately solve systems of order 106 in less than 3 minutes on a 16-core machine.

Beschreibung: Gradual patterns aim at describing co-variations of data such as the higher the size, the higher the weight. In recent years, such patterns have been studied more and more from the data mining point of view. The extraction of such patterns relies on efficient and smart orderings that can be built among data, for instance, when ordering the data with respect to the size, then the data are also ordered with respect to the weight. However, in many application domains, it is hardly possible to consider that data values are crisply ordered. When considering gene expression, it is not true from the biological point of view that Gene 1 is more expressed than Gene 2, if the levels of expression only differ from the tenth decimal. We thus consider fuzzy orderings and fuzzy gamma rank correlation. In this paper, we address two major problems related to this framework: (i) the high memory consumption and (ii) the precision, representation and efficient storage of the fuzzy concordance degrees versus the loss or gain of computing power. For this purpose, we consider multi-precision matrices represented using sparse matrices coupled with parallel algorithms. Experimental results show the interest of our proposal.

Beschreibung: In this work, we present an innovative approach for effective cross-network information dissemination, with applications to vehicular ad hoc networks (VANETs). The proposed approach, denoted as "Cross-Network Effective Traffic Alert Dissemination" (X-NETAD), leverages on the spontaneous formation of local WiFi (IEEE 802.11b) VANETs, with direct connections between neighboring vehicles, in order to disseminate, very quickly and inexpensively, traffic alerts received from the cellular network. The proposed communication architecture has been implemented on Android smartphones. The obtained experimental results show that an effective cross-network information dissemination service can entirely rely on smartphone-based communications. This paves the way to future Internet architectures, where vehicles will play a key role as information destinations and sources.

Beschreibung: A survey on the routing protocols based on ant-like mobile agents is given. These protocols are often employed in Mobile Ad Hoc Networks (MANET). Mobile Ad Hoc Networks are collections of wireless mobile nodes such as PDAs, laptop computers, and cellular phones having wireless communication capability that dynamically form a temporary network without using any existing network infrastructures such as wireless access points. The only infrastructure in MANET is the wireless communication interfaces on the devices. In such a circumstance, where some of the wireless devices are not within wireless range of each other, multi-hop routing is required to transmit messages to the destination. A node that wants to start communication with other nodes that are not within its one-hop wireless transmission range has to request intermediate nodes to forward their communication packets to the destination. In this paper, we survey a variety of proposed network protocols to accommodate this situation. We focus especially on biologically-inspired routing algorithms that are based on the ant colony optimization algorithm.

Beschreibung: This special issue of Algorithms is devoted to the design and analysis of algorithms for solving combinatorial problems of a theoretical or practical nature involving graphs, with a focus on computational complexity.

Beschreibung: Nowadays, due to the concern regarding environmental issues, establishing pedestrian/bike friendly urbanism is widely encouraged. To promote safety-assured, mobile communication environments, efficient, reliable maintenance, and information integrity need to be designed, especially in highly possibly interfered places. For busy traffic areas, regular degree-3 dedicated short range communication (DSRC) networks are safety and information featured with availability, reliability, and maintainability in paths of multi-lanes. For sparsely populated areas, probes of wireless sensors are rational, especially if sensor nodes can be organized to enhance security, reliability, and flexibility. Applying alternative network topologies, such as spider-webs, generalized honeycomb tori, and cube-connected cycles, for comparing and analyzing is proposed in DSRC and cellular communications to enhance integrity in communications.

Beschreibung: This paper studies the string-excluding (STR-EC)-constrained longest common subsequence (LCS) problem, a generalized LCS problem. For the two input sequences, X and Y , of lengths n andmand a constraint string, P, of length r, the goal is to find the longest common subsequence, Z, of X and Y that excludes P as a substring. The problem and its solution were first proposed by Chen and Chao, but we found that their algorithm cannot solve the problem correctly. A new dynamic programming solution for the STR-EC-LCS problem is then presented in this paper, and the correctness of the new algorithm is proven. The time complexity of the new algorithm is O(nmr).

Beschreibung: We consider a two-sided market under incomplete preference lists with ties, where the goal is to find a maximum size stable matching. The problem is APX-hard, and a 3/2-approximation was given by McDermid [1]. This algorithm has a non-linear running time, and, more importantly needs global knowledge of all preference lists. We present a very natural, economically reasonable, local, linear time algorithm with the same ratio, using some ideas of Paluch [2]. In this algorithm every person make decisions using only their own list, and some information asked from members of these lists (as in the case of the famous algorithm of Gale and Shapley). Some consequences to the Hospitals/Residents problem are also discussed.

Beschreibung: The present paper focuses on the development of an algorithm for safely and optimally managing the routing of aircraft on an airport surface in future airport operations. This tool is intended to support air traffic controllers’ decision-making in selecting the paths of all aircraft and the engine startup approval time for departing ones. Optimal routes are sought for minimizing the time both arriving and departing aircraft spend on an airport surface with engines on, with benefits in terms of safety, efficiency and costs. The proposed algorithm first computes a standalone, shortest path solution from runway to apron or vice versa, depending on the aircraft being inbound or outbound, respectively. For taking into account the constraints due to other traffic on an airport surface, this solution is amended by a conflict detection and resolution task that attempts to reduce and possibly nullify the number of conflicts generated in the first phase. An example application on a simple Italian airport exemplifies how the algorithm can be applied to true-world applications. Emphasis is given on how to model an airport surface as a weighted and directed graph with non-negative weights, as required for the input to the algorithm.

Beschreibung: This article examines how one data hub is working to become a relevant and useful source in the Web of big data and cloud computing. The focus is on OCLC’s WorldCat database of global library holdings and includes work by other library organizations to expose their data using big data concepts and standards. Explanation is given of how OCLC has begun work on the knowledge graph for this data and its active involvement with Schema.org in working to make this data useful throughout the Web.

Beschreibung: Course timetabling is a combinatorial optimization problem and has been confirmed to be an NP-complete problem. Course timetabling problems are different for different universities. The studied university course timetabling problem involves hard constraints such as classroom, class curriculum, and other variables. Concurrently, some soft constraints need also to be considered, including teacher’s preferred time, favorite class time etc. These preferences correspond to satisfaction values obtained via questionnaires. Particle swarm optimization (PSO) is a promising scheme for solving NP-complete problems due to its fast convergence, fewer parameter settings and ability to fit dynamic environmental characteristics. Therefore, PSO was applied towards solving course timetabling problems in this work. To reduce the computational complexity, a timeslot was designated in a particle’s encoding as the scheduling unit. Two types of PSO, the inertia weight version and constriction version, were evaluated. Moreover, an interchange heuristic was utilized to explore the neighboring solution space to improve solution quality. Additionally, schedule conflicts are handled after a solution has been generated. Experimental results demonstrate that the proposed scheme of constriction PSO with interchange heuristic is able to generate satisfactory course timetables that meet the requirements of teachers and classes according to the various applied constraints.

Beschreibung: An attractive advantage of mobile networks is that their users can gain easy access to different services. In some cases, equivalent services could be fulfilled by different providers, which brings the question of how to rationally select the best provider among all possibilities. In this paper, we investigate an answer to this question from both quality-of-service (QoS) and energy perspectives by formulating an optimisation problem. We illustrate the theoretical results with examples from experimental measurements of the resulting energy and performance.

Beschreibung: A novel noise filtering algorithm based on averaging Intrinsic Mode Function (aIMF), which is a derivation of Empirical Mode Decomposition (EMD), is proposed to remove white-Gaussian noise of foreign currency exchange rates that are nonlinear nonstationary times series signals. Noise patterns with different amplitudes and frequencies were randomly mixed into the five exchange rates. A number of filters, namely; Extended Kalman Filter (EKF), Wavelet Transform (WT), Particle Filter (PF) and the averaging Intrinsic Mode Function (aIMF) algorithm were used to compare filtering and smoothing performance. The aIMF algorithm demonstrated high noise reduction among the performance of these filters.

Beschreibung: This review gives an overview of the societal inequalities faced by people with intellectual disabilities, before focusing specifically on challenges people face accessing the Internet. Current access will be outlined along with the societal, support and attitudinal factors that can hinder access. Discussion of carer views of Internet use by people with intellectual disabilities will be covered incorporating consideration of the tension between protection, self-determination and lifestyle issues and gaining Internet access. We will address how impairment related factors may impede access and subsequently discuss how supports may be used to obfuscate impairments and facilitate access. We will move on from this to critically describe some of the potential benefits the Internet could provide to people with intellectual disabilities, including the potential for self-expression, advocacy and developing friendships. Finally, strategies to better include people with intellectual disabilities online will be given along with future research suggestions.

Beschreibung: One of the major challenges in handling realistic forward simulations for plant and animal breeding is the sheer number of markers. Due to advancing technologies, the requirement has quickly grown from hundreds of markers to millions. Most simulators are lagging behind in handling these sizes, since they do not scale well. We present a scheme for representing and manipulating such realistic size genomes, without any loss of information. Usually, the simulation is forward and over tens to hundreds of generations with hundreds of thousands of individuals at each generation. We demonstrate through simulations that our representation can be two orders of magnitude faster and handle at least two orders of magnitude more markers than existing software on realistic breeding scenarios.

Beschreibung: Portfolio optimization is one of the problems most frequently encountered by financial practitioners. The main goal of this paper is to fill a gap in the literature by providing a well-documented, step-by-step open-source implementation of Critical Line Algorithm (CLA) in scientific language. The code is implemented as a Python class object, which allows it to be imported like any other Python module, and integrated seamlessly with pre-existing code. We discuss the logic behind CLA following the algorithm’s decision flow. In addition, we developed several utilities that support finding answers to recurrent practical problems. We believe this publication will offer a better alternative to financial practitioners, many of whom are currently relying on generic-purpose optimizers which often deliver suboptimal solutions. The source code discussed in this paper can be downloaded at the authors’ websites (see Appendix).

Beschreibung: The purpose of this special issue is to explore social inequalities in the digital environment. The motivation for this issue is derived from the disproportionate focus on technological and economic aspects of the Information Society to the detriment of sociological and cultural aspects. The research presented here falls along three dimensions of inequality. Two papers explore the ways that race orders interaction online. A second pair of papers explores the experiences of technology users with physical and mental disabilities. A final paper looks at gender, and the higher rates of intimate partner violence experienced by women online. Taken as a whole, these five papers highlight some of the ways that the digital environment can reproduce or mitigate inequalities that have been molded and routinized in the physical environment.

Beschreibung: : The existing I/O workload generators and trace capturing tools are not adaptable to generating nor capturing the I/O requests of Android apps. The Android platform needs proper tools to capture and replay real world workload in the Android platform to verify the result of benchmark tools. This paper introduces Android Storage Performance Analysis Tool, AndroStep, which is specifically designed for characterizing and analyzing the behavior of the I/O subsystem in Android based devices. The AndroStep consists of Mobibench (workload generator), MOST (Mobile Storage Analyzer), and Mobigen (workload replayer). Mobibench is an Android app that generates a filesystem as well as SQLite database operations. Mobibench can also vary the number of concurrent threads to examining the filesystem scalability to support concurrency, e.g., metadata updates, journal file creation/deletion. MOST captures the trace and extracts key filesystem access characteristics such as access pattern with respect to file types, ratio between random vs. sequential access, ratio between buffered vs. synchronous I/O, fraction of metadata accesses, etc. MOST implements reverse mapping feature (finding an inode for a given block) and retrospective reverse mapping (finding an inode for a deleted file). Mobigen is a trace capturing and replaying tool that is specifically designed to perform the user experiment without actual human intervention. Mobigen records the system calls generated from the user behavior and sanitizes the trace for replayable form. Mobigen can replay this trace on different Android platforms or with different I/O stack configurations. As an example of using AndroStep, we analyzed the performances of twelve Android smartphones and the SQLite performances on five different filesystems. AndroStep makes otherwise time consuming I/O stack analysis extremely versatile. AndroStep makes a significant contribution in terms of shedding light on internal behavior of the Android I/O stack.

Beschreibung: This paper designs and evaluates a variant of CoSaMP algorithm, for recovering the sparse signal s from the compressive measurement  given a fixed low-rank subspace spanned by U. Instead of firstly recovering the full vector then separating the sparse part from the structured dense part, the proposed algorithm directly works on the compressive measurement to do the separation. We investigate the performance of the algorithm on both simulated data and video compressive sensing. The results show that for a fixed low-rank subspace and truly sparse signal the proposed algorithm could successfully recover the signal only from a few compressive sensing (CS) measurements, and it performs better than ordinary CoSaMP when the sparse signal is corrupted by additional Gaussian noise.

Beschreibung: Most direction-of-arrival (DOA) estimation approaches for conformal array suffer from high computational complexity, which cause high energy loss for the direction finding system. Thus, a low energy consumption DOA estimation algorithm for conformal array antenna is proposed in this paper. The arbitrary baseline direction finding algorithm is extended to estimate DOA for a conformal array in ultra-wideband. The rotation comparison method is adopted to solve the ambiguity of direction finding. The virtual baseline approach is used to construct the virtual elements. Theoretically, the virtual elements can be extended in the space flexibility. Four elements (both actual and virtual elements) can be used to obtain a group of solutions. The space angle estimation can be obtained by using sub-array divided technique and matrix inversion method. The stability of the proposed algorithm can be guaranteed by averaging the angles obtained by different sub-arrays. Finally, the simulation results verify the effectiveness of the proposed method with high DOA estimation accuracy and relatively low computational complexity.