Search

In 1982, Drezner proposed the (1|1)-centroid problem on the plane, in which two players, called the leader and the follower, open facilities to provide service to customers in a competitive manner. The leader opens the first facility, and then the follower opens the second. Each customer will patronize the facility closest to him (ties broken in favor of the leader's one), thereby decides the market share of the two players. The goal is to find the best position for the leader's facility so that his market share is maximized. The best algorithm for this problem is an $O(n^2 \log n)$-time parametric search approach, which searches over the space of possible market share values. In the same paper, Drezner also proposed a general version of (1|1)-centroid problem by introducing a minimal distance constraint $R$, such that the follower's facility is not allowed to be located within a distance $R$ from the leader's. He proposed an $O(n^5 \log n)$-time algorithm for this general version by identifying $O(n^4)$ points as the candidates of the optimal solution and checking the market share for each of them. In this paper, we develop a new parametric search approach searching over the $O(n^4)$ candidate points, and present an $O(n^2 \log n)$-time algorithm for the general version, thereby close the $O(n^3)$ gap between the two bounds., 27 pages, 6 figures. A preliminary version of this paper has been submitted to ISAAC 2016

We consider capacitated vertex cover with hard capacity constraints (VC-HC) on hypergraphs. In this problem we are given a hypergraph $G=(V,E)$ with a maximum edge size $f$. Each edge is associated with a demand and each vertex is associated with a weight (cost), a capacity, and an available multiplicity. The objective is to find a minimum-weight vertex multiset such that the demands of the edges can be covered by the capacities of the vertices and the multiplicity of each vertex does not exceed its available multiplicity. In this paper we present an $O(f)$ bi-approximation for VC-HC that gives a trade-off on the number of augmented multiplicity and the cost of the resulting cover. In particular, we show that, by augmenting the available multiplicity by a factor of $k \ge 2$, a~cover with a cost ratio of $\Big(1+\frac{1}{k-1}\Big)(f-1)$ to the optimal cover for the original instance can be obtained. This improves over a previous result, which has a cost ratio of $f^2$ via augmenting the available multiplicity by a factor of $f$.

We consider the problem of computing the time-convex hull of a point set under the general $L_p$ metric in the presence of a straight-line highway in the plane. The traveling speed along the highway is assumed to be faster than that off the highway, and the shortest time-path between a distant pair may involve traveling along the highway. The time-convex hull ${TCH}(P)$ of a point set $P$ is the smallest set containing both $P$ and \emph{all} shortest time-paths between any two points in ${TCH}(P)$. In this paper we give an algorithm that computes the time-convex hull under the $L_p$ metric in optimal $O(n\log n)$ time for a given set of $n$ points and a real number $p$ with $1\le p \le \infty$.

We consider the problem of online dynamic power management that provides hard real-time guarantees. In this problem, each of the given jobs is associated with an arrival time, a deadline, and an execution time, and the objective is to decide a schedule of the jobs as well as a sequence of state transitions on the processors so as to minimize the total energy consumption. In this paper, we examine the problem complexity and provide online strategies to achieve energy-efficiency. First, we show that the competitive factor of any online algorithm for this problem is at least 2.06. Then we present an online algorithm which gives a 4-competitive schedule. When the execution times of the jobs are unit, we show that the competitive factor improves to 3.59. At the end, the algorithm is generalized to allow a trade-off between the number of processors we use and the energy-efficiency of the resulting schedule.

We investigate higher-order Voronoi diagrams in the city metric. This metric is induced by quickest paths in the L1 metric in the presence of an accelerating transportation network of axis-parallel line segments. For the structural complexity of kth-order city Voronoi diagrams of n point sites, we show an upper bound of O(k(n - k) + kc) and a lower bound of {\Omega}(n + kc), where c is the complexity of the transportation network. This is quite different from the bound O(k(n - k)) in the Euclidean metric. For the special case where k = n - 1 the complexity in the Euclidean metric is O(n), while that in the city metric is {\Theta}(nc). Furthermore, we develop an O(k^2(n + c) log n)-time iterative algorithm to compute the kth-order city Voronoi diagram and an O(nc log^2(n + c) log n)-time divide-and-conquer algorithm to compute the farthest-site city Voronoi diagram., Comment: 15 pages, extended version of paper to appear in Proc. 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'12), Helsinki, Finland, 2012

We consider the capacitated domination problem, which models a service-requirement assigning scenario and which is also a generalization of the dominating set problem. In this problem, we are given a graph with three parameters defined on the vertex set, which are cost, capacity, and demand. The objective of this problem is to compute a demand assignment of least cost, such that the demand of each vertex is fully-assigned to some of its closed neighbours without exceeding the amount of capacity they provide. In this paper, we provide the first constant factor approximation for this problem on planar graphs, based on a new perspective on the hierarchical structure of outer-planar graphs. We believe that this new perspective and technique can be applied to other capacitated covering problems to help tackle vertices of large degrees.

Publication in the conference proceedings of EUSIPCO, Antalya, Turkey, 2005

Objectives The qualitative study was conducted within the international “Transcultural study of postnatal depression (PND)” in 17 centres located in 13 different countries. The aim was to explore perceptions of PND by lay and professional key informants, specifically regarding description of symptoms, awareness of this pathology and of possible care. Methods Broad areas of inquiry and open-ended probes were developed by the TCS-PND research group during international workshops to obtain data comparable between countries on perceptions of PND. A non-random convenience sampling method was used to recruit postpartum mothers for focus groups, and fathers and grandmothers for interviews. Influential healthcare planners and clinicians were interviewed as professional key informants in each centre. Within sites, transcripts of focus groups and interviews underwent a process of text analysis in the original language until exhaustive theme extraction was achieved. Themes (in English) from all the centres were combined into broader categories and after consensus discussions these categories were revalidated. Results and discussion Qualitative data were supplemented in each centre with sociodemographic data to address the issues of: (i) whether perceptions of PND are related to some specific cultural perception of mental heath and/or of status of parenthood and (ii) how high or low levels of general care and specificity of health policy relate to differences in perception of needs for care. Data collected using the same probes and methodology in different countries and cultures has enabled a comparative analysis of perceptions of PND. In addition it has shown that, although not described with the same words, PND is a well-recognised condition by recent mothers in all countries in this study. Data on focus groups and interviews from selected countries are given in the following abstracts to illustrate some similarities and differences in perceptions between countries.

1. This study has demonstrated that great efforts have been made by the Hospital Authority and the studied hospital cluster to contain and prevent infection, and that high levels of vigilance have been enforced in anticipation of future outbreaks of SARS and other droplet infections. 2. Most health care workers and support workers have good hospital infection control and isolation precaution knowledge levels. 3. Compliance with infection control guidelines is satisfactory and has increased compared with previous studies. 4. Most participants had positive perceptions of the guidelines and found the training programmes useful. 5. This study has identified several structures and infection control practice areas that need strengthening, including improving the clarity of some guidelines and minimising barriers to their implementation.

We present an efficient reduction mapping undirected graphs G with n = 2^k vertices for integers k to tables of partiallyspecified Boolean functions g: {0,1}^(4k+1) -> {0,1,*}so that for any integer m, G has a vertex colouringusing m colours if and only if g has a consistent ordered binarydecision diagram with at most (2m + 2)n^2 + 4n decision nodes.From this it follows that the problem of finding a minimum-sizedconsistent OBDD for an incompletely specified truth table is NP-hard and also hard to approximate.