Approximating <Emphasis Type="Italic">k</Emphasis>-generalized connectivity via collapsing HSTs

An instance of the k -generalized connectivity problem consists of an undirected graph G=(V,E), whose edges are associated with non-negative costs, and a collection \({\mathcal{D}}=\{(S_{1},T_{1}),\ldots,(S_{d},T_{d})\}\) of distinct demands, each of which comprises a pair of disjoint vertex sets. We say that a subgraph ??G connects a demand (S _i ,T _i ) when it contains a path with one endpoint in S _i and the other in T _i . Given an integer parameter k, the goal is to identify a minimum cost subgraph that connects at least k demands in \({\mathcal{D}}\).Alon, Awerbuch, Azar, Buchbinder and Naor (SODA ’04) seem to have been the first to consider the generalized connectivity paradigm as a unified machinery for incorporating multiple-choice decisions into network formation settings. Their main contribution in this context was to devise a multiplicative-update online algorithm for computing log-competitive fractional solutions, and to propose provably-good rounding procedures for important special cases. Nevertheless, approximating the generalized connectivity problem in its unconfined form, where one makes no structural assumptions about the underlying graph and collection of demands, has remained an open question up until a recent O(log?² nlog?² d) approximation due to Chekuri, Even, Gupta and Segev (SODA ’08). Unfortunately, the latter result does not extend to connecting a pre-specified number of demands. Furthermore, even the simpler case of singleton demands has been established as a challenging computational task, when Hajiaghayi and Jain (SODA ’06) related its inapproximability to that of dense k -subgraph.In this paper, we present the first non-trivial approximation algorithm for k-generalized connectivity, which is derived by synthesizing several techniques originating in probabilistic embeddings of finite metrics, network design, and randomization. Specifically, our algorithm constructs, with constant probability, a feasible subgraph whose cost is within a factor of O(n ^2/3?polylog(n,k)) of optimal. We believe that the fundamental approach illustrated in the current writing is of independent interest, and may be applicable in other settings as well.     

Mobile facility location: combinatorial filtering via weighted occupancy

An instance of the mobile facility location problem consists of a complete directed graph \(G = (V, E)\) , in which each arc \((u, v) \in E\) is associated with a numerical attribute \(\mathcal M (u,v)\) , representing the cost of moving any object from \(u\) to \(v\) . An additional ingredient of the input is a collection of servers \(S = \{ s_1, \ldots , s_k \}\) and a set of clients \(C = \{ c_1, \ldots , c_\ell \}\) , which are located at nodes of the underlying graph. With this setting in mind, a movement scheme is a function \(\psi : S \rightarrow V\) that relocates each server \(s_i\) to a new position, \(\psi ( s_i )\) . We refer to \(\mathcal M ( s_i, \psi ( s_i ) )\) as the relocation cost of \(s_i\) , and to \(\min _{i \in [k]} \mathcal M (c_j, \psi ( s_i ) )\) , the cost of assigning client \(c_j\) to the nearest final server location, as the service cost of \(c_j\) . The objective is to compute a movement scheme that minimizes the sum of relocation and service costs. In this paper, we resolve an open question posed by Demaine et al. (SODA ’07) by characterizing the approximability of mobile facility location through LP-based methods. We also develop a more efficient algorithm, which is based on a combinatorial filtering approach. The latter technique is of independent interest, as it may be applicable in other settings as well. In this context, we introduce a weighted version of the occupancy problem, for which we establish interesting tail bounds, not before demonstrating that existing bounds cannot be extended.     

A note on the effect of simple equicorrelation in detecting a spurious multivariate observation

This paper examines the robustness of the multivariate version of Grubs' (1950) procedure for detecting an outlier in a sample of n independent observations against equicorrelation of the observations. It is shown that the robustness of the univariate test to equicorrelation extends to the multivariate test in that the distribution of the maximum squared radii-test for a multivariate oulier in identical for both the independent and siaply equicorrelated data models.     

Why Does Cell Implementation Stop? Factors Influencing Cell Penetration in Manufacturing Plants

There is little understanding as to why firms have various degrees of cell usage. The intent of this study was to identify factors that had arrested continued implementation of cells at surveyed manufacturing plants. We found no dominant factor that had prevented the firms from continued cellularization. However, by sub‐dividing the plants into those with low and high degrees of direct labor hours spent in cells, short and long experience with cells, and those with and without plans for further cells, a clearer pattern emerged. The inability to find families with high and stable demand, lack of time to implement more cells, the existence of service processes, and the difficulty of cost justifying new cells were the most important factors, although their relative importance varied. The findings support the notion that cellular manufacturing has broad applicability as a form of work organization and that cell users pursue further implementations until no more viable cells with sufficient utilization, demand stability, or economic value can be found.