Search

The Pitcairn Islands are the last remaining Overseas Territory of the United Kingdom in the Pacific Ocean and are extremely remote, located in the central South Pacific approximately equidistant between Chile and New Zealand. The Territory consists of four widely-separated small islands, only one of which, Pitcairn itself, is inhabited. Along with many other Small Island Developing States (SIDS), Pitcairn shares significant challenges that present a special case within the world community. These include isolation and a lack of economy of scale, exacerbated by high transportation and communication costs. Considering these challenges, the UK Darwin Initiative recently funded a project to develop local capacity for adaptive fisheries management and to enhance tourism opportunities through the visits of cruise ships and the development of associated on-island facilities. Following the establishment of the Pitcairn Islands Marine Reserve in September 2016, which covers the whole of the Pitcairn Island Exclusive Economic Zone (an area of 836,000 km2), the key aim of the project was to mobilise community participation with a focus on introducing sustainable fisheries practices. Considering limited funds, resources and on-island capacity to implement monitoring, policing and enforcement of legislation, the establishment of a Locally Managed Marine Area (LMMA) scheme was viewed as the most appropriate way forward to ensure high levels of compliance at minimum costs.

A baited videographic survey at Pitcairn Island has significantly extended the known range for two reef-fish species: blue-lined triggerfish Xanthichthys caeruleolineatus and greater amberjack Seriola dumerili, with an additional minor extension noted for giant trevally Caranx ignobilis. This highlights the importance of further research in this remote, poorly studied island group and provides evidence supplementing the understanding of oceanographic patterns in the South Pacific.

The discovery of a population of Macrobrachium latimanus (von Martens, 1868) in a small pool on Pitcairn Island is a remarkable find, largely due to the island’s isolation, the small size of the prawn, and the paucity of suitable freshwater habitat. As in many southeastern Pacific islands, the volcanic origin of Pitcairn Island by geological activity at ‘hot spots’ through a pre-existing ocean floor, requires that their original colonization by the prawn must have resulted from long-distance dispersal. Like most carideans that live in freshwater and have small-size eggs, M. latimanus is an amphidromous species whose larvae are planktonic and must develop in a saline environment in estuaries and the open sea. After a period of some months in the marine environment, passing through many larval stages, the juveniles migrate upstream to the adult freshwater habitat. Macrobrachium latimanus has a widespread distribution throughout the Indo-West Pacific with Pitcairn Island, at 25°04'S, 130°06'W, now appearing to mark a new record for the southernmost and easternmost extent of its distribution.

The Pitcairn Islands are a remote group of four, widely separated islands in the central South Pacific, southeast of the Gambier Islands of French Polynesia. They mark the easternmost extent of the Indo-Pacific biogeographical province. Two (Oeno and Ducie) are small coral atolls, one is a raised coral atoll (Henderson), and other is an extinct volcano (Pitcairn). Pitcairn is the only inhabited island, with a population of about 50 people (in 2017). The group’s exclusive economic zone (EEZ) is very large, extending to over 836,000 km 2 . In September 2016, these waters became one of the world’s largest marine protected areas (MPAs). A total of 99.5% of the EEZ forms the nonextractive MPA, with small-scale, licensed subsistence and artisanal fishing allowed within the remaining 0.5% (termed coastal conservation areas—CCAs). In 2017 a Fisheries Management Plan was introduced for the management of fisheries within the CCAs, particularly around the Pitcairn Island. Anthropogenic pressures on their coastal waters are minimal. The main marine conservation concerns center on ocean-borne litter at the Henderson Island and damage to coral reefs at Pitcairn due to anchoring by visiting cruise ships and supply vessels.

Scarf's algorithm (Scarf, H. E. Econometrica 35, 50---69 1967) provides fractional core elements for NTU-games. Biro and Fleiner [4] showed that Scarf's algorithm can be extended for capacitated NTU-games. In this setting agents can be involved in more than one coalition at a time, cooperations may be performed with different intensities up to some limits, and the contribution of the agents can also differ in a coalition. The fractional stable solutions for the above model, produced by the extended Scarf algorithm, are called stable allocations. In this paper we apply this solution concept for the Hospitals / Residents problem with Couples (HRC). This is one of the most important general stable matching problems due to its relevant applications, also well-known to be NP-hard. We show that if a stable allocation yielded by the Scarf algorithm turns out to be integral then it provides a stable matching for an instance of HRC, so this method can be used as a heuristic. In an experimental study, we compare this method with other heuristics constructed for HRC that have been applied in practice in the American and Scottish resident allocation programs, respectively. Our main finding is that the Scarf algorithm outperforms all the other known heuristics when the proportion of couples is high.

The remote Pitcairn Island Group in the South Pacific was designated one of the world's largest marine reserves in 2016, encompassing some of the few remaining near-pristine areas within EEZ boundaries. Pitcairn's domestic fisheries are small-scale, and consist mainly of subsistence (non-commercial) and limited artisanal (commercial) catches. There is no locally-based industrial (large-scale commercial) fishery and the level of foreign industrial activity in recent times has been minimal, due in part to the low biomass of commercially valuable species, along with economic constraints of the EEZ's geographic isolation. Using a catch reconstruction method we estimated the total domestic marine catches for the Pitcairn Islands from 1950 to 2014. We show that overall the Pitcairn Islands' small-scale fisheries catches were almost 2.5 times higher than the data reported by the Food and Agriculture Organization (FAO) of the United Nations on behalf of the Pitcairn Islands, however, this primarily reflects discrepancies prior to the 1980s. Overall, catches for the subsistence and artisanal sectors started with around 12 t·year−1 in 1950, but declined to 4 t·year−1 by 2014. Domestic reconstructed subsistence catch levels were entirely driven by changes in the human population on the island, with reconstructed artisanal catches only occurring in recent years (2000 onwards). Industrial fishing is entirely executed by foreign vessels, this catch is considerably variable throughout the years and ceases entirely in 2006. The implementation of one of the world's largest marine reserves surrounding the offshore waters of Pitcairn Island has been specifically designed not to affect the rates of subsistence and artisanal fishing conducted by the resident population. Although there is no industrial fishing in the Pitcairn EEZ at present, climate change is predicted to influence the routes of migrating commercially-targeted species, potentially altering fishing effort levels and shift target fishing zones. Implementation of MPAs such as the Pitcairn Island Marine Reserve protect large oceanic areas from risk of future industrial exploitation, whilst protecting near-shore reef and deep-water zones, maintaining domestic coastal fisheries vital for local communities.

We consider two variants of the classical Stable Roommates problem with Incomplete (but strictly ordered) preference lists SRI that are degree constrained, i.e., preference lists are of bounded length. The first variant, EGAL d-SRI, involves finding an egalitarian stable matching in solvable instances of SRI with preference lists of length at most d. We show that this problem is NP-hard even if d=3. On the positive side we give a (2d+3)/7-approximation algorithm for d={3,4,5} which improves on the known bound of 2 for the unbounded preference list case. In the second variant of SRI, called d-SRTI, preference lists can include ties and are of length at most d. We show that the problem of deciding whether an instance of d-SRTI admits a stable matching is NP-complete even if d=3. We also consider the "most stable" version of this problem and prove a strong inapproximability bound for the d=3 case. However for d=2 we show that the latter problem can be solved in polynomial time., Comment: short version appeared at SAGT 2016

We explore the complexity and exact computation of a variant of the classical stable marriage problem in which we seek matchings that are not only stable, but are also “fair” in a formal sense. In particular, we study the sex-equal stable marriage problem (SESM), in which, roughly speaking, we wish to find a stable matching with the property that the men’s happiness is as close as possible to the women’s happiness. This problem is known to be strongly NP-hard (Kato in Jpn. J. Ind. Appl. Math. 10:1–19, 1993). We specifically consider SESM instances in which the preference lists of the men and/or women are bounded in length by a constant. On the negative side, we show that SESM is NP-hard, even if both the men’s and women’s preference lists are of length at most three, and is not even in the class XP when parameterized by the objective value of the solution. This strengthens the NP-hardness results of Kato (Jpn. J. Ind. Appl. Math. 10:1–19, 1993). On the positive side, we show that our hardness result is “tight” by giving a polynomial-time algorithm for the case in which the preference lists on one side (say the men) are of length at most two, and the lengths of the lists on the other side (the women) are unbounded. Furthermore, we give a low-order exponential-time algorithm for SESM in which the preference lists on one side are of length at most l (and the lengths of the lists on the other side are unbounded). In particular, for every pair of constants $l \in\mathcal{Z}^{+}$ and $\epsilon\in\mathcal{R}^{+}$ there is an algorithm with running time bounded by $O^{\star}(2^{(5 - \sqrt{24})(l-2 + \epsilon)n}) + O^{\star}(2^{\frac {(l-1)}{2\epsilon}})$ . Hence, if ϵ is chosen to be a sufficiently small constant, the running time is in O ⋆(1.0726 n ), O ⋆(1.1504 n ), O ⋆(1.2339 n ),… for l=3,4,5,… .

Matching problems with preferences occur in widespread applications such as the assignment of school-leavers to universities, junior doctors to hospitals, students to campus housing, children to schools, kidney transplant patients to donors and so on. The common thread is that agents have preference lists over the possible outcomes and the task is to find a matching of the participants that is in some sense optimal with respect to these preferences. The archetypal problem of this kind is the celebrated Stable Marriage problem, first introduced by David Gale and Lloyd Shapley in 1962. Over the last decade there has been something of a resurgence of interest in the algorithmic study of variants of this problem. In addition, research has been instigated into related matching problems, for example bipartite models with one-sided preferences, under criteria such as rank-maximality, popularity and Pareto optimality. These developments can be attributed in part to the growing tendency for matching processes to involve the online collection of preference information, necessitating efficient algorithms for constructing matchings that are fair and optimal in an expanding range of problem variants.

An instance of the popular matching problem (POP-M) consists of a set of applicants and a set of posts. Each applicant has a preference list that strictly ranks a subset of the posts. A matching M of applicants to posts is popular if there is no other matching M? such that more applicants prefer M? to M than prefer M to M?. Abraham et al. (SIAM J. Comput. 37:1030---1045, 2007) described a linear time algorithm to determine whether a popular matching exists for a given instance of POP-M, and if so to find a largest such matching. A number of variants and extensions of POP-M have recently been studied. This paper provides a characterization of the set of popular matchings for an arbitrary POP-M instance in terms of a structure called the switching graph, a directed graph computable in linear time from the preference lists. We show that the switching graph can be exploited to yield efficient algorithms for a range of associated problems, including the counting and enumeration of the set of popular matchings, generation of a popular matching uniformly at random, finding all applicant-post pairs that can occur in a popular matching, and computing popular matchings that satisfy various additional optimality criteria. Our algorithms for computing such optimal popular matchings improve those described in a recent paper by Kavitha and Nasre (Proceedings of MATCH-UP: Matching Under Preferences--Algorithms and Complexity, 2008).

A probe mapping technique using a novel implementation of a persistent q-gram index was developed. It guarantees to find all matches that meet certain definitions. These include exact matching of the central 19 bases of 25 base probes, matching the central 19 bases with at most one or three mismatches and exact matching of any 16 bases. In comparison with BLAST and BLAT, the new methods were either significantly faster or identified matches missed by the heuristics. The 16 bp method was used to map the 342,410 perfect match probes from the Affymetrix GeneChip Rat Genome 230 2.0 Array to the genome. When compared with the mapping from Ensembl, the new mapping included over seven million novel matches, providing additional evidence for researchers wishing to further investigate the sources of signals measured in microarray experiments. The results demonstrate the practicality of the index, which could support other q-gram based algorithms.

We consider variants of the classical stable marriage problem in which preference lists may contain ties, and may be of bounded length. Such restrictions arise naturally in practical applications, such as centralised matching schemes that assign graduating medical students to their first hospital posts. In such a setting, weak stability is the most common solution concept, and it is known that weakly stable matchings can have different sizes. This motivates the problem of finding a maximum cardinality weakly stable matching, which is known to be NP-hard in general. We show that this problem is solvable in polynomial time if each man's list is of length at most 2 (even for women's lists that are of unbounded length). However if each man's list is of length at most 3, we show that the problem becomes NP-hard (even if each women's list is of length at most 3) and not approximable within some δ>1 (even if each woman's list is of length at most 4).

We study variants of the classical stable marriage problem in which the preferences of the men or the women, or both, are derived from a master preference list. This models real-world matching problems in which participants are ranked according to some objective criteria. The master list(s) may be strictly ordered, or may include ties, and the lists of individuals may involve ties and may include all, or just some, of the members of the opposite sex. In fact, ties are almost inevitable in the master list if the ranking is done on the basis of a scoring scheme with a relatively small range of distinct values. We show that many of the interesting variants of stable marriage that are NP-hard remain so under very severe restrictions involving the presence of master lists, but a number of special cases can be solved in polynomial time. Under this master list model, versions of the stable marriage problem that are already solvable in polynomial time typically yield to faster and/or simpler algorithms, giving rise to simple new structural characterisations of the solutions in these cases.

We study variants of classical stable matching problems in which there is an additional requirement for a stable matching, namely that there should not be two participants who would prefer to exchange partners. The problem is motivated by the experience of real-world medical matching schemes that use stable matchings, where cases have arisen in which two participants discovered that each of them would prefer the other’s allocation, a situation that is seen as unfair. Our main result is that the problem of deciding whether an instance of the classical stable marriage problem admits a stable matching, with the additional property that no two men would prefer to exchange partners, is NP-complete. This implies a similar result for more general problems, such as the hospitals/residents problem, the many-to-one extension of stable marriage. Unlike previous NP-hardness results for variants of stable marriage, the proof exploits the powerful algebraic structure underlying the set of all stable matchings. In practical matching schemes, however, applicants’ preference lists are typically of short fixed length, and we describe a linear time algorithm for the problem in the special case where all of the men’s preference lists are of length ≤3.

When ties and incomplete preference lists are permitted in the Stable Marriage and Hospitals/Residents problems, stable matchings can have different sizes. The problem of finding a maximum cardinality stable matching in this context is known to be NP-hard, even under very severe restrictions on the number, size and position of ties. In this paper, we describe polynomial-time 5/3-approximation algorithms for variants of these problems in which ties are on one side only and at the end of the preference lists. The particular variant is motivated by important applications in large scale centralised matching schemes.

We consider a generalization of the Stable Roommates problem (sr), in which preference lists may be partially ordered and forbidden pairs may be present, denoted by srpf. This includes, as a special case, a corresponding generalization of the classical Stable Marriage problem (sm), denoted by smpf. By extending previous work of Feder, we give a two-step reduction from srpf to 2-sat. This has many consequences, including fast algorithms for a range of problems associated with finding “optimal” stable matchings and listing all solutions, given variants of sr and sm. For example, given an smpf instance I, we show that there exists an O(m) “succinct” certificate for the unsolvability of I, an O(m) algorithm for finding all the super-stable pairs in I, an O(m+kn) algorithm for listing all the super-stable matchings in I, an O(m1.5) algorithm for finding an egalitarian super-stable matching in I, and an O(m) algorithm for finding a minimum regret super-stable matching in I, where n is the number of men, m is the total length of the preference lists, and k is the number of super-stable matchings in I. Analogous results apply in the case of srpf.

Recently, a number of interesting algorithmic problems have arisen from the emergence, in a number of countries, of kidney exchange schemes, whereby live donors are matched with recipients according to compatibility and other considerations. One such problem can be modeled by a variant of the well-known stable roommates problem in which blocking cycles, as well as the normal blocking pairs, are significant. We show here that this variant of the stable roommates problem is NP-complete, thus solving an open question posed by Cechlarova and Lacko.

Suppose that each member of a set A of applicants ranks a subset of a set P of posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each applicant and each post appears in at most one pair. A rank-maximal matching is one in which the maximum possible number of applicants are matched to their first choice post, and subject to that condition, the maximum possible number are matched to their second choice post, and so on. This is a relevant concept in any practical matching situation and it was first studied by Irving [2003].We give an algorithm to compute a rank-maximal matching with running time O (min( n + C , C √ n ) m ), where C is the maximal rank of an edge used in a rank-maximal matching, n is the number of applicants and posts and m is the total size of the preference lists.

The Ig new antigen receptors (IgNARs) are single-domain antibodies found in the serum of sharks. Here, we report 2.2- and 2.8-Å structures of the type 2 IgNAR variable domains 12Y-1 and 12Y-2. Structural features include, first, an Ig superfamily topology transitional between cell adhesion molecules, antibodies, and T cell receptors; and, second, a vestigial complementarity-determining region 2 at the “bottom” of the molecule, apparently discontinuous from the antigen-binding paratope and similar to that observed in cell adhesion molecules. Thus, we suggest that IgNARs originated as cell-surface adhesion molecules coopted to the immune repertoire and represent an evolutionary lineage independent of variable heavy chain/variable light chain type antibodies. Additionally, both 12Y-1 and 12Y-2 form unique crystallographic dimers, predominantly mediated by main-chain framework interactions, which represent a possible model for primordial cell-based interactions. Unusually, the 12Y-2 complementarity-determining region 3 also adopts an extended β-hairpin structure, suggesting a distinct selective advantage in accessing cryptic antigenic epitopes.

Suffix trees and suffix arrays are classical data structures that are used to represent the set of suffixes of a given string, and thereby facilitate the efficient solution of various string processing problems--in particular on-line string searching. Here we investigate the potential of suitably adapted binary search trees as competitors in this context. The suffix binary search tree (SBST) and its balanced counterpart, the suffix AVL-tree, are conceptually simple, relatively easy to implement, and offer time and space efficiency to rival suffix trees and suffix arrays, with distinct advantages in some circumstances--for instance in cases where only a subset of the suffixes need be represented.Construction of a suffix BST for an n-long string can be achieved in O(nh) time, where h is the height of the tree. In the case of a suffix AVL-tree this will be O(n log n) in the worst case. Searching for an m-long substring requires O(m + l) time, where l is the length of the search path. In the suffix AVL-tree this is O(m + log n) in the worst case. The space requirements are linear in n, generally intermediate between those for a suffix tree and a suffix array.Empirical evidence, illustrating the competitiveness of suffix BSTs, is presented.

We consider instances of the classical stable marriage problem in which persons may include ties in their preference lists. We show that, in such a setting, strong lower bounds hold for the approximability of each of the problems of finding an egalitarian, minimum regret and sex-equal stable matching. We also consider stable marriage instances in which persons may express unacceptable partners in addition to ties. In this setting, we prove that there are constants delta, delta' such that each of the problems of approximating a maximum and minimum cardinality stable matching within factors of delta, delta' (respectively) is NP-hard, under strong restrictions. We also give an approximation algorithm for both problems that has a performance guarantee expressible in terms of the number of lists with ties. This significantly improves on the best-known previous performance guarantee, for the case that the ties are sparse. Our results have applications to large-scale centralized matching schemes.