Constant factor approximation for the weighted partial degree bounded edge packing problem

In the partial degree bounded edge packing problem (PDBEP), the input is an undirected graph \(G=(V,E)\) with capacity \(c_v\in {\mathbb {N}}\) on each vertex v. The objective is to find a feasible subgraph \(G'=(V,E')\) maximizing \(|E'|\), where \(G'\) is said to be feasible if for each \(e=\{u,v\}\in E'\), \(\deg _{G'}(u)\le c_u\) or \(\deg _{G'}(v)\le c_v\). In the weighted version of the problem, additionally each edge \(e\in E\) has a weight w(e) and we want to find a feasible subgraph \(G'=(V,E')\) maximizing \(\sum _{e\in E'} w(e)\). The problem is already NP-hard if \(c_v = 1\) for all \(v\in V\) (Zhang in: Proceedings of the joint international conference on frontiers in algorithmics and algorithmic aspects in information and management, FAW-AAIM 2012, Beijing, China, May 14–16, pp 359–367, 2012). In this paper, we introduce a generalization of the PDBEP problem. We let the edges have weights as well as demands, and we present the first constant-factor approximation algorithms for this problem. Our results imply the first constant-factor approximation algorithm for the weighted PDBEP problem, improving the result of Aurora et al. (FAW-AAIM 2013) who presented an \(O(\log n)\)-approximation for the weighted case. We also study the weighted PDBEP problem on hypergraphs and present a constant factor approximation if the maximum degree of the hypergraph is bounded above by a constant. We study a generalization of the weighted PDBEP problem with demands where each edge additionally specifies whether it requires at least one, or both its end-points to not exceed the capacity. The objective is to pick a maximum weight subset of edges. We give a constant factor approximation for this problem. We also present a PTAS for the weighted PDBEP problem with demands on H-minor free graphs, if the demands on the edges are bounded by polynomial. We show that the PDBEP problem is APX-hard even for bipartite graphs with \(c_v = 1, \; \forall v\in V\) and having degree at most 3.     

FPT algorithms for Connected Feedback Vertex Set

We study the recently introduced Connected Feedback Vertex Set (CFVS) problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical Feedback Vertex Set problem and is defined as follows: given a graph G=(V,E) and an integer k, decide whether there exists F?V, |F|??k, such that G[V?F] is a forest and G[F] is connected. We show that Connected Feedback Vertex Set can be solved in time O(2 ^O(k) n ^O(1)) on general graphs and in time $O(2^{O(\sqrt{k}\log k)}n^{O(1)})$ on graphs excluding a fixed graph H as a minor. Our result on general undirected graphs uses, as a subroutine, a parameterized algorithm for Group Steiner Tree, a well studied variant of Steiner Tree. We find the algorithm for Group Steiner Tree of independent interest and believe that it could be useful for obtaining parameterized algorithms for other connectivity problems.     

LBI tests for the detection of compound normal distribution in control and treatment populations

Independent samples are drawn from control and treatment populations with normal and compound normal distributions respectively. We derive the locally best invariant (LBI) tests through Wijsman’s representation for the detection of mixture departures from the normal distribution. These tests may be viewed as tests for the equality of control and treatment populations. Further, they are optimally robust for the model considered by Durairajan and Raman (1994).     

Improving Intimate Partner Violence Services in Home Visiting: A Multisite Learning Collaborative Approach

Abstract

To improve intimate partner violence (IPV) service delivery, the Florida Maternal, Infant, and Early Childhood Home Visiting (MIECHV) Initiative’s continuous quality improvement (CQI) team implemented a Breakthrough Series model Learning Collaborative with eight program sites. Using mixed-methods, we: examined post-Collaborative changes in Florida MIECHV home visitors’ knowledge, system awareness, and confidence; identified strategies to address challenges in supporting families with IPV; and assessed post-Collaborative program improvements. The Collaborative included three interactive 2-day sessions, six webinars, and testing strategies using the Model for Improvement (Plan-Do-Study-Act). Three online surveys assessed changes influencing IPV screening, referrals, and safety planning. Thematic content analysis of qualitative data revealed existing barriers and strategies to address challenges. Home visitors reported accurate knowledge (change: 2.3%-34.8%), confidence (change: 31.8%-37.9%), and system awareness (change: 22.7%-53.5%) for all items from baseline to final survey. There was also an increase in rates of IPV screening (change: 88.0%-91.0%) and referrals (change: 43.0%-100.0%). Strategies for addressing challenges in supporting families experiencing IPV were identified at the individual (self-care, continuous education); interpersonal (reflective supervision, trauma-informed approach); organizational (defining success, supportive agency/program, policies); and community (collaboration with IPV service providers) levels. Lessons learned from the MIECHV IPV Learning Collaborative informed future CQI projects.