ALBERT

Description: In the classic k -center problem, we are given a metric graph, and the objective is to select k nodes as centers such that the maximum distance from any vertex to its closest center is minimized. In this paper, we consider two important generalizations of k -center, the matroid center problem and the knapsack center problem. Both problems are motivated by recent content distribution network applications. Our contributions can be summarized as follows: (1) We consider the matroid center problem in which the centers are required to form an independent set of a given matroid. We show this problem is NP-hard even on a line. We present a 3-approximation algorithm for the problem on general metrics. We also consider the outlier version of the problem where a given number of vertices can be excluded as outliers from the solution. We present a 7-approximation for the outlier version. (2) We consider the (multi-)knapsack center problem in which the centers are required to satisfy one (or more) knapsack constraint(s). It is known that the knapsack center problem with a single knapsack constraint admits a 3-approximation. However, when there are at least two knapsack constraints, we show this problem is not approximable at all. To complement the hardness result, we present a polynomial time algorithm that gives a 3-approximate solution such that one knapsack constraint is satisfied and the others may be violated by at most a factor of \(1+\epsilon \) . We also obtain a 3-approximation for the outlier version that may violate the knapsack constraint by \(1+\epsilon \) .

Description: We design a succinct data structure for representing a poset that, given two elements, can report whether one precedes the other in constant time. This is equivalent to succinctly representing the transitive closure graph of the poset, and we note that the same method can also be used to succinctly represent the transitive reduction graph. For an n element poset, the data structure occupies \(n^2/4 + o(n^2)\) bits in the worst case. Furthermore, a slight extension to this data structure yields a succinct oracle for reachability in arbitrary directed graphs. Thus, using no more than a quarter of the space required to represent an arbitrary directed graph, reachability queries can be supported in constant time. We also consider the operation of listing all the successors or predecessors of a given element, and show how to do this in constant time per element reported using a slightly modified version of our succinct data structure.

Description: We consider a graph observability problem: how many edge colors are needed for an unlabeled graph so that an agent, walking from node to node, can uniquely determine its location from just the observed color sequence of the walk? Specifically, let G ( n ,  d ) be an edge-colored subgraph of d -dimensional (directed or undirected) lattice of size \(n^d = n \times n \times \cdots \times n\) . We say that G ( n ,  d ) is t -observable if an agent can uniquely determine its current position in the graph from the color sequence of any t -dimensional walk, where the dimension is the number of different directions spanned by the edges of the walk. A walk in an undirected lattice G ( n ,  d ) has dimension between 1 and d , but a directed walk can have dimension between 1 and 2 d because of two different orientations for each axis. We derive bounds on the number of colors needed for t -observability. Our main result is that \(\varTheta (n^{d/t})\) colors are both necessary and sufficient for t -observability of G ( n ,  d ), where d is considered a constant. This shows an interesting dependence of graph observability on the ratio between the dimension of the lattice and that of the walk. In particular, the number of colors for full-dimensional walks is \(\varTheta (n^{1/2})\) in the directed case, and \(\varTheta (n)\) in the undirected case, independent of the lattice dimension. All of our results extend easily to non-square lattices: given a lattice graph of size \(N = n_1 \times n_2 \times \cdots \times n_d\) , the number of colors for t -observability is \(\varTheta (\root t \of {N})\) .

Description: Background: With the introduction and implementation of a variety of government programs and policies to encourage adoption of electronic medical records (EMRs), EMRs are being increasingly adopted in North America. We sought to evaluate the completeness of a variety of EMR fields to determine if family physicians were comprehensively using their EMRs and the suitability of use of the data for secondary purposes in Ontario, Canada. Methods: We examined EMR data from a convenience sample of family physicians distributed throughout Ontario within the Electronic Medical Record Administrative data Linked Database (EMRALD) as extracted in the summer of 2012. We identified all physicians with at least one year of EMR use. Measures were developed and rates of physician documentation of clinical encounters, electronic prescriptions, laboratory tests, blood pressure and weight, referrals, consultation letters, and all fields in the cumulative patient profile were calculated as a function of physician and patient time since starting on the EMR. Results: Of the 167 physicians with at least one year of EMR use, we identified 186,237 patients. Overall, the fields with the highest level of completeness were for visit documentations and prescriptions (〉70 %). Improvements were observed with increasing trends of completeness overtime for almost all EMR fields according to increasing physician time on EMR. Assessment of the influence of patient time on EMR demonstrated an increasing likelihood of the population of EMR fields overtime, with the largest improvements occurring between the first and second years. Conclusions: All of the data fields examined appear to be reasonably complete within the first year of adoption with the biggest increase occurring the first to second year. Using all of the basic functions of the EMR appears to be occurring in the current environment of EMR adoption in Ontario. Thus the data appears to be suitable for secondary use.

Description: Background: Recognising the limitations of a paper-based approach to documenting vital sign observations and responding to national clinical guidelines, we have explored the use of an electronic solution that could improve the quality and safety of patient care. We have developed a system for recording vital sign observations at the bedside, automatically calculating an Early Warning Score, and saving data such that it is accessible to all relevant clinicians within a hospital trust. We have studied current clinical practice of using paper observation charts, and attempted to streamline the process. We describe our user-focussed design process, and present the key design decisions prior to describing the system in greater detail. Results: The system has been deployed in three pilot clinical areas over a period of 9 months. During this time, vital sign observations were recorded electronically using our system. Analysis of the number of observations recorded (21,316 observations) and the number of active users (111 users) confirmed that the system is being used for routine clinical observations. Feedback from clinical end-users was collected to assess user acceptance of the system. This resulted in a System Usability Scale score of 77.8, indicating high user acceptability. Conclusions: Our system has been successfully piloted, and is in the process of full implementation throughout adult inpatient clinical areas in the Oxford University Hospitals. Whilst our results demonstrate qualitative acceptance of the system, its quantitative effect on clinical care is yet to be evaluated.

Description: We revisit the matrix problems sparse null space and matrix sparsification , and show that they are equivalent. We then proceed to seek algorithms for these problems: we prove the hardness of approximation of these problems, and also give a powerful tool to extend algorithms and heuristics for sparse approximation theory to these problems.

Description: We introduce Planar Disjoint Paths Completion , a completion counterpart of the Disjoint Paths problem, and study its parameterized complexity. The problem can be stated as follows: given a, not necessarily connected, plane graph G ,  k pairs of terminals, and a face F of G ,  find a minimum-size set of edges, if one exists, to be added inside F so that the embedding remains planar and the pairs become connected by k disjoint paths in the augmented network. Our results are twofold: first, we give an upper bound on the number of necessary additional edges when a solution exists. This bound is a function of k , independent of the size of G . Second, we show that the problem is fixed-parameter tractable, in particular, it can be solved in time \(f(k)\cdot n^{2}\) .

Description: Background: According to the World Health Organization 130–150 million (according to WHO) of people globally are chronically infected with hepatitis C virus. The virus is responsible for chronic hepatitis that ultimately may cause liver cirrhosis and death. The disease is progressive, however antiviral treatment may slow down or stop its development. Therefore, it is important to estimate the severity of liver fibrosis for diagnostic, therapeutic and prognostic purposes.Liver biopsy provides a high accuracy diagnosis, however it is painful and invasive procedure. Recently, we witness an outburst of non-invasive tests (biological and physical ones) aiming to define severity of liver fibrosis, but commonly used FibroTest®, according to an independent research, in some cases may have accuracy lower than 50 %. In this paper a data mining and classification technique is proposed to determine the stage of liver fibrosis using easily accessible laboratory data. Methods: Research was carried out on archival records of routine laboratory blood tests (morphology, coagulation, biochemistry, protein electrophoresis) and histopathology records of liver biopsy as a reference value. As a result, the granular model was proposed, that contains a series of intervals representing influence of separate blood attributes on liver fibrosis stage. The model determines final diagnosis for a patient using aggregation method and voting procedure. The proposed solution is robust to missing or corrupted data. Results: The results were obtained on data from 290 patients with hepatitis C virus collected over 6 years. The model has been validated using training and test data. The overall accuracy of the solution is equal to 67.9 %. The intermediate liver fibrosis stages are hard to distinguish, due to effectiveness of biopsy itself. Additionally, the method was verified against dataset obtained from 365 patients with liver disease of various etiologies. The model proved to be robust to new data. What is worth mentioning, the error rate in misclassification of the first stage and the last stage is below 6.5 % for all analyzed datasets. Conclusions: The proposed system supports the physician and defines the stage of liver fibrosis in chronic hepatitis C. The biggest advantage of the solution is a human-centric approach using intervals, which can be verified by a specialist, before giving the final decision. Moreover, it is robust to missing data. The system can be used as a powerful support tool for diagnosis in real treatment.

Description: Background: Health decision-making requires evidence from high-quality data. As one example, the Discharge Abstract Database (DAD) compiles data from the majority of Canadian hospitals to form one of the most comprehensive and highly regarded administrative health databases available for health research, internationally. However, despite the success of this and other administrative health data resources, little is known about their history or the factors that have led to their success. The purpose of this paper is to provide an historical overview of Canadian administrative health data for health research to contribute to the institutional memory of this field. Methods: We conducted a qualitative content analysis of approximately 20 key sources to construct an historical narrative of administrative health data in Canada. Specifically, we searched for content related to key events, individuals, challenges, and successes in this field over time. Results: In Canada, administrative health data for health research has developed in tangent with provincial research centres. Interestingly, the lessons learned from this history align with the original recommendations of the 1964 Royal Commission on Health Services: (1) standardization, and (2) centralization of data resources, that is (3) facilitated through governmental financial support. Conclusions: The overview history provided here illustrates the need for longstanding partnerships between government and academia, for classification, terminology and standardization are time-consuming and ever-evolving processes. This paper will be of interest to those who work with administrative health data, and also for countries that are looking to build or improve upon their use of administrative health data for decision-making.

Description: We prove that in a graph with n vertices, induced chordal and interval subgraphs with the maximum number of vertices can be found in time \(\mathcal {O}(2^{\lambda n})\) for some \(\lambda 〈1\) . These are the first algorithms breaking the trivial \(2^n n^{\mathcal {O}(1)}\) bound of the brute-force search for these problems.

Description: We investigate the effect of limiting the number of reserve prices on the revenue in a probabilistic single item auction. In the model considered, bidders compete for an impression drawn from a known distribution of possible types. The auction mechanism sets up to \(\ell \) reserve prices, and each impression type is assigned the highest reserve price lower than the valuation of some bidder for it. The bidder proposing the highest bid for an arriving impression gets it provided his bid is at least the corresponding reserve price, and pays the maximum between the reserve price and the second highest bid. Since the number of impression types may be huge, we consider the revenue \(R_{\ell }\) that can be ensured using only \(\ell \) reserve prices. Our main results are tight lower bounds on \(R_{\ell }\) for the cases where the impressions are drawn from the uniform or a general probability distribution.

Description: Background: There is general consensus that appropriate development and use of information and communication technologies (ICT) are crucial in the delivery of effective primary care (PC). Several countries are defining policies to support and promote a structural change of the health care system through the introduction of ICT. This study analyses the state of development of basic ICT in PC systems of 31 European countries with the aim to describe the extent of, and main purposes for, computer use by General Practitioners (GPs) across Europe. Additionally, trends over time have been analysed. Methods: Descriptive statistical analysis was performed on data from the QUALICOPC (Quality and Costs of Primary Care in Europe) survey, to describe the geographic differences in the general use of computer, and in specific computerized clinical functions for different health-related purposes such as prescribing, medication checking, generating health records and research for medical information on the Internet. Results: While all the countries have achieved a near-universal adoption of a computer in their primary care practices, with only a few countries near or under the boundary of 90 %, the computerisation of primary care clinical functions presents a wide variability of adoption within and among countries and, in several cases (such as in the southern and central-eastern Europe), a large room for improvement. Conclusions: At European level, more efforts could be done to support southern and central-eastern Europe in closing the gap in adoption and use of ICT in PC. In particular, more attention seems to be need on the current usages of the computer in PC, by focusing policies and actions on the improvement of the appropriate usages that can impact on quality and costs of PC and can facilitate an interconnected health care system. However, policies and investments seem necessary but not sufficient to achieve these goals. Organizational, behavioural and also networking aspects should be taken in consideration.

Description: Background: Bangladesh is facing serious shortage of trained health professionals. In the pluralistic healthcare system of Bangladesh, formal health care providers constitute only 5 % of the total workforce; the rest are informal health care providers. Information Communication Technologies (ICTs) are increasingly seen as a powerful tool for linking the community with formal healthcare providers. Our study assesses an intervention that linked village doctors (a cadre of informal health care providers practising modern medicine) to formal doctors through call centres from the perspective of the village doctors who participated in the intervention. Methods: The study was conducted in Chakaria, a remote rural area in south-eastern Bangladesh during April–May 2013. Twelve village doctors were selected purposively from a pool of 55 village doctors who participated in the mobile health (mHealth) intervention. In depth interviews were conducted to collect data. The data were manually analysed using themes that emerged.ResultThe village doctors talked about both business benefits (access to formal doctors, getting support for decision making, and being entitled to call trained doctors) and personal benefits (both financial and non-financial). Some of the major barriers mentioned were technical problems related to accessing the call centre, charging consultation fees, and unfamiliarity with the call centre physicians. Conclusion: Village doctors saw many benefits to having a business relationship with the trained doctors that the mHealth intervention provided. mHealth through call centres has the potential to ensure consultation services to populations through existing informal healthcare providers in settings with a shortage of qualified healthcare providers.

Description: Background: Choosing the most appropriate family physician (FP) for the individual, plays a fundamental role in primary care. The aim of this study is to determine the selection criteria for the patients in choosing their family doctors and priority ranking of these criteria by using the multi-criteria decision-making method of the Analytic Hierarchy Process (AHP) model. Methods: The study was planned and conducted in two phases. In the first phase, factors affecting the patients’ decisions were revealed with a qualitative research. In the next phase, the priorities of FP selection criteria were determined by using AHP model. Criteria were compared in pairs. 96 patient were asked to fill the information forms which contains comparison scores in the Family Health Centres. Results: According to the analysis of focus group discussions FP selection criteria were congregated in to five groups: Individual Characteristics, Patient-Doctor relationship, Professional characteristics, the Setting, and Ethical Characteristics.For each of the 96 participants, comparison matrixes were formed based on the scores of their information forms. Of these, models of only 5 (5.2 %) of the participants were consistent, in other words, they have been able to score consistent ranking. The consistency ratios (CR) were found to be smaller than 0.10. Therefore the comparison matrix of this new model, which was formed based on the medians of scores only given by these 5 participants, was consistent (CR = 0.06 

Description: The new dual-pivot Quicksort by Vladimir Yaroslavskiy—used in Oracle’s Java runtime library since version 7—features intriguing asymmetries. They make a basic variant of this algorithm use less comparisons than classic single-pivot Quicksort. In this paper, we extend the analysis to the case where the two pivots are chosen as fixed order statistics of a random sample. Surprisingly, dual-pivot Quicksort then needs more comparisons than a corresponding version of classic Quicksort, so it is clear that counting comparisons is not sufficient to explain the running time advantages observed for Yaroslavskiy’s algorithm in practice. Consequently, we take a more holistic approach and give also the precise leading term of the average number of swaps, the number of executed Java Bytecode instructions and the number of scanned elements, a new simple cost measure that approximates I/O costs in the memory hierarchy. We determine optimal order statistics for each of the cost measures. It turns out that the asymmetries in Yaroslavskiy’s algorithm render pivots with a systematic skew more efficient than the symmetric choice. Moreover, we finally have a convincing explanation for the success of Yaroslavskiy’s algorithm in practice: compared with corresponding versions of classic single-pivot Quicksort, dual-pivot Quicksort needs significantly less I/Os, both with and without pivot sampling.

Description: In this paper, we consider the Unsplittable (hard) Capacitated Facility Location Problem (UCFLP) with uniform capacities and present new approximation algorithms for it. This problem is a generalization of the classical facility location problem where each facility can serve at most u units of demand and each client must be served by exactly one facility. This problem is motivated by its applications in many practical problems including supply chain problems of indivisible goods (Verter in Foundations of location analysis, chapter 2. International series in operations research and management science. Springer, Berlin, 2011 ) and the assignment problem in the content distribution networks (Bateni and Hajiaghayi in Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, pp 805–814, 2009 ). While there are several approximation algorithms for the soft capacitated version of this problem (in which one can open multiple copies of each facility) or the splittable version (in which the demand of each client can be divided to be served by multiple open facilities), there are very few results for the UCFLP. It is known that it is NP-hard to approximate this problem within any factor without violating the capacities. So we consider bicriteria \((\alpha ,\beta )\) -approximations where the algorithm returns a solution whose cost is within factor \(\alpha \) of the optimum and violates the capacity constraints within factor \(\beta \) . Shmoys et al. (Proceedings of the twenty-ninth annual ACM symposium on theory of computing, pp 265–274, 1997 ) were the first to consider this problem and gave a (9, 4)-approximation. Later results imply ( O (1), 2)-approximations, however, no constant factor approximation is known with capacity violation of less than 2. We present a framework for designing bicriteria approximation algorithms for this problem and show two new approximation algorithms with factors (9, 3 / 2) and (29.315, 4 / 3). These are the first algorithms with constant approximation in which the violation of capacities is below 2. The heart of our algorithm is a reduction from the UCFLP to a restricted version of the problem. One feature of this reduction is that any \((O(1),1+{\epsilon })\) -approximation for the restricted version implies an \((O(1),1+{\epsilon })\) -approximation for the UCFLP and we believe our techniques might be useful towards finding such approximations or perhaps \((f({\epsilon }),1+{\epsilon })\) -approximation for the UCFLP for some function f . In addition, we present a quasi-polynomial time \((1+\epsilon ,1+\epsilon )\) -approximation for the (uniform) UCFLP in Euclidean metrics, for any constant \({\epsilon }〉0\) .

Description: Background: Non-adherence to Antiretroviral Treatment (ART) is strongly associated with virologic rebound and drug resistance. Studies have shown that the most frequently mentioned reason for missing ART doses is the forgetfulness of patients to take their medications on time. Therefore using communication devices as reminder tools, for example alarms, pagers, text messages and telephone calls could improve adherence to ART. The aim of this study is to measure access to cellphones, willingness to receive text message medication reminders and to identify associated factors of ART patients at the University of Gondar Hospital, in North West Ethiopia. Methods: An institution based cross sectional quantitative study was conducted among 423 patients on ART during April 2014. Data were collected using structured interviewer-administered questionnaires. Data entry and analysis were done using Epi-Info version 7 and SPSS version 20 respectively. Descriptive statistics and multivariable logistic regression analysis were used to describe the characteristic of the sample and identify factors associated with the willingness to receive text message medication reminders. Results: A total of 415 (98 % response rate) respondents participated in the interview. The majority of respondents 316 (76.1 %) owned a cellphone, and 161(50.9 %) were willing to receive text message medication reminders. Positively associated factors to the willingness were the following: Younger age group (AOR = 5.18, 95 % CI: [1.69, 15.94]), having secondary or higher education (AOR = 4.61, 95 % CI: [1.33, 16.01]), using internet (AOR = 3.94, 95 % CI: [1.67, 9.31]), not disclosing HIV status to anyone other than HCP (Health Care Provider) (AOR = 3.03, 95 % CI: [1.20, 7.61]), availability of radio in dwelling (AOR = 2.74 95 % CI: [1.27, 5.88]), not answering unknown calls (AOR = 2.67, 95 % CI: [1.34, 5.32]), use of cellphone alarm as medication reminder (AOR = 2.22, 95%CI [1.09, 4.52]), and forgetting to take medications (AOR = 2.13, 95 % CI: [1.14, 3.96]). Conclusions: A high proportion of respondents have a cell phone and are willing to use it as medication reminders. Age, educational status and using internet were the main factors that are significantly associated with the willingness of patients to receive text message medication reminders.

Description: A commonly studied means of parameterizing graph problems is the deletion distance from triviality (Guo et al., Parameterized and exact computation, Springer, Berlin, pp. 162–173, 2004 ), which counts vertices that need to be deleted from a graph to place it in some class for which efficient algorithms are known. In the context of graph isomorphism, we define triviality to mean a graph with maximum degree bounded by a constant, as such graph classes admit polynomial-time isomorphism tests. We generalise deletion distance to a measure we call elimination distance to triviality, based on elimination trees or tree-depth decompositions. We establish that graph canonisation, and thus graph isomorphism, is \(\mathsf {FPT}\) when parameterized by elimination distance to bounded degree, extending results of Bouland et al. (Parameterized and exact computation, Springer, Berlin, pp. 218–230, 2012 ).

Description: Recent advances in drift analysis have given us better and better tools for understanding random processes, including the run time of randomized search heuristics. In the setting of multiplicative drift we do not only have excellent bounds on the expected run time, but also more general results showing the strong concentration of the run time. In this paper we investigate the setting of additive drift under the assumption of strong concentration of the “step size” of the process. Under sufficiently strong drift towards the goal we show a strong concentration of the hitting time. In contrast to this, we show that in the presence of small drift a Gambler’s-Ruin-like behavior of the process overrides the influence of the drift, leading to a maximal movement of about \(\sqrt{t}\) steps within t iterations. Finally, in the presence of sufficiently strong negative drift the hitting time is superpolynomial with high probability; this corresponds to the well-known Negative Drift Theorem.

Description: Binets and trinets are phylogenetic networks with two and three leaves, respectively. Here we consider the problem of deciding if there exists a binary level-1 phylogenetic network displaying a given set  \(\mathbb {T}\) of binary binets or trinets over a taxon set  X , and constructing such a network whenever it exists. We show that this is NP-hard for trinets but polynomial-time solvable for binets. Moreover, we show that the problem is still polynomial-time solvable for inputs consisting of binets and trinets as long as the cycles in the trinets have size three. Finally, we present an  \(O(3^{|X|} poly(|X|))\) time algorithm for general sets of binets and trinets. The latter two algorithms generalise to instances containing level-1 networks with arbitrarily many leaves, and thus provide some of the first supernetwork algorithms for computing networks from a set of rooted phylogenetic networks.

Description: We consider stochastic versions of OneMax and LeadingOnes and analyze the performance of evolutionary algorithms with and without populations on these problems. It is known that the ( \(1+1\) ) EA on OneMax performs well in the presence of very small noise, but poorly for higher noise levels. We extend these results to LeadingOnes and to many different noise models, showing how the application of drift theory can significantly simplify and generalize previous analyses. Most surprisingly, even small populations (of size \(\varTheta (\log n)\) ) can make evolutionary algorithms perform well for high noise levels, well outside the abilities of the ( \(1+1\) ) EA. Larger population sizes are even more beneficial; we consider both parent and offspring populations. In this sense, populations are robust in these stochastic settings.

Description: Since Tinhofer proposed the MinGreedy algorithm for maximum cardinality matching in 1984, several experimental studies found the randomized algorithm to perform excellently for various classes of random graphs and benchmark instances. In contrast, only few analytical results are known. We show that MinGreedy cannot improve on the trivial approximation ratio of  \(\frac{1}{2}\) whp., even for bipartite graphs. Our hard inputs seem to require a small number of high-degree nodes. This motivates an investigation of greedy algorithms on graphs with maximum degree  \(\varDelta \) : we show that  MinGreedy achieves a  \({\frac{{\varDelta }-1}{2{\varDelta }-3}} \) -approximation for graphs with  \({\varDelta } {=} 3\) and for \(\varDelta \) -regular graphs, and a guarantee of  \({\frac{{\varDelta }-1/2}{2{\varDelta }-2}} \) for graphs with maximum degree  \({\varDelta } \) . Interestingly, our bounds even hold for the deterministic MinGreedy that breaks all ties arbitrarily. Moreover, we investigate the limitations of the greedy paradigm, using the model of priority algorithms introduced by Borodin, Nielsen, and Rackoff. We study deterministic priority algorithms and prove a  \({\frac{{\varDelta }-1}{2{\varDelta }-3}}\) -inapproximability result for graphs with maximum degree  \({\varDelta } \) ; thus, these greedy algorithms do not achieve a  \(\frac{1}{2} {+} \varepsilon \) -approximation and in particular the  \(\frac{2}{3}\) -approximation obtained by the deterministic MinGreedy for  \({\varDelta } {=} 3\) is optimal in this class. For  k -uniform hypergraphs we show a tight  \(\frac{1}{k}\) -inapproximability bound. We also study fully randomized priority algorithms and give a  \(\frac{5}{6}\) -inapproximability bound. Thus, they cannot compete with matching algorithms of other paradigms.

Description: We discuss how string sorting algorithms can be parallelized on modern multi-core shared memory machines. As a synthesis of the best sequential string sorting algorithms and successful parallel sorting algorithms for atomic objects, we first propose string sample sort. The algorithm makes effective use of the memory hierarchy, uses additional word level parallelism, and largely avoids branch mispredictions. Then we focus on NUMA architectures, and develop parallel multiway LCP-merge and -mergesort to reduce the number of random memory accesses to remote nodes. Additionally, we parallelize variants of multikey quicksort and radix sort that are also useful in certain situations. As base-case sorter for LCP-aware string sorting we describe sequential LCP-insertion sort which calculates the LCP array and accelerates its insertions using it. Comprehensive experiments on five current multi-core platforms are then reported and discussed. The experiments show that our parallel string sorting implementations scale very well on real-world inputs and modern machines.

Description: Background: Prenatal screening tests for Down syndrome (DS) are routine in many developed countries and new tests are rapidly becoming available. Decisions about prenatal screening are increasingly complex with each successive test, and pregnant women need information about risks and benefits as well as clarity about their values. Decision aids (DAs) can help healthcare providers support women in this decision. Using an environmental scan, we aimed to identify publicly available DAs focusing on prenatal screening/diagnosis for Down syndrome that provide effective support for decision making. Methods: Data sources searched were the Decision Aids Library Inventory (DALI) of the Ottawa Patient Decision Aids Research Group at the Ottawa Health Research Institute; Google searches on the internet; professional organizations, academic institutions and other experts in the field; and references in existing systematic reviews on DAs. Eligible DAs targeted pregnant women, focused on prenatal screening and/or diagnosis, applied to tests for fetal abnormalities or aneuploidies, and were in French, English, Spanish or Portuguese. Pairs of reviewers independently identified eligible DAs and extracted characteristics including the presence of practical decision support tools and features to aid comprehension. They then performed quality assessment using the 16 minimum standards established by the International Patient Decision Aids Standards (IPDASi v4.0). Results: Of 543 potentially eligible DAs (512 in DALI, 27 from experts, and four on the internet), 23 were eligible and 20 were available for data extraction. DAs were developed from 1996 to 2013 in six countries (UK, USA, Canada, Australia, Sweden, and France). Five DAs were for prenatal screening, three for prenatal diagnosis and 12 for both). Eight contained values clarification methods (personal worksheets). The 20 DAs scored a median of 10/16 (range 6–15) on the 16 IPDAS minimum standards.DiscussionNone of the 20 included DAs met all 16 IPDAS minimum standards, and few included practical decision support tools or aids to comprehension. Conclusions: Our results indicate there is a need for DAs that effectively support decision making regarding prenatal testing for Down syndrome, especially in light of the recently available non-invasive prenatal screening tests.

Description: Background: A plethora of publicly available biomedical resources do currently exist and are constantly increasing at a fast rate. In parallel, specialized repositories are been developed, indexing numerous clinical and biomedical tools. The main drawback of such repositories is the difficulty in locating appropriate resources for a clinical or biomedical decision task, especially for non-Information Technology expert users. In parallel, although NLP research in the clinical domain has been active since the 1960s, progress in the development of NLP applications has been slow and lags behind progress in the general NLP domain.The aim of the present study is to investigate the use of semantics for biomedical resources annotation with domain specific ontologies and exploit Natural Language Processing methods in empowering the non-Information Technology expert users to efficiently search for biomedical resources using natural language. Methods: A Natural Language Processing engine which can “translate” free text into targeted queries, automatically transforming a clinical research question into a request description that contains only terms of ontologies, has been implemented. The implementation is based on information extraction techniques for text in natural language, guided by integrated ontologies. Furthermore, knowledge from robust text mining methods has been incorporated to map descriptions into suitable domain ontologies in order to ensure that the biomedical resources descriptions are domain oriented and enhance the accuracy of services discovery. The framework is freely available as a web application at (http://calchas.ics.forth.gr/). Results: For our experiments, a range of clinical questions were established based on descriptions of clinical trials from the ClinicalTrials.gov registry as well as recommendations from clinicians. Domain experts manually identified the available tools in a tools repository which are suitable for addressing the clinical questions at hand, either individually or as a set of tools forming a computational pipeline. The results were compared with those obtained from an automated discovery of candidate biomedical tools. For the evaluation of the results, precision and recall measurements were used. Our results indicate that the proposed framework has a high precision and low recall, implying that the system returns essentially more relevant results than irrelevant. Conclusions: There are adequate biomedical ontologies already available, sufficiency of existing NLP tools and quality of biomedical annotation systems for the implementation of a biomedical resources discovery framework, based on the semantic annotation of resources and the use on NLP techniques. The results of the present study demonstrate the clinical utility of the application of the proposed framework which aims to bridge the gap between clinical question in natural language and efficient dynamic biomedical resources discovery.

Description: Stochastic boolean function evaluation (SBFE) is the problem of determining the value of a given boolean function f on an unknown input x , when each bit \(x_i\) of x can only be determined by paying a given associated cost \(c_i\) . Further, x is drawn from a given product distribution: for each \(x_i\) , \(\mathbf{Pr}[x_i=1] = p_i\) and the bits are independent. The goal is to minimize the expected cost of evaluation. In this paper, we study the complexity of the SBFE problem for classes of DNF formulas. We consider both exact and approximate versions of the problem for subclasses of DNF, for arbitrary costs and product distributions, and for unit costs and/or the uniform distribution.

Description: Background: Although evidence has suggested that computerized drug-drug interaction alert systems may reduce the occurrence of drug-drug interactions, the numerous reminders and alerts generated by such systems could represent an excessive burden for clinicians, resulting in a high override rate of not only unimportant, but also important alerts. Methods: We analyzed physicians’ responses to alerts of relative contraindications and contraindications for coadministration in a computerized drug-drug interaction alert system at Hokkaido University Hospital. In this system, the physician must enter a password to override an alert and continue an order. All of the drug-drug interaction alerts generated between December 2011 and November 2012 at Hokkaido University Hospital were included in this study. Results: The system generated a total of 170 alerts of relative contraindications and contraindication for coadministration; 59 (34.7 %) of the corresponding orders were cancelled after the alert was accepted, and 111 (65.3 %) were overridden. The most frequent contraindication alert was for the combination of 3-hydroxy-3-methylglutaryl–coenzyme A reductase inhibitors and fibrates. No incidents involving drug-drug interactions were reported among patients who were prescribed contraindicated drug pairs after an override. Conclusions: Although computerized drug-drug interaction alert systems that require password overrides appear useful for promoting medication safety, having to enter passwords to override alerts may represent an excessive burden for the prescribing physician. Therefore, both patient safety and physicians’ workloads should be taken into consideration in future designs of computerized drug-drug interaction alert systems.

Description: Background: When new pharmaceutical products appear on the market, physicians need to know whether they are likely to be useful in their practices. Physicians currently obtain most of their information about the market release and properties of new drugs from pharmaceutical industry representatives. However, the official information contained in the summary of product characteristics (SPCs) and evaluation reports from health agencies, provide a more complete view of the potential value of new drugs, although they can be long and difficult to read. The main objective of this work was to design a prototype computer program to facilitate the objective appraisal of the potential value of a new pharmaceutical product by physicians. This prototype is based on the modeling of pharmaceutical innovations described in a previous paper. Methods: The interface was designed to allow physicians to develop a rapid understanding of the value of a new drug for their practices. We selected five new pharmaceutical products, to illustrate the function of this prototype. We considered only the texts supplied by national or international drug agencies at the time of market release. The perceived usability of the prototype was evaluated qualitatively, except for the System Usability Scale (SUS) score evaluation, by 10 physicians differing in age and medical background. Results: The display is based on the various axes of the conceptual model of pharmaceutical innovations. The user can select three levels of detail when consulting this information (highly synthetic, synthetic and detailed). Tables provide a comparison of the properties of the new pharmaceutical product with those of existing drugs, if available for the same indication, in terms of efficacy, safety and ease of use.The interface was highly appreciated by evaluators, who found it easy to understand and suggested no other additions of important, internationally valid information. The mean System Usability Scale score for the 10 physicians was 82, corresponding to a “good” user interface. Conclusions: This work led us to propose the selection, grouping, and mode of presentation for various types of knowledge on pharmaceutical innovations in a way that was appreciated by evaluators. It provides physicians with readily accessible objective information about new drugs.

Description: Background: Clinical trials apply standards approved by regulatory agencies for Electronic Data Capture (EDC). Operational Data Model (ODM) from Clinical Data Interchange Standards Consortium (CDISC) is commonly used. Electronic Health Record (EHR) systems for patient care predominantly apply HL7 standards, specifically Clinical Document Architecture (CDA). In recent years more and more patient data is processed in electronic form. Results: An open source reference implementation was designed and implemented to convert forms between ODM and CDA format. There are limitations of this conversion method due to different scope and design of ODM and CDA. Specifically, CDA has a multi-level hierarchical structure and CDA nodes can contain both XML values and XML attributes. Conclusions: Automated transformation of ODM files to CDA and vice versa is technically feasible in principle.

Description: Background: An academic, community medicine partnership was established to build a phenotype-to-outcome model targeting chronic pain. This model will be used to drive clinical decision support for pain medicine in the community setting. The first step in this effort is an examination of the electronic health records (EHR) from clinics that treat chronic pain. The biopsychosocial components provided by both patients and care providers must be of sufficient scope to populate the spectrum of patient types, treatment modalities, and possible outcomes. Methods: The patient health records from a large Midwest pain medicine practice (Michigan Pain Consultants, PC) contains physician notes, administrative codes, and patient-reported outcomes (PRO) on over 30,000 patients during the study period spanning 2010 to mid-2014. The PRO consists of a regularly administered Pain Health Assessment (PHA), a biopsychosocial, demographic, and symptomology questionnaire containing 163 items, which is completed approximately every six months with a compliance rate of over 95 %. The biopsychosocial items (74 items with Likert scales of 0–10) were examined by exploratory factor analysis and descriptive statistics to determine the number of independent constructs available for phenotypes and outcomes. Pain outcomes were examined both in the aggregate and the mean of longitudinal changes in each patient. Results: Exploratory factor analysis of the intake PHA revealed 15 orthogonal factors representing pain levels; physical, social, and emotional functions; the effects of pain on these functions; vitality and health; and measures of outcomes and satisfaction. Seven items were independent of the factors, offering unique information. As an exemplar of outcomes from the follow-up PHAs, patients reported approximately 60 % relief in their pain. When examined in the aggregate, patients showed both a decrease in pain levels and an increase in coping skills with an increased number of visits. When examined individually, 80-85 % of patients presenting with the highest pain levels reported improvement by approximately two points on an 11-point pain scale. Conclusions: We conclude that the data available in a community practice can be a rich source of biopsychosocial information relevant to the phenotypes of chronic pain. It is anticipated that phenotype linkages to best treatments and outcomes can be constructed from this set of records.

Description: Health information is increasingly being digitally stored and exchanged. The public is regularly collecting and storing health-related data on their own electronic devices and in the cloud. Diabetes prevention...

Description: Electronic medical records (EMR) offer a major potential for secondary use of data for research which can improve the safety, quality and efficiency of healthcare. They also enable the measurement of disease b...

Description: Interval graphs are intersection graphs of closed intervals of the real-line. The well-known computational problem, called recognition , asks whether an input graph G can be represented by closed intervals, i.e., whether G is an interval graph. There are several linear-time algorithms known for recognizing interval graphs, the oldest one is by Booth and Lueker (J Comput Syst Sci 13:335–379, 1976 ) based on PQ-trees. In this paper, we study a generalization of recognition, called partial representation extension . The input of this problem consists of a graph G with a partial representation \({{{\mathcal {R}}}}'\) fixing the positions of some intervals. The problem asks whether it is possible to place the remaining interval and create an interval representation \({{{\mathcal {R}}}}\) of the entire graph G extending \({{{\mathcal {R}}}}'\) . We generalize the characterization of interval graphs by Fulkerson and Gross (Pac J Math 15:835–855, 1965 ) to extendible partial representations. Using it, we give a linear-time algorithm for partial representation extension based on a reordering problem of PQ-trees.

Description: Epileptic seizure is a serious health problem in the world and there is a huge population suffering from it every year. If an algorithm could automatically detect seizures and deliver the patient therapy or no...

Description: Learning deep representations of clinical events based on their distributions in electronic health records has been shown to allow for subsequent training of higher-performing predictive models compared to the...

Description: Glands are vital structures found throughout the human body and their structure and function are affected by many diseases. The ability to segment and detect glands among other types of tissues is important fo...

Description: People want to live independently, but too often disabilities or advanced age robs them of the ability to do the necessary activities of daily living (ADLs). Finding relationships between electromyograms measu...

Description: Cancer is a disease characterized as an uncontrolled growth of abnormal cells that invades neighboring tissues and destroys them. Lung cancer is the primary cause of cancer-related deaths in the world, and it ...

Description: Healthcare researchers often use multiple healthcare survey instruments to examine a particular patient symptom. The use of multiple instruments can pose some interesting research questions, such as whether th...

Description: Modern data management systems often need to deal with massive, dynamic and inherently distributed data sources. We collect the data using a distributed network, and at the same time try to maintain a global view of the data at a central coordinator using a minimal amount of communication. Such applications have been captured by the distributed monitoring model which has attracted a lot of attention in recent years. In this paper we investigate the monitoring of the entropy functions, which are very useful in network monitoring applications such as detecting distributed denial-of-service attacks. Our results improve the previous best results by Arackaparambil et al. in ICLP 1: 95–106 ( 2009 ). Our technical contribution also includes implementing the celebrated AMS sampling method (by Alon et al. in J Comput Syst Sci 58(1): 137–147 1999 ) in the distributed monitoring model, which could be of independent interest.

Description: In the Boundary Labeling problem, we are given a set of  n points, referred to as sites , inside an axis-parallel rectangle  R , and a set of  n pairwise disjoint rectangular labels that are attached to  R from the outside. The task is to connect the sites to the labels by non-intersecting rectilinear paths, so-called leaders , with at most one bend. In this paper, we study the Multi-Sided Boundary Labeling problem, with labels lying on at least two sides of the enclosing rectangle. We present a polynomial-time algorithm that computes a crossing-free leader layout if one exists. So far, such an algorithm has only been known for the cases in which labels lie on one side or on two opposite sides of  R (here a crossing-free solution always exists). The case where labels may lie on adjacent sides is more difficult. We present efficient algorithms for testing the existence of a crossing-free leader layout that labels all sites and also for maximizing the number of labeled sites in a crossing-free leader layout. For two-sided boundary labeling with adjacent sides, we further show how to minimize the total leader length in a crossing-free layout.

Description: In this paper we consider the problem of the strict self-assembly of infinite fractals within tile self-assembly. In particular, we provide tile assembly algorithms for the assembly of a Sierpinski triangle and the discrete Sierpinski carpet within a class of models we term the h - handed assembly model ( h -HAM), which generalizes the 2-HAM to allow up to h assemblies to combine in a single assembly step. Despite substantial consideration, no purely growth self-assembly model has yet been shown to strictly assemble an infinite fractal without significant modification to the fractal shape. In this paper we not only achieve this, but in the case of the Sierpinski carpet are able to achieve it within the 2-HAM, one of the most well studied tile assembly models in the literature. Our specific results are as follows: We provide a 6-HAM construction for a Sierpinski triangle that works at scale factor 1, 30 tile types, and assembles the fractal in a near perfect way in which all intermediate assemblies are finite-sized iterations of the recursive fractal. We further assemble a Sierpinski triangle within the 3-HAM at scale factor 3 and 990 tile types. For the Sierpinski carpet, we present a 2-HAM result that works at scale factor 3 and uses 1216 tile types. We further include analysis showing that the aTAM is incapable of strictly assembling the Sierpinski triangle considered in this paper, and that multiple hands are needed for the near-perfect assembly of a Sierpinski triangle and the Sierpinski carpet.

Description: We consider k -Facility Location games, where n strategic agents report their locations on the real line and a mechanism maps them to k facilities. Each agent seeks to minimize his connection cost, given by a nonnegative increasing function of his distance to the nearest facility. Departing from previous work, that mostly considers the identity cost function, we are interested in mechanisms without payments that are (group) strategyproof for any given cost function, and achieve a good approximation ratio for the social cost and/or the maximum cost of the agents. We present a randomized mechanism, called Equal Cost , which is group strategyproof and achieves a bounded approximation ratio for all k and n , for any given concave cost function. The approximation ratio is at most 2 for Max Cost and at most n for Social Cost . To the best of our knowledge, this is the first mechanism with a bounded approximation ratio for instances with \(k \ge 3\) facilities and any number of agents. Our result implies an interesting separation between deterministic mechanisms, whose approximation ratio for Max Cost jumps from 2 to unbounded when k increases from 2 to 3, and randomized mechanisms, whose approximation ratio remains at most 2 for all k . On the negative side, we exclude the possibility of a mechanism with the properties of Equal Cost for strictly convex cost functions. We also present a randomized mechanism, called Pick the Loser , which applies to instances with k facilities and only \(n = k+1\) agents. For any given concave cost function, Pick the Loser is strongly group strategyproof and achieves an approximation ratio of 2 for Social Cost .

Description: We give a deterministic #SAT algorithm for de Morgan formulas of size up to \(n^{2.63}\) , which runs in time \(2^{n-n^{{\varOmega }(1)}}\) . This improves upon the deterministic #SAT algorithm of Chen et al. (Proceedings of the twenty-ninth annual IEEE conference on computational complexity, 2014 ), which has similar running time but works only for formulas of size less than \(n^{2.5}\) . Our new algorithm is based on the shrinkage of de Morgan formulas under random restrictions, shown by Paterson and Zwick (Random Struct Algorithms 4(2):135–150, 1993 ). We prove a concentrated and constructive version of their shrinkage result. Namely, we give a deterministic polynomial-time algorithm that selects variables in a given de Morgan formula so that, with high probability over the random assignments to the chosen variables, the original formula shrinks in size, when simplified using a given deterministic polynomial-time formula-simplification algorithm.

Description: We consider Conditional random fields ( CRFs ) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) \(x_1\ldots x_n\) is the sum of terms over intervals [ i ,  j ] where each term is non-zero only if the substring \(x_i\ldots x_j\) equals a prespecified pattern w . Such CRFs can be naturally applied to many sequence tagging problems. We present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively \(O(\textit{nL})\) , \(O(\textit{nL} \ell _{\max })\) and \(O(\textit{nL} \min \{|D|,\log (\ell _{\max }\!+\!1)\})\) where L is the combined length of input patterns, \(\ell _{\max }\) is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of Ye et al. (NIPS, 2009 ) whose complexities are respectively \(O(\textit{nL} |D|)\) , \(O\left( n |\varGamma | L^2 \ell _{\max }^2\right) \) and \(O(\textit{nL} |D|)\) , where \(|\varGamma |\) is the number of input patterns. In addition, we give an efficient algorithm for sampling, and revisit the case of MAP with non-positive weights.

Description: Estimating the number of triangles in graph streams using a limited amount of memory has become a popular topic in the last decade. Different variations of the problem have been studied, depending on whether the graph edges are provided in an arbitrary order or as incidence lists. However, with a few exceptions, the algorithms have considered insert-only streams. We present a new algorithm estimating the number of triangles in dynamic graph streams where edges can be both inserted and deleted. We show that our algorithm achieves better time and space complexity than previous solutions for various graph classes, for example sparse graphs with a relatively small number of triangles. Also, for graphs with constant transitivity coefficient, a common situation in real graphs, this is the first algorithm achieving constant processing time per edge. The result is achieved by a novel approach combining sampling of vertex triples and sparsification of the input graph. In the course of the analysis of the algorithm we present a lower bound on the number of pairwise independent 2-paths in general graphs which might be of independent interest. At the end of the paper we discuss lower bounds on the space complexity of triangle counting algorithms that make no assumptions on the structure of the graph.

Description: We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets (denoted Identifying Code , (Open) Open Locating-Dominating Set and Metric Dimension ) of an interval or a permutation graph. In these problems, one asks to distinguish all vertices of a graph by a subset of the vertices, using either the neighbourhood within the solution set or the distances to the solution vertices. Using a general reduction for this class of problems, we prove that the decision problems associated to these four notions are NP-complete, even for interval graphs of diameter 2 and permutation graphs of diameter 2. While Identifying Code and (Open) Locating-Dominating Set are trivially fixed-parameter-tractable when parameterized by solution size, it is known that in the same setting Metric Dimension is W [2]-hard. We show that for interval graphs, this parameterization of Metric Dimension is fixed-parameter-tractable.

Description: The study investigated the feasibility of conducting a future Randomised Controlled Trial (RCT) of a mobile health (mHealth) intervention for weight loss and HbA1c reduction in Type 2 Diabetes Mellitus (T2DM).

Description: A growing number of physicians are using social media as a professional platform for health communication. The purpose of this study was to understand perspectives and experiences of these “early adopter” phys...

Description: The volume of research published in the biomedical domain has increasingly lead to researchers focussing on specific areas of interest and connections between findings being missed. Literature based discovery ...

Description: To facilitate long-term safety surveillance of marketing drugs, many spontaneously reporting systems (SRSs) of ADR events have been established world-wide. Since the data collected by SRSs contain sensitive pe...

Description: Cardiac rehabilitation (CR) can slow or reverse the progression of cardiovascular disease (CVD). However, uptake of community-based CR is very low. E-cardiology, e-health and technology solutions for physical ...

Description: Risk prediction models have been proposed for various diseases and are being improved as new predictors are identified. A major challenge is to determine whether the newly discovered predictors improve risk pr...

Description: Despite considerable international eHealth impetus, there is no guidance on the development of online clinical care pathways. Advances in diagnostics now enable self-testing with home diagnosis, to which compr...

Description: Nearest neighbor (NN) imputation algorithms are efficient methods to fill in missing data where each missing value on some records is replaced by a value obtained from related cases in the whole set of records...

Description: In biomedical research, data sharing and information exchange are very important for improving quality of care, accelerating discovery, and promoting the meaningful secondary use of clinical data. A big concer...

Description: The study on disease-disease association has been increasingly viewed and analyzed as a network, in which the connections between diseases are configured using the source information on interactome maps of bio...

Description: Accurately assessing pain for those who cannot make self-report of pain, such as minimally responsive or severely brain-injured patients, is challenging. In this paper, we attempted to address this challenge b...

Description: Given a partition of an n element set into equivalence classes, we study the problem of assigning unique labels to these elements in order to support the query that asks whether the elements corresponding to two given labels belong to the same equivalence class. This has various applications including for testing whether two vertices are in the same connected component in an undirected graph or in the same strongly connected component in a directed graph. We consider the problem in several models. Concerning labeling schemes where we assign labels to elements and the query is to be answered just by examining the labels of the queried elements (without any extra space): if each vertex is required to have a unique label, then we show that a label space of \(\sum _{i=1}^n \lfloor {n \over i} \rfloor \) is necessary and sufficient. In other words, \(\lg n + \lg \lg n + O(1)\) bits of space are necessary and sufficient for representing each of the labels. This slightly strengthens the known lower bound and is in contrast to the known necessary and sufficient bound of \(\lceil \lg n \rceil \) for the label length, if each vertex need not get a unique label. Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set \(\{1,\ldots , n\}\) , we first show that \(\varTheta (\sqrt{n})\) bits are necessary and sufficient to represent the equivalence class information. This space includes the space for implicitly encoding the vertex labels. We can support the query in such a structure in O (1) time in the standard word RAM model. We also develop a dynamic structure that uses \(O(\sqrt{n} \lg n)\) bits to support equivalence queries and unions in \(O(\lg n/\lg \lg n)\) worst case time or \(O(\alpha (n))\) expected amortized time where \(\alpha (n)\) is the inverse Ackermann function. Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set \(\{1,\ldots , cn\}\) for any constant \(c 〉 1\) , we show that \(\varTheta (\lg n)\) bits are necessary and sufficient to represent the equivalence class information. Moreover, we can support the query in such a structure in O (1) time in the standard word RAM model. We believe that our work can trigger further work on tradeoffs between label space and auxiliary data structure space for other labeling problems.

Description: We perform a thorough study of various characteristics of the asynchronous push–pull protocol for spreading a rumor on Erdős–Rényi random graphs \(G_{n,p}\) , for any \(p〉c\ln (n)/n\) with \(c〉1\) . In particular, we provide a simple strategy for analyzing the asynchronous push–pull protocol on arbitrary graph topologies and apply this strategy to \(G_{n,p}\) . We prove tight bounds of logarithmic order for the total time that is needed until the information has spread to all nodes. Surprisingly, the time required by the asynchronous push–pull protocol is asymptotically almost unaffected by the average degree of the graph. Similarly tight bounds for Erdős–Rényi random graphs have previously only been obtained for the synchronous push protocol, where it has been observed that the total running time increases significantly for sparse random graphs. Finally, we quantify the robustness of the protocol with respect to transmission and node failures. Our analysis suggests that the asynchronous protocols are particularly robust with respect to these failures compared to their synchronous counterparts.

Description: A problem-oriented approach is one of the possibilities to organize a medical record. The problem-oriented medical record (POMR) - a structured organization of patient information per presented medical problem...

Description: Web-based interventions for smoking cessation available in Portuguese do not adhere to evidence-based treatment guidelines. Besides, all existing web-based interventions are built on proprietary platforms that...

Description: Despite international initiatives like Orphanet, it remains difficult to find up-to-date information about rare diseases. The aim of this study is to propose an exhaustive set of queries for PubMed based on te...

Description: We study connectivity relations among points, where the precise location of each input point lies in a region of uncertainty. We distinguish two fundamental scenarios under which uncertainty arises. In the favorable Best-Case Uncertainty , each input point can be chosen from a given set to yield the best possible objective value. In the unfavorable Worst-Case Uncertainty , the input set has worst possible objective value among all possible point locations, which are uncertain due, for example, to imprecise data. We consider these notions of uncertainty for the bottleneck spanning tree problem, giving rise to the following Best-Case Connectivity with Uncertainty problem: given a family of geometric regions, choose one point per region, such that the longest edge length of an associated geometric spanning tree is minimized. We show that this problem is NP-hard even for very simple scenarios in which the regions are line segments or squares. On the other hand, we give an exact solution for the case in which there are \(n+k\) regions, where k of the regions are line segments and n of the regions are fixed points. We then give approximation algorithms for cases where the regions are either all line segments or all unit discs. We also provide approximation methods for the corresponding Worst-Case Connectivity with Uncertainty problem: Given a set of uncertainty regions, find the minimal distance r such that for any choice of points, one per region, there is a spanning tree among the points with edge length at most r .

Description: We define the modular treewidth of a graph as its treewidth after contraction of modules. This parameter properly generalizes treewidth and is itself properly generalized by clique-width. We show that the number of satisfying assignments can be computed in polynomial time for CNF formulas whose incidence graphs have bounded modular treewidth. Our result generalizes known results for the treewidth of incidence graphs and is incomparable with known results for clique-width (or rank-width) of signed incidence graphs. The contraction of modules is an effective data reduction procedure. Our algorithm is the first one to harness this technique for #SAT. The order of the polynomial bounding the runtime of our algorithm depends on the modular treewidth of the input formula. We show that it is unlikely that this dependency can be avoided by proving that SAT is W[1]-hard when parameterized by the modular incidence treewidth of the given CNF formula.

Description: In a classical online network design problem, traffic requirements are gradually revealed to an algorithm. Each time a new request arrives, the algorithm has to satisfy it by augmenting the network under construction in a proper way (with no possibility of recovery). In this paper we study a natural generalization of online network design problems, where a fraction of the requests (the outliers ) can be disregarded. Now, each time a request arrives, the algorithm first decides whether to satisfy it or not, and only in the first case it acts accordingly. We cast three classical network design problems into this framework: (i) Online Steiner tree with outliers In this case a set of t terminals that belong to an n -node graph is presented, one at a time, to an algorithm. Each time a new terminal arrives, the algorithm can either discard or select it. In the latter case, the algorithm connects it to the Steiner tree under construction (initially consisting of a given root node). At the end of the process, at least k terminals must be selected. (ii) Online TSP with outliers This is the same problem as above, but with the Steiner tree replaced by a TSP tour. (iii) Online facility location with outliers In this case, we are also given a set of facility nodes, each one with an opening cost. Each time a terminal is selected, we have to connect it to some facility (and open that facility, if it is not already open). We focus on the known distribution model, where terminals are independently sampled from a given distribution. For all the above problems, we present bicriteria online algorithms that, for any constant \(\epsilon 〉0\) , select at least \((1-\epsilon )k\) terminals with high probability and pay in expectation \(O(\log ^2n)\) times more than the expected cost of the optimal offline solution (selecting k terminals). These upper bounds are complemented by inapproximability results for the case that one insists on selecting exactly k terminals, and by lower bounds including an \(\varOmega (\log n/\log \log n)\) lower bound for the case that the online algorithm is allowed to select \(\alpha \,k\) terminals only, for a sufficiently large constant \(\alpha \in (0,1)\) .

Description: A well known result in graph algorithms, due to Edmonds, states that given a digraph D and a positive integer \(\ell \) , we can test whether D contains \(\ell \) arc-disjoint out-branchings in polynomial time. However, if we ask whether there exists an out-branching and an in-branching which are arc-disjoint, then the problem becomes NP -complete. In fact, even deciding whether a digraph D contains an out-branching which is arc-disjoint from some spanning tree in the underlying undirected graph remains NP -complete. In this paper we formulate some natural optimization questions around these problems and initiate its study in the realm of parameterized complexity. More precisely, the problems we study are the following: Arc - Disjoint Branchings and Non - Disconnecting Out - Branching . In Arc - Disjoint Branchings ( Non - Disconnecting Out - Branching ), a digraph D and a positive integer k are given as input and the goal is to test whether there exist an out-branching and in-branching (respectively, a spanning tree in the underlying undirected graph) that differ on at least k arcs. We obtain the following results for these problems. Non - Disconnecting Out - Branching is fixed parameter tractable (FPT) and admits a linear vertex kernel. Arc - Disjoint Branchings is FPT on strong digraphs. The algorithm for Non - Disconnecting Out - Branching runs in time \(2^{\mathcal {O}(k)}n^{\mathcal {O}(1)}\) and the approach we use to obtain this algorithms seems useful in designing other moderately exponential time algorithms for edge/arc partitioning problems.

Description: We study the stable roommates problem in networks where players are embedded in a social context and may incorporate positive externalities into their decisions. Each player is a node in a social network and strives to form a good match with a neighboring player. We consider the existence, computation, and inefficiency of stable matchings from which no pair of players wants to deviate. We characterize prices of anarchy and stability, which capture the ratio of the total profit in the optimum matching over the total profit of the worst and best stable matching, respectively. When the benefit from a match (which we model by associating a reward with each edge) is the same for both players, we show that externalities can significantly improve the price of stability, while the price of anarchy remains unaffected. Furthermore, a good stable matching achieving the bound on the price of stability can be obtained in polynomial time. We extend these results to more general matching rewards, when players matched to each other may receive different benefits from the match. For this more general case, we show that network externalities (i.e., “caring about your friends”) can make an even larger difference and greatly reduce the price of anarchy. We show a variety of existence results and present upper and lower bounds on the prices of anarchy and stability for various structures of matching benefits. All our results on stable matchings immediately extend to the more general case of fractional stable matchings.

Description: We present the first general bounds on the mixing time of the Markov chain associated to the logit dynamics for wide classes of strategic games. The logit dynamics with inverse noise \(\beta \) describes the behavior of a complex system whose individual components act selfishly according to some partial (“noisy”) knowledge of the system, where the capacity of the agent to know the system and compute her best move is measured by parameter \(\beta \) . In particular, we prove nearly tight bounds for potential games and games with dominant strategies. Our results show that for potential games the mixing time is bounded by an exponential in \(\beta \) and in the maximum potential difference. Instead, for games with dominant strategies the mixing time cannot grow arbitrarily with \(\beta \) . Finally, we refine our analysis for a subclass of potential games called graphical coordination games, often used for modeling the diffusion of new technologies. We prove that the mixing time of the logit dynamics for these games can be upper bounded by a function that is exponential in the cutwidth of the underlying graph and in \(\beta \) . Moreover, we consider two specific and popular network topologies, the clique and the ring. For the clique, we prove an almost matching lower bound on the mixing time of the logit dynamics that is exponential in \(\beta \) and in the maximum potential difference, while for the ring we prove that the time of convergence of the logit dynamics to its stationary distribution is significantly shorter.

Description: Given a plane graph G (i.e., a planar graph with a fixed planar embedding and outer face) and a biconnected subgraph \(G^{\prime }\) with a fixed planar straight-line convex drawing, we consider the question whether this drawing can be extended to a planar straight-line drawing of G . We characterize when this is possible in terms of simple necessary conditions, which we prove to be sufficient. This also leads to a linear-time testing algorithm. If a drawing extension exists, one can be computed in the same running time.

Description: In communicating chronic risks, there is increasing use of a metaphor that can be termed ‘effective-age’: the age of a ‘healthy’ person who has the same risk profile as the individual in question. Popular meas...

Description: Administrative health care data are frequently used to study disease burden and treatment outcomes in many conditions including osteoarthritis (OA). OA is a chronic condition with significant disease burden af...

Description: Mobile phone technology is utilized for better delivery of health services worldwide. In low-and-middle income countries mobile phones are now ubiquitous. Thus leveraging mHealth applications in health sector ...

Description: The use of telemonitoring is a promising approach to optimizing outcomes in the treatment of heart failure (HF) for patients living in the community. HF telemonitoring interventions, however, have not been tes...

Description: The rotor–router model , also called the Propp machine , was first considered as a deterministic alternative to the random walk. The edges adjacent to each node  v (or equivalently, the exit ports at  v ) are arranged in a fixed cyclic order, which does not change during the exploration. Each node  v maintains a port pointer   \(\pi _v\) which indicates the exit port to be adopted by an agent on the conclusion of the next visit to this node (the “next exit port”). The rotor–router mechanism guarantees that after each consecutive visit at the same node, the pointer at this node is moved to the next port in the cyclic order. It is known that, in an undirected graph  G with  m edges, the route adopted by an agent controlled by the rotor–router mechanism eventually forms an Euler tour based on arcs obtained via replacing each edge in  G by two arcs with opposite direction. The process of ushering the agent to an Euler tour is referred to as the lock-in problem . In Yanovski et al. (Algorithmica 37(3):165–186, 2003 ), it was proved that, independently of the initial configuration of the rotor–router mechanism in  G , the agent locks-in in time bounded by  \(2mD\) , where \(D\) is the diameter of  G . In this paper we examine the dependence of the lock-in time on the initial configuration of the rotor–router mechanism. Our analysis is performed in the form of a game between a player \({\mathcal {P}}\) intending to lock-in the agent in an Euler tour as quickly as possible and its adversary \({\mathcal {A}}\) with the counter objective. We consider all cases of who decides the initial cyclic orders and the initial values \(\pi _v\) . We show, for example, that if \({\mathcal {A}}\) provides its own port numbering after the initial setup of pointers by \({\mathcal {P}}\) , the worst-case complexity of the lock-in problem is \({\varTheta }(m\cdot \min \{\log m,D\})\) . We also investigate the robustness of the rotor–router graph exploration in presence of faults in the pointers \(\pi _v\) or dynamic changes in the graph. We show, for example, that after the exploration establishes an Eulerian cycle, if k edges are added to the graph, then a new Eulerian cycle is established within \(\mathcal {O}(km)\) steps.

Description: While, lost to follow-up (LTFU) from antiretroviral therapy (ART) can be considered a catch-all category for patients who miss scheduled visits or medication pick-ups, operational definitions and methods for d...

Description: Consider the problem of selecting k items that maximize the value of a monotone submodular set function f , where f can be accessed using value queries. It is well known that polynomially many queries suffice in order to obtain an approximation ratio of \(1 - \frac{1}{e}\) . We consider a variation on this problem in which the value queries are required to be of uniform size: each queried set, like the desired solution itself, must contain k items. We show that polynomially many uniform size queries suffice in order to obtain an approximation ratio of \(\frac{1}{2}\) , and that an approximation ratio of \(\frac{1 + \epsilon }{2}\) requires a number of queries that is exponential in \(\epsilon k\) . For the interesting special case of coverage functions, we show that an approximation ratio strictly better than \(\frac{1}{2}\) is attainable with polynomially many uniform size queries. The “uniform size” requirement is motivated by situations in which a firm may offer a menu of exactly k items to its clients, where k is a parameter determined by external considerations. Performing a query corresponds to physically changing the identities of the items offered, and the reply to the query is deduced by observing the behavior of clients in response to the change. Queries that involve a number of items that differs from k may not be desirable due to these external considerations. In such situations it is natural to ask whether the same approximation ratios that can be guaranteed by general value queries can also be obtained by uniform size queries.

Description: In this paper, we study the approximability of the Maximum Labeled Path problem: given a vertex-labeled directed acyclic graph D , find a path in D that collects a maximum number of distinct labels. For any \(\epsilon 〉0\) , we provide a polynomial time approximation algorithm that computes a solution of value at least \(OPT^{1-\epsilon }\) and a self-reduction showing that any constant ratio approximation algorithm for this problem can be converted into a PTAS. This last result, combined with the APX -hardness of the problem, shows that the problem cannot be approximated within any constant ratio unless \(P=NP\) .

Description: We present the first results on the parameterized complexity of reconfiguration problems, where a reconfiguration variant of an optimization problem \(\mathcal {Q}\) takes as input two feasible solutions S and T and determines if there is a sequence of reconfiguration steps, i.e. a reconfiguration sequence, that can be applied to transform S into T such that each step results in a feasible solution to \(\mathcal {Q}\) . For most of the results in this paper, S and T are sets of vertices of a given graph and a reconfiguration step adds or removes a vertex. Our study is motivated by results establishing that for many NP -hard problems, the classical complexity of reconfiguration is PSPACE -complete. We address the question for several important graph properties under two natural parameterizations: k , a bound on the size of solutions, and \(\ell \) , a bound on the length of reconfiguration sequences. Our first general result is an algorithmic paradigm, the reconfiguration kernel, used to obtain fixed-parameter tractable algorithms for reconfiguration variants of Vertex Cover and, more generally, Bounded Hitting Set and Feedback Vertex Set , all parameterized by k . In contrast, we show that reconfiguring Unbounded Hitting Set is W[2] -hard when parameterized by \(k+\ell \) . We also demonstrate the W[1] -hardness of reconfiguration variants of a large class of maximization problems parameterized by \(k+\ell \) , and of their corresponding deletion problems parameterized by \(\ell \) ; in doing so, we show that there exist problems in FPT when parameterized by k , but whose reconfiguration variants are W[1] -hard when parameterized by \(k+\ell \) .

Description: The greedy spanner is the highest quality geometric spanner (in e.g. edge count and weight, both in theory and practice) known to be computable in polynomial time. Unfortunately, all known algorithms for computing it on n points take \(\varOmega (n^2)\) time, limiting its applicability on large data sets. We propose a novel algorithm design which uses the observation that for many point sets, the greedy spanner has many ‘short’ edges that can be determined locally and usually quickly. To find the usually few remaining ‘long’ edges, we use a combination of already determined local information and the well-separated pair decomposition. We give experimental results showing large to massive performance increases over the state-of-the-art on nearly all tests and real-life data sets. On the theoretical side we prove a near-linear expected time bound on uniform point sets and a near-quadratic worst-case bound. Our bound for point sets drawn uniformly and independently at random in a square follows from a local characterization of t -spanners we give on such point sets. We give a geometric property that holds with high probability, which in turn implies that if an edge set on these points has t -paths between pairs of points ‘close’ to each other, then it has t -paths between all pairs of points. This characterization gives an \(O(n \log ^2 n \log ^2 \log n)\) expected time bound on our greedy spanner algorithm, making it the first subquadratic time algorithm for this problem on any interesting class of points. We also use this characterization to give an \(O((n + |E|) \log ^2 n \log \log n)\) expected time algorithm on uniformly distributed points that determines whether E is a t -spanner, making it the first subquadratic time algorithm for this problem that does not make assumptions on E .

Description: Let \(\mathcal {D} = \{\mathsf {T}_1,\mathsf {T}_2, \ldots ,\mathsf {T}_D\}\) be a collection of D string documents of n characters in total, that are drawn from an alphabet set \(\varSigma =[\sigma ]\) . The top-k document retrieval problem is to preprocess \(\mathcal{D}\) into a data structure that, given a query \((P[1\ldots p],k)\) , can return the k documents of \(\mathcal{D}\) most relevant to the pattern P . The relevance is captured using a predefined ranking function, which depends on the set of occurrences of P in \(\mathsf {T}_d\) . For example, it can be the term frequency (i.e., the number of occurrences of P in \(\mathsf {T}_d\) ), or it can be the term proximity (i.e., the distance between the closest pair of occurrences of P in \(\mathsf {T}_d\) ), or a pattern-independent importance score of \(\mathsf {T}_d\) such as PageRank. Linear space and optimal query time solutions already exist for the general top- k document retrieval problem. Compressed and compact space solutions are also known, but only for a few ranking functions such as term frequency and importance. However, space efficient data structures for term proximity based retrieval have been evasive. In this paper we present the first sub-linear space data structure for this relevance function, which uses only o ( n ) bits on top of any compressed suffix array of \(\mathcal{D}\) and solves queries in \(O((p+k) {{\mathrm{polylog}}}\,\,n)\) time. We also show that scores that consist of a weighted combination of term proximity, term frequency, and document importance, can be handled using twice the space required to represent the text collection.

Description: We study the parameterized complexity of Geometric Graph Isomorphism (Known as the Point Set Congruence problem in computational geometry): given two sets of n points A and B with rational coordinates in k -dimensional euclidean space, with k as the fixed parameter, the problem is to decide if there is a bijection \(\pi :A \rightarrow B\) such that for all \(x,y \in A\) , \(\Vert x-y\Vert = \Vert \pi (x)-\pi (y)\Vert \) , where \(\Vert \cdot \Vert \) is the euclidean norm. Our main result is the following: We give a \(O^*(k^{O(k)})\) time (The \(O^*(\cdot )\) notation here, as usual, suppresses polynomial factors) FPT algorithm for Geometric Isomorphism. This is substantially faster than the previous best time bound of \(O^*(2^{O(k^4)})\) for the problem (Evdokimov and Ponomarenko in Pure Appl Algebra 117–118:253–276, 1997 ). In fact, we show the stronger result that even canonical forms for finite point sets with rational coordinates can also be computed in \(O^*(k^{O(k)})\) time. We also briefly discuss the isomorphism problem for other \(l_p\) metrics. Specifically, we describe a deterministic polynomial-time algorithm for finite point sets in \(\mathbb {Q}^2\) .

Description: We present deterministic and randomized algorithms for the problem of online packet routing in grids in the competitive network throughput model (Aiello et al. in SODA, pp 771–780 2003 ). In this model the network has nodes with bounded buffers and bounded link capacities. The goal in this model is to maximize the throughput, i.e., the number of delivered packets. Our deterministic algorithm is the first online algorithm with an \(O\left( \log ^{O(1)}(n)\right) \) competitive ratio for uni-directional grids (where n denotes the size of the network). The deterministic online algorithm is centralized and handles packets with deadlines. This algorithm is applicable to various ranges of values of buffer sizes and communication link capacities. In particular, it holds for buffer size and communication link capacity in the range \([3 \ldots \log n]\) . Our randomized algorithm achieves an expected competitive ratio of \(O(\log n)\) for the uni-directional line. This algorithm is applicable to a wide range of buffer sizes and communication link capacities. In particular, it holds also for unit size buffers and unit capacity links. This algorithm improves the best previous \(O(\log ^2 n)\) -competitive ratio of Azar and Zachut (ESA, pp 484–495, 2005 ).

Description: Improving retention in prevention of mother to child transmission (PMTCT) of HIV programs is critical to optimize maternal and infant health outcomes, especially now that lifelong treatment is immediate regard...

Description: As health care becomes more complex, it becomes more important for clinicians and patients to share information. Electronic health information exchange can help address this need. To this end, all provinces an...

Description: The survival of patients with breast cancer is highly sporadic, from a few months to more than 15 years. In recent studies, the gene expression profiling of tumors has been used as a promising means of predict...

Description: Identifying subtypes of complex diseases such as cancer is the very first step toward developing highly customized therapeutics on such diseases, as their origins significantly vary even with similar physiolog...

Description: The Variome corpus, a small collection of published articles about inherited colorectal cancer, includes annotations of 11 entity types and 13 relation types related to the curation of the relationship between...

Description: Risk calculation is increasingly used in lipid management, congestive heart failure, and atrial fibrillation. The risk scores are then used for decisions about statin use, anticoagulation, and implantable defi...

Description: The utilization of routine health information systems (HIS) for surveillance of assisted partner services (aPS) for HIV in sub-Saharan is sub-optimal, in part due to poor data quality and limited use of inform...

Description: A specific Electronic Health Record (EHR) for ophthalmology was introduced in an academic center in Germany. As diagnoses coding corresponding to the International Classification of Diseases Version 10 (ICD-10...

Description: In the Shortest Superstring problem we are given a set of strings \(S=\{s_1, \ldots , s_n\}\) and integer \(\ell \) and the question is to decide whether there is a superstring s of length at most \(\ell \) containing all strings of S as substrings. We obtain several parameterized algorithms and complexity results for this problem. In particular, we give an algorithm which in time \(2^{\mathcal {O}(k)} {\text {poly}}(n)\) finds a superstring of length at most \(\ell \) containing at least k strings of S . We complement this by a lower bound showing that such a parameterization does not admit a polynomial kernel up to some complexity assumption. We also obtain several results about “below guaranteed values” parameterization of the problem. We show that parameterization by compression admits a polynomial kernel while parameterization “below matching” is hard.

Description: We prove that given a bipartite graph G with vertex set V and an integer  k , deciding whether there exists a subset of V of size at most k hitting all maximal independent sets of G is complete for the class \(\varSigma_{2}^{\mathrm{P}}\) .

Description: We present the first approximate distance oracle for sparse directed networks with time-dependent arc-travel-times determined by continuous, piecewise linear, positive functions possessing the FIFO property. Our approach precomputes \((1+\varepsilon )\) -approximate distance summaries from selected landmark vertices to all other vertices in the network. Our oracle uses subquadratic space and time preprocessing, and provides two sublinear-time query algorithms that deliver constant and \((1+\sigma )\) -approximate shortest-travel-times, respectively, for arbitrary origin–destination pairs in the network, for any constant \(\sigma 〉 \varepsilon \) . Our oracle is based only on the sparsity of the network, along with two quite natural assumptions about travel-time functions which allow the smooth transition towards asymmetric and time-dependent distance metrics.

Description: A Bloom filter is a method for reducing the space (memory) required for representing a set by allowing a small error probability. In this paper we consider a Sliding Bloom Filter: a data structure that, given a stream of elements, supports membership queries of the set of the last n elements (a sliding window), while allowing a small error probability and a slackness parameter. The problem of sliding Bloom filters has appeared in the literature in several communities, but this work is the first theoretical investigation of it. We formally define the data structure and its relevant parameters and analyze the time and memory requirements needed to achieve them. We give a low space construction that runs in \(O(1)\) time per update with high probability (that is, for all sequences with high probability all operations take constant time) and provide an almost matching lower bound on the space that shows that our construction has the best possible space consumption up to an additive lower order term.

Description: We study the complexity of the Channel Assignment problem. By applying the meet-in-the-middle approach we get an algorithm for the \(\ell \) -bounded Channel Assignment (when the edge weights are bounded by \(\ell \) ) running in time \(O^*((2\sqrt{\ell +1})^n)\) . This is the first algorithm which breaks the \((O(\ell ))^n\) barrier. We extend this algorithm to the counting variant, at the cost of slightly higher polynomial factor. Very recently the second author showed that Channel Assignment does not admit a \(O(c^n)\) -time algorithm, for a constant c independent of \(\ell \) . We consider a similar question for Generalized \(T\) - Coloring , a CSP problem that generalizes Channel Assignment . We show that Generalized \(T\) - Coloring   does not admit a \(2^{2^{o\left( \sqrt{n}\right) }} \mathrm{poly}(r)\) -time algorithm, where r is the size of the instance.

Description: We introduce and investigate a new notion of resilience in graph spanners. Let \(S\) be a spanner of a weighted graph \(G\) . Roughly speaking, we say that \(S\) is resilient if all its point-to-point distances are resilient to edge failures. Namely, whenever any edge in \(G\) fails, then as a consequence of this failure all distances do not degrade in \(S\) substantially more than in \(G\) (i.e., the relative distance increases in \(S\) are very close to those in the underlying graph \(G\) ). In this paper we show that sparse resilient spanners exist, and that they can be computed efficiently.