A graph spanner is a subgraph that preserves the shortest distance between every pair of vertices within a permissible distortion. Typically, the allowed distortion is a multiplicative factor (of the original distances) and is referred to as stretch. Efficient multiplicative spanners, based on finding low diameter decompositions, have been studied in the distributed and parallel settings. Most of these studies aim to find spanners with theoretical guarantees on the stretch and spanner size. The spanner size guarantees obtained in these works are not very useful for real world sparse graphs. In this work, we evaluate and compare the state of the art algorithms for multiplicative spanners on real world and synthetic graphs. We propose a heuristic that aims to reduce the size of the output spanner. When combined with existing approaches, it admits similar theoretical guarantees as described in prior work while yielding considerably smaller spanners. Our heuristic builds on the idea of selecting centers with large neighborhoods and growing clusters around them. We present a parallel algorithm for selecting a large set of cluster centers based on this heuristic. We evaluate our algorithms on 18 real world graphs from the SNAP data set and 3 well studied synthetic graphs. We demonstrate that our heuristic yields spanners with significantly fewer edges - up to 6x smaller on real world graphs and up to 20x smaller on synthetic graphs, compared to baselines from prior work.

In this paper, we propose and analyze a local search algorithm for the Universal facility location problem. Our algorithm improves the approximation ratio of this problem from 5.83, given by Angel et al., to 5. A second major contribution of the paper is that it gets rid of the expensive multi operation that was a mainstay of all previous local search algorithms for capacitated facility location and universal facility location problem. The only operations that we require to prove the 5-approximation are add, open, and close. A multi operation is basically a combination of the open and close operations. The 5-approximation algorithm for the capacitated facility location problem, given by Bansal et al., also uses the multi operation. However, on careful observation, it turned out that add, open, and close operations are sufficient to prove a 5-factor for the problem. This resulted into an improved algorithm for the universal facility location problem, with an improved factor.

In this paper, we give the first constant factor approximation algorithm for capacitated knapsack median problem (CKnM) for hard uniform capacities, violating the budget by a factor of 1+epsilon and capacities by a 2+epsilon factor. To the best of our knowledge, no constant factor approximation is known for the problem even with capacity/budget/both violations. Even for the uncapacitated variant of the problem, the natural LP is known to have an unbounded integrality gap even after adding the covering inequalities to strengthen the LP. Our techniques for CKnM provide two types of results for the capacitated k-facility location problem. We present an O(1/epsilon^2) factor approximation for the problem, violating capacities by (2+epsilon). Another result is an O(1/epsilon) factor approximation, violating the capacities by a factor of at most (1 + epsilon) using at most 2k facilities for a fixed epsilon>0. As a by-product, a constant factor approximation algorithm for capacitated facility location problem with uniform capacities is presented, violating the capacities by (1 + epsilon) factor. Though constant factor results are known for the problem without violating the capacities, the result is interesting as it is obtained by rounding the solution to the natural LP, which is known to have an unbounded integrality gap without violating the capacities. Thus, we achieve the best possible from the natural LP for the problem. The result shows that the natural LP is not too bad.

The replica placement problem has been well studied on trees. In this paper, we study this problem on directed acyclic graphs. The replica placement problem on general DAGs generalizes the set cover problem. We present a constant factor approximation algorithm for the special case of DAGs having bounded degree and bounded tree-width (BDBT-DAGs). We also present a constant factor approximation algorithm for DAGs composed of local BDBT-DAGs connected in a tree like manner (TBDBT-DAGs). The latter class of DAGs generalizes trees as well; we improve upon the previously best known approximation ratio for the problem on trees. Our algorithms are based on the LP rounding technique; the core component of our algorithm exploits the structural properties of tree-decompositions to massage the LP solution into an integral solution.

In this paper, we study the replica placement problem on trees and present a constant factor approximation algorithm (with an additional additive constant factor). This improves the best known previous algorithm having an approximation ratio dependent on the maximum degree of the tree. Our techniques also extend to the partial cover version. Our algorithms are based on the LP rounding technique. The core component of our algorithm exploits a connection between the natural LP solutions of the replica placement problem and the capacitated vertex cover problem.

In this paper we present the generalization of the relaxed Multi- Organization Scheduling Problem (α MOSP). In our generalized problem, we are given a set of organizations; each organization is comprised of a set of machines. We are interested in minimizing the global makespan while allowing a constant factor, αO, degradation in the local objective of each organization and a constant factor, αM, degradation in the local objective of each machine. Previous work on α MOSP have primarily focussed on the degree of co-operativeness only at organization level whereas the degree of co-operativeness of an individual machine is also equally important. We develop a general framework for building approximation algorithms for the problem. Using this framework we present a family of approximation algorithms with varying approximation guarantees on the global makespan and the degrees of cooperativeness of the machines and organizations. In particular, we present (4, 2, 3), (4, 3, 2) and (3, 3, 3) approximation results where the first, and second values in the triplet represent the degree of co-operativeness of the machines and the organizations respectively and the third value denotes approximation guarantee for the global makespan. We also present and experimentally analyze different heuristics to improve the global makespan once solutions with the above theoretical guarantees are obtained.

Biclustering solutions generally depend upon various parameters like number of biclusters and random initialisations. Ensemble techniques have been used to eliminate the impact of such parameters on the output. In this paper, we present a novel ensemble technique for biclustering solutions using mutual information. Unlike the existing approaches, the proposed technique does not require the biclusters to be aligned. As a result, it does away with the requirement that all the biclustering solutions generate the same number of biclusters. Moreover, most of the existing approaches require the user to specify the number of output biclusters. Our approach determines the number of well separated biclusters from the input solutions itself. Experiments performed on synthetic and real datasets show that our approach improves upon the biclustering error over the input solutions as well as the ensemble techniques of hanczar et al.

Abstract Most of the protocols to defend ad hoc networks against wormhole attacks rely on ‘trust your neighbor’ relationship. In this paper, we present an end‐to‐end algorithm which is more efficient than the existing algorithm both in terms of space and time. As our algorithm does not require speed and time, we do not need clock synchronization. We prove that our algorithm is able to detect wormholes with tunnel length greater than or equal to $ \left[\{({2p-1})/{2p}\}k+{2}/{p}\right]r_{\rm max}$ , where $p ={r_{\rm max}}/{r_{\rm min}}$ , $r_{\rm min}$ is the minimum communication range, $r_{\rm max}$ is the maximum communication range between any two nodes, and $k$ is path length in terms of the number of hop‐counts. However, with the help of simulations we show that we are able to detect wormholes even when tunnel length is much less than $\left[\{({2p-1})/{2p}\}k+{2}/{p}\right]r_{\rm max}$ . We also studied the effect of error in the positions of the node on the wormhole detection capability. In the absence of any error in the location, there are no false alarms and in the presence of error the effect on detection capability is negligible. Copyright © 2011 John Wiley & Sons, Ltd.

We present a parallel version of BIRCH with the objective of enhancing the scalability without compromising on the quality of clustering. The incoming data is distributed in a cyclic manner (or block cyclic manner if the data is bursty) to balance the load among processors. The algorithm is implemented on a message passing share-nothing model. Experiments show that for very large data sets the algorithm scales nearly linearly with the increasing number of processors. Experiments also show that clusters obtained by PBIRCH are comparable to those obtained using BIRCH

In this paper we focus on the problem of designing very fast parallel algorithms for the convex hull problem in two and three dimensions in the arbitrary CRCW model whose running times are output-size sensitive.