On the inapproximability of the exemplar conserved interval distance problem of genomes

In this paper we present two main results about the inapproximability of the exemplar conserved interval distance problem of genomes. First, we prove that it is NP-complete to decide whether the exemplar conserved interval distance between any two genomes is zero or not. This result implies that the exemplar conserved interval distance problem does not admit any approximation in polynomial time, unless P=NP. In fact, this result holds, even when every gene appears in each of the given genomes at most three times. Second, we strengthen the first result under a weaker definition of approximation, called weak approximation. We show that the exemplar conserved interval distance problem does not admit any weak approximation within a super-linear factor of , where m is the maximal length of the given genomes. We also investigate polynomial time algorithms for solving the exemplar conserved interval distance problem when certain constrains are given. We prove that the zero exemplar conserved interval distance problem of two genomes is decidable in polynomial time when one genome is O(log n)-spanned. We also prove that one can solve the constant-sized exemplar conserved interval distance problem in polynomial time, provided that one genome is trivial.     

Hypothesis group testing for disjoint pairs

Classical group testing (CGT) is a widely applicable biotechnical technique used to identify a small number of distinguished objects from a population when the presence of any one of these distinguished objects among a group of others produces an observable result. This paper discusses a variant of CGT called group testing for disjoint pairs (GTAP). The difference between the two is that in GTDP, the distinguished items are pairs from, not individual objects in, the population. There are several biological examples of when this abstract model applies. One biological example is DNA hybridization. The presence of pairs of hybridized DNA strands can be detected in a pool of DNA strands. Another situation is the detection of binding interactions between prey and bait proteins. This paper gives a random pooling method, similar in spirit to hypothesis testing, which identifies pairs of objects from a population that collectively have an observable function. This method is simply to apply, achieves good results, is amenable to automation and can be easily modified to compensate for testing errors. M.A. Bishop is supported by AFOSR FA8750-06-C-0007. A.J. Macula is supported by NSF-0436298, AFOSR FA8750-06-C-0007.     

A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries

The vehicle routing problem with pickups and deliveries (VRPPD) extends the vehicle routing problem (VRP) by allowing customers to both send and receive goods. The main difficulty of the problem is that the load of vehicles is fluctuating rather than decreasing as in the VRP. We design a reactive tabu search metaheuristic that can check feasibility of proposed moves quickly and reacts to repetitions to guide the search. Several new best solutions are found for benchmark problems.     

Central State Steering of Local Collaboration: Assessing the Impact of Tools of Meta-governance in Homelessness Services in England

Much of the discussion of state steering of service delivery networks to encourage collaboration at the local level has been theoretical. This study builds on this analysis systematically to assess the relationship between meta-governance tools of central government steering and the extent of local collaboration, using the case of homelessness services in England. Contrary to the pessimist expectations of some contemporary theory, central government funding tools and facilitating the transfer of best practice encourages collaboration. However, simple information provision and authority based tools are only partially effective, risking tokenistic compliance. Authority tools are more effective when combined with other tools.

Accountability in the Shadow of Hierarchy: The Horizontal Accountability of Agencies

In the Netherlands, new accountability arrangements are created as remedies for the accountability deficit of agencies. These arrangements are of a ‘horizontal’ nature, as the agencies account for their behaviour towards accountees that are not their hierarchical superiors: clients, stakeholders or peers. This paper provides an inventory and qualitative assessment of horizontal accountability arrangements. It is argued that they have added value because they stimulate learning. However, horizontal accountability is not a substitute for hierarchical accountability. Horizontal accountability arrangements operate ‘in the shadow of hierarchy’: they gain significance through complex interactions with traditional forms of accountability.

Citizen Support for Hospital Privatization: A Hierarchical Cross-National Analysis

The movement for a new public management (NPM) holds that citizens will put aside partisan and ideological differences to support more efficient service delivery. Focusing on hospital privatization, a multi-national sample is utilized to investigate this assertion. Generalized hierarchical linear modeling (GHLM) is employed as the method of statistical analysis. The findings with regard to privatizing hospitals reveal that citizens develop their policy position by reference to a combination of symbolic political variables, service demand, self-interest, information levels, and political efficacy. The results cast doubt on the assertion that partisan differences will be set aside as citizens consider privatization reforms.

Quo Vadis? Suggestions for future corporate governance research

In this paper I first review the basic tenets of agency theory and theory of managerial capitalism as well as some of the major research in these areas then suggest for areas for future research that go beyond the extant empirical work. First, I suggest that it would be useful to reconsider the basic nature of the agency relationship, taking into account that while equity holders can be considered the principal, the board of directors may be more realistically in need of agent-like controls. Second, the complementary or supplementary nature of the monitoring/incentive alignment relationship has been shown theoretically but the empirical evidence is equivocal and needs future investigation. Third, there has been very limited research on the construct validity of archival measures of the sort used in agency theory. This requires the use of methodologies outside those of the more conventional type used in agency theory (i.e., from economics and finance). Finally, agency theory development would profit greatly by more extensive use of research methods such as laboratory studies and survey methodology and the integration of concepts such as personality and control processes.

A quadratic lower bound for colourful simplicial depth

We show that any point in the convex hull of each of (d+1) sets of (d+1) points in ℝ ^d is contained in at least ⌊(d+2)²/4⌋ simplices with one vertex from each set. Both authors were supported by NSERC Discovery grants. Additionally, T. Stephen was supported by DFG FG-468 and the Dynamical Systems research focus at the University of Magdeburg.     

Online scheduling on parallel machines with two GoS levels

This paper investigates the online scheduling problem on parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels. Hence each job and machine are labeled with the GoS levels, and each job can be processed by a particular machine only when the GoS level of the job is not less than that of the machine. The goal is to minimize the makespan. In this paper, we consider the problem with two GoS levels. It assumes that the GoS levels of the first k machines and the last m−k machines are 1 and 2, respectively. And every job has a GoS level of 1 alternatively or 2. We first prove the lower bound of the problem under consideration is at least 2. Then we discuss the performance of algorithm AW presented in Azar et al. (J. Algorithms 18:221–237, 1995) for the problem and show it has a tight bound of 4−1/m. Finally, we present an approximation algorithm with competitive ratio . Research supported by Natural Science Foundation of Zhejiang Province (Y605316) and its preliminary version appeared in Proceedings of AAIM2006, LNCS, 4041, 11-21.