Algorithms

153 KiB

Open AccessArticle

Improving Man-Optimal Stable Matchings by Minimum Change of Preference Lists

by Takao Inoshita, Robert W. Irving, Kazuo Iwama, Shuichi Miyazaki and Takashi Nagase

Algorithms 2013, 6(2), 371-382; https://doi.org/10.3390/a6020371 - 28 May 2013

Cited by 3 | Viewed by 8984

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 [...] Read more.

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(n³) and O(n²), 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(n^2k+1)-time and O(n^k+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(n^2.5 log n)-time and O(n²)-time algorithms for the optimization and decision variants, respectively. Full article

(This article belongs to the Special Issue Special Issue on Matching under Preferences)

► Show Figures

Figure 1

427 KiB

Open AccessArticle

Filtering Degenerate Patterns with Application to Protein Sequence Analysis

by Matteo Comin and Davide Verzotto

Algorithms 2013, 6(2), 352-370; https://doi.org/10.3390/a6020352 - 22 May 2013

Cited by 4 | Viewed by 6548

Abstract

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 [...] Read more.

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. Full article

(This article belongs to the Special Issue Algorithms for Sequence Analysis and Storage)

► Show Figures

Figure 1

560 KiB

Open AccessArticle

Practical Compressed Suffix Trees

by Andrés Abeliuk, Rodrigo Cánovas and Gonzalo Navarro

Algorithms 2013, 6(2), 319-351; https://doi.org/10.3390/a6020319 - 21 May 2013

Cited by 24 | Viewed by 8607

Abstract

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 [...] Read more.

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. Full article

(This article belongs to the Special Issue Algorithms for Sequence Analysis and Storage)

► Show Figures

Figure 1

288 KiB

Open AccessArticle

Multi-Sided Compression Performance Assessment of ABI SOLiD WES Data

by Tommaso Mazza and Stefano Castellana

Algorithms 2013, 6(2), 309-318; https://doi.org/10.3390/a6020309 - 21 May 2013

Cited by 2 | Viewed by 6937

Abstract

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 [...] Read more.

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. Full article

(This article belongs to the Special Issue Algorithms for Sequence Analysis and Storage)

► Show Figures

Figure 1

495 KiB

Open AccessArticle

A Generic Two-Phase Stochastic Variable Neighborhood Approach for Effectively Solving the Nurse Rostering Problem

by Ioannis P. Solos, Ioannis X. Tassopoulos and Grigorios N. Beligiannis

Algorithms 2013, 6(2), 278-308; https://doi.org/10.3390/a6020278 - 21 May 2013

Cited by 19 | Viewed by 9915

Abstract

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 [...] Read more.

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. Full article

(This article belongs to the Special Issue Novel Evolutionary Computation Approaches to Scheduling and Timetabling)

► Show Figures

Figure 1

1247 KiB

Open AccessArticle

Fast Rescheduling of Multiple Workflows to Constrained Heterogeneous Resources Using Multi-Criteria Memetic Computing

by Wilfried Jakob, Sylvia Strack, Alexander Quinte, Günther Bengel, Karl-Uwe Stucky and Wolfgang Süß

Algorithms 2013, 6(2), 245-277; https://doi.org/10.3390/a6020245 - 22 Apr 2013

Cited by 10 | Viewed by 8860

Abstract

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 [...] Read more.

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. Full article

(This article belongs to the Special Issue Novel Evolutionary Computation Approaches to Scheduling and Timetabling)

► Show Figures

Graphical abstract

387 KiB

Open AccessArticle

Solving University Course Timetabling Problems Using Constriction Particle Swarm Optimization with Local Search

by Ruey-Maw Chen and Hsiao-Fang Shih

Algorithms 2013, 6(2), 227-244; https://doi.org/10.3390/a6020227 - 19 Apr 2013

Cited by 48 | Viewed by 12777

Abstract

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 [...] Read more.

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. Full article

(This article belongs to the Special Issue Novel Evolutionary Computation Approaches to Scheduling and Timetabling)

► Show Figures

Figure 1

442 KiB

Open AccessArticle

Enforcing Security Mechanisms in the IP-Based Internet of Things: An Algorithmic Overview

by Simone Cirani, Gianluigi Ferrari and Luca Veltri

Algorithms 2013, 6(2), 197-226; https://doi.org/10.3390/a6020197 - 2 Apr 2013

Cited by 84 | Viewed by 13881

Abstract

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 [...] Read more.

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. Full article

(This article belongs to the Special Issue Sensor Network)

► Show Figures

Figure 1

Journal Menu

Journal Browser

Algorithms, Volume 6, Issue 2 (June 2013) – 8 articles , Pages 197-382

Further Information

Guidelines

MDPI Initiatives

Follow MDPI